《初等数论》习题解答（第三版）广东石油化工学院
?n?1?!?p?n?!???1?
n?1?p?1?!???1???1?
n?1???1n??modp?
其次由p?4m?1，可令n?2m?1?p ，代入上式
即有 ?2m!???1?mopd?
故原同余式的解为 x???2m?!?modp? §3 勒让得符号
1．用本节方法判断下列同余式是否有解
2?i?x2?429?mod5?63 ?ii?x2?680?mod7?6 9 其中503，563，769，1013都是质数
013?iii?x2?503?mod1? 解：?i???429???1，有解。 ?563?680??ii?????1，有解。
769???iii???503???1，有解。 ?1013?2、求出以?2为平方剩余的质数的一般表达式；以?2为平方非剩余的质数的一般表达式。
p?1p?1??2???1??2??28 解：????1????????p??p??p?2p?1p2?1??2n ?2为模p平方剩余时，必有28?i?p?4k?1，必有p?8k??1，故p?8m?1 ?ii?p?4k?3，必有p?8k??3，故p?8m?3
p?1p2?1??2n?1 ?2为模p平方非剩余时，必有28?i?p?4k?1，必有p?8k??3，故p?8m?5
46 / 77
《初等数论》习题解答（第三版）广东石油化工学院
?ii?p?4k?3，必有p?8k??1，故p?8m?7
3、设n是正整数，4n?3及8n?7都是质数，说明
24n?3?1(mod8n?7)
由此证明：23|211?1,47|223?1,503|2251?1。
证明：当p?8n?7时，由本节定理1的推论知2为平方剩余，应用欧拉判别条件即有
2p?12?1(modp)
由p?8n?7，即得出24n?3?1(mod8n?7)
而23?8?2?7,47?8?5?7,503?8?62?7都是形如8n?7的素数，并且
11?23?147?1503?1，所以 ,23?,251?22223|211?1,47|223?1,503|2251?1。
§4 前节定理的证明
1、 求以?3为平方剩余的质数的一般表达式，什么质数以?3为平方非剩余？
p?1?3??p?解：由互反律 ?????1?2??
?3??p?p?12因此??1??3??p?,??当它们同为1或同时为?1时，???1， ?3??p??3????1 p??p?12一为1，一为?1时，?p?1显然，当为偶数，而p?1(mod4)时，(?1)2p?1当是奇数，即p??1(mod4)时，(?1)2p?12?1，
??1。
再因为p是奇质数，关于模3我们有p?1或p??1， 当p?1(mod3)时，??p??1??????1 ?3??3? 47 / 77
《初等数论》习题解答（第三版）广东石油化工学院
当p??1(mod3)时，?
?p???1???????1 3???3?这样3为平方剩余时，p为下方程组的解
?p?1(mod3)?p??1(mod3)或? ??p?1(mod4)?p??1(mod4)由孙子定理，即可知p?1或?1(mod12)，立即 当p?12n?1时，3为平方剩余。
3为平方非剩余时，p为下方程组的解 ?p?1(mod3)?p??1(mod3)或 ??p??1(mod4)p?1(mod4)??由孙子定理，即可知p?5或?5(mod12)，立即 当p?12n?5时，3为平方非剩余。
p?1?3?133因为()?()()?(?1)2()
pppp当
33p?1p?1为偶数，()?1，或为奇数，()??1时，即
pp22p?12n?1或12n?5时，?3为平方剩余，
类似p?12n?1或12n?5，?3为平方非剩余。 2、求以3为最小平方非剩余的质数的一般表达式。 解：由上题知以3为平方非剩余的质数p满足：
p??5(mod12)
又由3为模p的最小平方非剩余，故()＝1 从而p??1(mod8)（§3Th1推证）
48 / 77
2p 《初等数论》习题解答（第三版）广东石油化工学院
满足p??5(mod12)的素数p形如24m?5,24m?7,24m?17,24m?19， 其中只有24m?7,24m?17满足p??1(mod8)
故p?24m?7或24m?17时，3为它的最小平方非剩余。 §5 雅可比符号 1、 判断§3习题1所列各同余式是否有解。 略
2、 求出下列同余式的解数：
(i)x2?3766(mod5987)，(ii)x2?3149(mod5987)其中5987是一个质数。
解：(i)(37662?188321883)?()?()() 598759875987598725987?748?8?3，故()??1
59871883?15987?1?1883598759873382()(?1)2()??()??() 598718831883188321691691883246??()()?()?()?()?()
1883188318831691691692331694?()()?()?()?()?1 16916916933故??3766????1，即?i?的解数为0． ?5987??3149???1，故解数为2． ?5987? ?ii? ?3． ?i?在有解的情况下，应用定理1，求同余式
x2?a(modp)，p?4m?3的解。
?ii?在有解的情况下，应用 §2 定理1及§3定理1的推论，求同余式
x2?a(modp)，p?8m?5的解。
解：同余式x2?a(modp)有解，故
a1(p?1)2?1(modp)
49 / 77
《初等数论》习题解答（第三版）广东石油化工学院
?i? a1(p?1)2?a?a1(p?1)2?a(modp)
由p?4m?3知(am?1)2?a(modp) 故x??a(modp)即为原同余式的解。
?ii? 由p?8m?5知
1(p?1)?4m?2，故 2a4m?2?1?0(modp)
故(a2m?1?1)(a2m?1?1)?0(modp)
因此(a2m?1?1)?0(modp)或(a2m?1?1)?0(modp) 若前式成立，那末a2m?1?a?a(modp) 即 (am?1)2?a(modp)
若a2m?1?1(modp)则原同余式的解是x??am?1(modp) 即 x??am?1(modp)为原同余式的解。
1 若后式成立，那末 a2m?1?a??a(modp)
由§3定理1的推论知，2是模p的平方剩余，即
1(p?1)22?24m?2??1(modp)
于是： 24m?2?a2m?2?a(modp)
2 若a2m?1??1(modp)则原同余式的解是
x??22m?1am?1(modp)
故x??22m?1am?1(modp)为原同余式的解． §6 合数模的情形
25)?x?41(mod64) 1. 解同余式 ?i?x2?59(mod1，?ii
解：从同余式x2?59(mod125) 得x?2(mod5)
50 / 77