初等数论总复习题及知识点总结(6)

（2）勒让德符号，二次互反律。 （3）素数模同余方程的解法。

四、自学指导

对于一般的高次同余方程的求解归纳为模为pα的情形。对于同余方程f(x)≡0(mod pα)的求解依赖于f(x) ≡o(mod p)的解。而且对于一般的f(x)，求解f(x) ≡0(mod p)的解是很困难的。本章讨论f(x)为一个整系数的二次三项式时情形。可得到二次同余式的标准形式

x2 ≡a(mod p) (a ,p)=1 p为奇素数。 （1） 以下内容都是在标准形式下得到的。其中p为奇素数。

平方剩余和平方非剩余是以同余方程（1）是否有解来定义的。因此平方剩余和平方非剩余只要在模p的一个简化剩余系中找即可。实际上，模m的全体平方剩余和全体平方非剩余构成了模p的一个简化剩余系。因为平方剩余和平方非剩余各占一半，且平方剩余与下列数

p?1?同余。这为我们提供了计算模p的平方剩余的方法，另一个为欧拉判列1，2，?????2??222别定理ap?12 ≡1(mod p)，这个定理的证明依赖于高次同余方程的素数模p，次数等于解数

的条件，再结合欧拉定理即可得到，但缺点是计算量比较大。

为了弥补计算量大的不足，引进了勒让德符号，根据定义可得到一系列性质，其中

??1?=1或?2?=1的p及??1?=-1，?2?=-1的p的值需要记忆，

?????p???p???p???p??????????即有

1、p=4K+1时，-1是p的平方剩余，p=4K+3时，-1是p的平方非剩余。

2、p=8K+1或8K-1时，2是p的平方剩余，p=8K+3或8K-3时，2是p的平方非剩余。 3、对一些较小的素数其平方剩余和平方非剩余列表如下：

P 平方剩余 平方非剩余 3 1 2 5 1，4 2，3 7 1，2，4 3，5，6 11 1，3，4，5，9 2，6，7，8，10

26

13 1，3，4，12，9，10 2，5，6，7，8，11

其余性质要理解，特别是二次互反律的条件为p，g为二个不同的奇素数。勒让德符号计算的最大困难对a要进行素因数分解，往往很烦，也很困难。

为了弥补这个困难，再引进雅可比符号，由雅可比符号的定义出发可建立形式上和勒让德符号完全一致的性质。由于雅可比符号是勒让德符号的推广，因此雅可比符号在这里的主要功能是为了计算勒让德符号的值。

本章主要解决以下三个问题

1、已知素数p判别同余方程x2≡a(mod p)是否有解。

a?=1或-1 。 即计算??????p?a?=1或?a?=-1的p的一般形式。 2、已知a，求所有使及??????????p??p?a?=1的条件下，如何求出x2≡a(mod p)的解。若x为一个解，则另一个解为-x 。 3、在?11?????p?上述已叙述了问题（1）、（2），现在只剩下解（3）解的方法。除了书上介绍的公方法，我们再补充另一个方法即高斯逐步淘汰法。 五、例子选讲

补充知识

pp22高斯逐步淘汰法：首先，不妨设0

24x2?ax2p因解同余方程x≡a(mod p)（1）相当于不定方程x=a+py，故0

pp422

因而在求y的值时，不必考虑大于

p的整数，这就大大缩小了讨论的范围。 4其次，任取素数q≠p，求出q的平方非剩余为a1 ,a2??as并以v1 ,v2,??vs表示同余方程 a+py≡a1 (mod q) ,a+py≡a2(mod q)，??

a+py≡as(mod q)的解，由于平方数一定为任何模的平方剩余，故若取y≡vi(mod q)，则a+py是q的平方非剩余，因而a+py一定不是平方数。而不能有x2=a+py这样可淘汰满足y≡vi(mod g)的各个y的值。

取不同的q，淘汰y的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出（1）

27

的解。

例：解同余方程x2≡73(mod137)

?73?2

解 ∵ ??=1，∴x≡73(mod137)有二个解

?137?

因为p=137，故0

取q=3，则2为3一平方非剩余。 解同余方程 73+137y≡3(mod3)

得y≡2(mod 3)，从不大于34的正整数中淘汰形如y=2+3t的数，即有下面

1，3，4，6，7，9，10，12，13，15，16，18，19，21，22，24，25，27，28，30，31，33，34。

再取q=5，2，3为g的平方非剩余的同余方程

