初等数论总复习(4)

法方法都是这一标准形式得到的。

同余方程组（1）有解的条件?(mi ,mj) ∣bi-bj ，1?i，j?k 。 在使用时一定要对所有可解进行验算，进行有解的判别

求解一次同余方程组（1）有两种方法：待定系数法和孙子定理。二种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是二二互素。孙子定理为下面定理：

（孙子定理）k?2,m1,m2,....,mk两两互素，m?m1m2...mk,m?miMi,i?1,2,...k则一次同余式组 x?b1(modm1),x?b2(modm2),..x?bk(modmk) 的解为 ''x?M1M1'b1?M2M2b2?...MkMkbk(modm), 其中MiMi'?1(modmi),i?1,2,...k. 对待定系数法和孙子定理要有深刻的理解。体会其实质，这样不必死记硬背。

次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理也可求出原同余方程的解。

求高次同余方程解的基本方法有两条，一是小模，二是降次。 设m=?k?1p1?pk；则要求f(x) ≡0(mod m)的解只要求f(x) ≡0(mod pα) (2) 的解即可，其中p为素数。α?1 。

对于（2）的解的求法我们用待定系数法。

设f(x) ≡0(mod p)的解为x≡x1(mod p)为解。则当p├ f′(x)时，

f(x) ≡0(mod p)的一个解x1可求出f(x) ≡0(mod p)的一个解。方法如下：

2

将x=x1+pt1代入 f(x) ≡0(mod p)有

22

f(x1+pt1) ≡0(mod p)?f(x1)+pt1f′(x1) ≡0(mod p)

2

?f?x1?,+t1f(x1) ≡0(mod p) ?t1=t1′+ p t2 p2

2

代入 x=x1+pt1=x1+p(t1′+t2p)=x2+ pt2

则 x≡x2(mod p)即为f(x) ≡0(mod p)的解。然后重复上述过程，即可由x2得f(x) ≡0(mod pα)的解 x3 。最后求出f(x) ≡0(mod pα)的解x?

从上所述，关键是求素数模的同余方程f(x) ≡0(mod p)的解。 f(x) ≡0(mod p)的性质 （1）同余方程的解与f(x)的分解之间的关系，这一点和代数方程几乎一样。注意素数p的条件必不可少。 （2）同余方程的解数与次数之间有关系 解数?次数。这一点和代数方程也一样。此时，素数p的条件

也必不可少

本节的辅产品是著名的wilsom定理。 P为素数，则有(p-1)！≡-1(mod p)， 实际上wilsom定理的逆定理也成立。故wilsom定理可以作为素数成立主要条件。

2

2

五、例子选讲

补充知识

定义1：当（a，m）=1时，若ab?1(modm)，则记b?根据定义和记号，则

1(modm)，称为形式分数。 ac1表示c?关于模m，则有下列性质 aa1、

cc?mt1?(modm),t1,t2?Z. aa?mt2cc1?(modm). aa12、若（d，m）=1，且a?da1,c?dc1,则利用形式分数的性质把分母变成1，从而一次同余式的解。

例1：解一次同余式17x?19(mod25)

解：∵（17，25）=1，原同余方程有解，利用形式分数的性质，

同余方程解为 x?

19?618?7????7(mod25) 17?824?112)?x??2(mod?10) 例2：解同余方程组?x?6(mod?x?1(mod15)?解：∵（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1

∴ 原同余方程有解，且等位于

?x??2(mod4)?x??2(mod3)??x??2(mod4)?x?6(mod2)????x?1(mod3) 此时变成模两两互素 ??x?1(mod5)?x?6(mod5)??x?1(mod3)???x?(mod5)由孙子定理可求得其解为：x?46(mod60)

例3：解一次同余式组

?51x?57(mod75) ??3x?1(mod4)解: 用常规方法先求每一个一次同余式的解，得到下列一次同余式组

?x?7,32,57(mod75) ?x?3(mod4)?然后用孙子定理求解，所以同余方程组有3个解，且解分别为

x?7(mod300)，x?107(mod300)，x?207(mod300)

例4：设2p+1是素数，则

(P!)2?(?1)p?0(mod2p?1)

证：设n=2p+1,由假设n为素数，于是由威尔逊定理有(n-1)! ≡-1(mod n) 由于(n-1)!+1≡(n-1)(n-2)?(p+2)(p+1)p(p-1)?3·2·1+1 ≡1·(n-1)·2(n-2)·2(n-3)?·(p-1)[n-(p-1)]·p·(n-p)+1

2p≡p!(n-1)(n-2)?(n-p)+1≡(p!)(-1)+1(mod n)

p∴ (p!)2(-1) +1≡0(mod n) ∴ (p!)2+(-1)p≡0(mod 2p+1)

例5：解同余方程28x≡21(mod 35) 解：∵ （28,35）=7|21，

∴ 原同余方程有解，且有7个解 原同余方程等价于4x≡3(mod 5) 而且4x≡3(mod 5)解为x≡2(mod 5)

∴ 原同余方程解为2，7，12，17，22，27，31（mod 35）

第五章 二次剩余理论

一、 主要内容

平方剩余与平方非剩余的概念、欧拉判别条件、勒让德符号、二次互反律、雅可比符号、素数模同余方程的解法

二、基本要求

通过本章的学习，掌握平方剩余与平方非剩余的概念，掌握勒让德符号的定义、性质计算及利用它来判别一个二次同余方程是否有解，对于几个较特殊的勒让德符号的值，要求能掌握它的推导方法。了解推可比符号的定义，性质及功能，会解素数的模的二次同余方程。及证明一些二次不定方程无解中的应用。

三、重点和难点

（1）欧拉判别定理：即a为p的平方剩余的条件。

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

四、自学指导

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

2

x ≡a(mod p) (a ,p)=1 p为奇素数。 （1） 以下内容都是在标准形式下得到的。其中p为奇素数。 平方剩余和平方非剩余是以同余方程（1）是否有解来定义的。因此平方剩余和平方非剩余只要在模p的一个简化剩余系中找即可。实际上，模m的全体平方剩余和全体平方非剩余构成了模p的一个简化剩α

α

p?1?同余。这为我余系。因为平方剩余和平方非剩余各占一半，且平方剩余与下列数列1，2，?????2??222们提供了计算模p的平方剩余的方法，另一个为欧拉判别定理ap?12 ≡1(mod p)，这个定理的证明依赖于高次同余方程的素数模p，次数等于解数的条件，再结合欧拉定理即可得到，但缺点是计算量比较大。

?1?=1或?2?=1为了弥补计算量大的不足，引进了勒让德符号，根据定义可得到一系列性质，其中????p???p??????的p及????1??2?=-1，=-1的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 13 1，3，4，12，9，10 2，5，6，7，8，11

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

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

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

2

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

?a?即计算??=1或-1 。

?p????a??a?2、已知a，求所有使及??=1或??=-1的p的一般形式。

?p??p??????a?2

3、在??=1的条件下，如何求出x≡a(mod p)的解。若x1为一个解，则另一个解为-x1 。

?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的平方

2

非剩余，因而a+py一定不是平方数。而不能有x=a+py这样可淘汰满足y≡vi(mod g)的各个y的值。 取不同的q，淘汰y的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出（1）的解。

2

例：解同余方程x≡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 。

22

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

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