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

二、基本要求

通过本章的学习要求掌握同余方程的一些基本概念，例同余方程的次数、解等，能解一次同余方程，一次同余方程组，理解孙子定理并用它来解一次同余方程组，会解高次同余方程，对于以素数模的同余方程的一般理论知识能理解。

三、重点和难点

（1） 孙子定理的内容与证明，从中学会求出一次同余方程组的解并从中引伸更一般的情

形，即模不二二互素的情形。

（2） 素数模的同余方程的一些基本理论性问题，并能与一般方程所类似的性质作比较。

四、自学指导

同余方程和不定方程一样，我们同样要考虑以下三个问题，即有解的条件，解数及如何求解，一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入验算总解组则所需的结果。因此上述三个问题已基本解决，只不过具体到某一个同余方程计算起来困难一点而异。但对于解数，传统的结果不再成立。例如一个同余方程的解数可以大于其次数。读者可以举出反例来证明这一事实。

要学好同余方程这一章。必须首先弄清同余方程的概念，特别是同余方程解的概念，互相同余的解是同一个解。其次有使原同余方程和新的同余方程互相等价的若干变换。移项运算是传统的，同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。无论是乘上一数k或除去一个数k，为了保持其同解性，必须（k ,m）=1，这一点和同余的性质有区别。

一次同余方程的一般形式为ax≡b(mod m)，我们讨论的所有内容都在这标准形式下进行的。总结一次同余方程与二元一次不定方程有相当的联系，一次同余方程的求解可以由二元一次不定方程的求解方式给出。反之亦然。但要注意在对“解”的认识上是不一致的，从而导致有无穷组解和有限个解的区别。为了求ax≡b(mod m)的一个特解，可在条件(a ,m)=1下进行。教材上有若干种求解方式，供读者在同样问题选择使用。

一次同余方程组的标准形式为

21

x≡b1(mod m1) x≡b2(mod m2)

?? (1) x≡bn(mod mn)

若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求法方法都是这一标准形式得到的。

同余方程组（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）的解的求法我们用待定系数法。

22

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

f(x) ≡0(mod p)的一个解x1可求出f(x) ≡0(mod p2)的一个解。方法如下： 将x=x1+pt1代入 f(x) ≡0(mod p2)有

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

?f?x1?+t1f,(x1) ≡0(mod p) ?t1=t1′+ p t2 p代入 x=x1+pt1=x1+p(t1′+t2p2)=x2+ p2t2

则 x≡x2(mod p2)即为f(x) ≡0(mod p2)的解。然后重复上述过程，即可由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定理可以作为素数成立主要条件。

五、例子选讲

补充知识

定义1：当（a，m）=1时，若ab?1(modm)，则记b?1(modm)，称为形式分数。 ac1根据定义和记号，则表示c?关于模m，则有下列性质

aa1、

cc?mt1?(modm),t1,t2?Z. aa?mt2cc1?(modm). aa123

2、若（d，m）=1，且a?da1,c?dc1,则

利用形式分数的性质把分母变成1，从而一次同余式的解。

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

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

同余方程解为 x?19?618?717??8?24??1?7(mod25)

?12)例2：解同余方程组?x??2(mod?x?6(mod10) ??x?1(mod15)解：∵（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1

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

??x??2(mod4)?x??2(mod3)???x?6(mod2)?x??2(mod4)6(mod5)???x?1(mod3) 此时变成模两两互素 ?x???x?1(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)

24

例4：设2p+1是素数，则 (P!)?(?1)2p?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 ≡p!(n-1)(n-2)?(n-p)+1≡(p!)2(-1)p+1(mod n) ∴ (p!)2(-1)p +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的平方剩余的条件。

25

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