73+137y≡2(mod5) ，73+137y≡3(mod5)解为y≡2(mod5) ,y≡0(mod5)，再从前面的数中淘汰形如y=2+5t和y=5t，有下面

1，3，4，6，9，13，16，18，19，21，24，28，31，33，34。 又取q=7，3，5，6为g的三个平方非剩余的同余方程 73+137y≡3,5,6(mod7)

的y≡0,4,6(mod7)淘汰y=4+7t,7t,6+7t,就只留下了 1,3,9,16,19,24,31,33 。

将上述数代入137y+73=x2及137×3+73=484=222 故x≡±22(mod137)为本题同余方程的解。

例1：设p=4n+3是素数，试证当q=2p+1也是素数时，梅素数Mp不是素数。 证：∵ q=8n+7,24n?3?2q?12?2????q???1(modq) ??∴ q|24n+3-1，即q |Mp，∴ Mp不是素数。

例2：若3是素数p平方剩余，问p是什么形式的素数？

28

?3?解：∵ 由反转定律??p???(?1)??p?12?p????， ?3?p?1(mod4)

p??1(mod4)p??1注意到p>3，p只能为p??1(mod 3)且?????

?3???1?3???p???1只能下列情况 ??∴

?p?1(mod3) ?p?1(mod4)?d)?p??1(mo3 ?

d)?p??1(mo4∴

p?1(mod12)或p??1(mod12)

例3：证明形如4m+1的素数有无穷多个。

证：假设形如4m+1的素数只有有限个，设为p1?pk，

显然(2p1?pk)2+1的最小素因数p是奇数，且p与p1?pk不同，

设p为4m+3形的素数，但p整除(2p1?pk)2+1，表明(2p1?pk)2+1≡0（mod p） 即x2

??1??1?≡(-1)(mod p)有解，即?，但????1?p??p???????(?1)p?12?(?1)2m?1??1矛盾，

∴p为4m+1形，这与4m+1的素数只有k个矛盾。

例4：证明不定方程x2+23y=17无解。 证：只要证x2≡17(mod 23)无解即可，

∵ 17≡1(mod 4) ∴

?17??23??6??2??3??3??17??2?????????????????????????1 ?23??17??17??17??17??17??3??3?∴ x2≡17(mod 23)无解，即原方程无解。

例5设x为整数，证明形如x2证：设2n+1是整数x2?1的整数的所有奇因数都有

4h+1的形式，（其中h为整数）

?1的任一奇素因数，于是有

x2?1?0(mod2n?1),即x2??1(mod2n?1).

可以证明，这时x2?0(mod2n?1)，否则有1?0(mod2n?1)，这是不可能的。

因此，由2n?1是奇素数，便有(x2,2n?1)?1。

29

从而(x,2n但是x2n?1)?1，这样由费马定理，有x2n?1(mod2n?1)。

?(x2)n?(?1)n(mod2n?1),因此有(?1)n?1(mod2n?1).

?1的的所有奇

?1由此可知，n必为偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数x2素因数形式必为4h+1形式。又由于两个4h+1形式的数的乘积仍为4h+1形式的数，故x2形式的数的奇因数必为4h+1形式的数。 证2：由上面可知，-1是模2n+1的平方剩余，即???1??2n?1???1.

其中2n+1是奇素数。由定理3知2n?1?1(mod4)

从而 2n?0(mod4)，故n?0(mod2)，所以n是偶数，其余同上。

例6：证明：形如p?1(mod8)的素数有无穷多个。

证：设N是任意正整数，p1,p2,...,ps是不超过N的一切形如p?1(mod8)的素数。记

q?(2p1p42...ps)?1。

显然q的任意素因数a异于2，且x?2p1p2...ps是同余式x4?1?0(moda)的解。由a?1(mod8).又由于是pi(i?1,2,...,s)不是q的因数，

故a?pi(i?1,2,...,s)，从而a?N。因此形如p?1(mod8)的素数有无穷多个。

例7: 解如下二次同余式x2?11(mod125)

解： (1)125=53。先解x2?11?1(mod5)。它的一个解是x=1。

再解x2?11(mod52)。令x?1?5y，

则有(1?5y)2?11(mod52).化简得(1?10y)?11(mod52)，

得到y?1(mod5),从而有5y?5(mod52)，1?5y?6(mod52)， 所以x2?11(mod52)的一个解为x?6,最后解x2?11(mod53)。

设x?6?52z。代入有(6?52z)2?11(mod53)，

30

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库初等数论总复习题及知识点总结(6)在线全文阅读。