《初等数论》习题解答（第三版）广东石油化工学院

?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