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

1、初等数论学习总结本课程只介绍初等数论的的基本内容。由于初等数论的基本知识和技巧与中学数学有着密切的关系， 因此初等数论对于中学的数学教师和数学系(特别是师范院校)的本科生来说，是一门有着重要意义的课程，在可能情况下学习数论的一些基础内容是有益的一方面通过这些内容可加深对数的性质的了解，更深入地理解某些他邻近学科，另一方面，也许更重要的是可以加强他们的数学训练，这些训练在很多方面都是有益的正因为如此，许多高等院校，特别是高等师范院校，都开设了数论课程。 最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过如果学习数论时只注意到它的内容而

2、忽略习题的作用，则相当于只身来到宝库而空手返回而异。数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的“哥德巴赫猜想”和费马大定理的阅读材料。初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法最大公因数和辗转相除法整除的进一步性质和最小公倍数素数、算术基本定理x和x的性质及其在数论中的应用习题要求：2，3 ； ：4 ；：1；：1，2，5；：1。第二章：不定方程（4学时）自学12学时二元一次不定方程多元一次不定方程勾股数费尔马大定理。习题要求：1，2，4；：2，3。第三章：同余（4学时）自学12学时同余

3、的定义、性质剩余类和完全剩余系欧拉函数、简化剩余系欧拉定理、费尔马小定理及在循环小数中的应用习题要求：2，6；：1；：2，3； 1，2。第四章：同余式（方程）（4学时）自学12学时同余方程概念孙子定理高次同余方程的解数和解法素数模的同余方程威尔逊定理。习题要求：1；：1，2；：1，2。第五章：二次同余式和平方剩余（4学时）自学12学时二次同余式单素数的平方剩余与平方非剩余勒让德符号二次互反律雅可比符号、素数模同余方程的解法习题要求：2； ：1，2，3；：1，2；：2；：1。第一章：原根与指标（2学时）自学8学时指数的定义及基本性质原根存在的条件指标及n次乘余模2及合数模指标组、特征函数习题要求

4、：3。Ø 第一章 整除一、主要内容整除的定义、带余除法定理、余数、最大公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、算术基本定理、Eratosthesen筛法、x和x的性质、n！的标准分解式。二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除 整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个著名的定理：带余除法定理和算术基本定理。认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。能熟练求出二个整数的最大公因数和最小公倍数，掌握高斯函数x的性质及其应用。三、重点和难点（1）

5、素数以及它有关的性质，判别正整数a为素数的方法，算术基本定理及其应用。（2）素数有无穷多个的证明方法。（3）整除性问题的若干解决方法。（4）x的性质及其应用，n！的标准分解式。四、自学指导整除是初等数论中最基本的概念之一，ba的意思是存在一个整数q，使得等式a=bq成立。因此这一标准作为我们讨论整除性质的基础。也为我们提供了解决整除问题的方法。即当我们无法用整除语言来叙述或讨论整除问题时，可以将其转化为我们很熟悉的等号问题。对于整除的若干性质，最主要的性质为传递性和线性组合性，即（1） ab, bc, 则有ac（2） ab, ac, 则有amb+nc读者要熟练掌握并能灵活应用。特别要注意，数论

6、的研究对象是整数集合，比小学数学中非负整数集合要大。本章中最重要的定理之一为带余除法定理，即为设a是整数，b是非零整数，则存在两个整数q，r，使得 a=bq+r （0）它可以重作是整除的推广。同时也可以用带余除法定理来定义整除性，（即当余数r=0时）。带余除法可以将全体整数进行分类，从而可将无限的问题转化为有限的问题。这是一种很重要的思想方法，它为我们解决整除问题提供了又一条常用的方法。同时也为我们建立同余理论建立了基础。读者应熟知常用的分类方法，例如把整数可分成奇数和偶数，特别对素数的分类方法。例全体奇素数可以分成4k+1，4k+3；或6k+1，6k+5等类型。和整除性一样，二个数的最大公约

7、数实质上也是用等号来定义的，因此在解决此类问题时若有必要可化为等式问题，最大公因数的性质中最重要的性质之一为 a=bq+c，则一定有（a，b）=（b，c），就是求二个整数的最大公约数的理论根据。也是解决关于最大公约数问题的常用方法之一。读者应有尽有认真体会该定理的证明过程。互素与两两互素是二个不同的概念，既有联系，又有区别。要认真体会这些相关的性质，例如，对于任意a ,bZ，可设（a ,b）=d，则a=da1 ,b=db1，则（a1 ,b1）=1，于是可对a1 ,b1使用相应的定理，要注意，相关定理及推论中互素的条件是经常出现的。读者必须注意定理成立的条件，也可以例举反例来进行说明以加深影响。

8、顺便指出，若ac，bc，（a ,b）=1，则abc是我们解决当除数为合数时的一种方法。好处是不言而喻的。最小公倍数实际上与最大公因数为对偶命题。特别要指出的是a和b的公倍数是有无穷多个。所以一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数中的最小的正整数。这一点实际上是应用自然数的最小自然数原理，即自然数的任何一个子集一定有一个最小自然数有在。最小公倍数的问题一般都可以通过以下式子转化为最大公因数的问题。两者的关系为a ,bN， a ,b=上述仅对二个正整数时成立。当个数大于2时，上述式子不再成立。证明这一式子的关键是寻找a , b的所有公倍数的形式，然后从中找一个最小的正

9、整数。解决了两个数的最小公倍数与最大公因数问题后，就可以求出n个数的最小公倍数与最大公因数问题，可以两个两个地求。即有下面定理设是n个整数，则（）=设则有=素数是数论研究的核心，许多中外闻名的题目都与素数有关。除1外任何正整数不是质数即为合数。判断一个已知的正整数是否为质数可用判别定理去实现。判别定理又是证明素数无穷的关键。实际上，对于任何正整数n>1，由判别定理一定知存在素数p，使得pn 。即任何大于1的整数一定存在一个素因数p 。素数有几个属于内在本身的性质，这些性质是在独有的，读者可以用反例来证明：素数这一条件必不可少。以加深对它们的理解。其中pabpa或pb也是常用的性质之一。也

10、是证明算术基本定理的基础。算术基本定理是整数理论中最重要的定理之一，即任何整数一定能分解成一些素数的乘积，而且分解是唯一的，不是任何数集都能满足算术基本定理的，算术基本定理为我们提供了解决其它问题的理论保障。它有许多应用，由算术基本定理我们可以得到自然数的标准分解问题。设a=，b=，则有（a，b）= a，b= 例如可求最大公约数，正整数正约数的个数等方面问题，对具体的n，真正去分解是件不容易的事。对于较特殊的n，例如n！分解还是容易的。应用x的性质，n！的标准分解式可由一个具体的公式表示出来，这一公式结合x的性质又提供了解决带有乘除符号的整除问题的方法。本章的许多问题都围绕着整除而展开，读者应

11、对整除问题的解决方法作一简单的小结。五、例子选讲补充知识最小自然数原理：自然数的任意非空子集中一定存在最小自然数。抽屉原理：（1）设n是一个自然数，有n个盒子，n+1个物体，把n+1个物体放进n个盒子，至少有一个盒子放了两个或两个以上物体；（2）km+1个元素，分成k组，至少有一组元素其个数大于或等于m+1；（3）无限个元素分成有限组，至少有一组其元素个数为无限。梅森数：形如2n-1的数叫梅森数，记成Mn=2n-1。费尔马数：n为非负整数，形如的数叫费尔马数，记成Fn=。设n=，设n的正因子个数为d(n)，所有正因子之和为，则有有关技巧1. 整数表示a=a0×10n+a1×

12、10n-1+an，a=2kb(b为奇数) 2.整除的常用方法a. 用定义b. 对整数按被n除的余数分类讨论c. 连续n个整数的积一定是n的倍数d. 因式分解an-bn=(a-b)M1,an+bn=(a+b)M2, 2 ne. 用数学归纳法f. 要证明a|b，只要证明对任意素数p，a中p的幂指数不超过b中p的幂指数即可，用p(a)表示a中p的幂指数，则a|bp(a)p(b)例题选讲例1.请写出10个连续正整数都是合数.解: 11!+2，11!+3，11！+11。例2. 证明连续三个整数中，必有一个被3整除。证：设三个连续正数为a，a+1，a+2，而a只有3k，3k+1，3k+2三种情况，令a=3

13、k，显然成立，a=3k+1时，a+2=3(k+1)，a=3k+2时，a+1=3(k+1)。例3. 证明lg2是无理数。证：假设lg2是有理数，则存在二个正整数p，q，使得lg2=，由对数定义可得10=2，则有2·5 =2,则同一个数左边含因子5，右边不含因子5，与算术基本定理矛盾。lg2为无理数。例4. 求(21n+4，14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1例5. 求2004!末尾零的个数。解：因为10=2×5，而2比5多，所以只要考虑2004！中5的幂指数，即5（2004！）=例6.证明（n

14、!）(n-1)!|(n!)!证：对任意素数p,设（n!）(n-1)!中素数p的指数为，（n!）!中p的指数，则，,即，即左边整除右边。例7. 证明2003|（20022002+20042004-2005）证： 20022002=（2003-1）2002=2003M1+120042004=（2003+1）2002=2003M2+120022002+20042004-2005=2003（M1+M2-1）由定义2003|（20022002+20042004-2005）例8. 设d(n)为n的正因子的个数， (n)为n的所有正因子之和，求d(1000)， (1000)。解： 1000=23·

15、53 d(1000)=(3+1)(3+1)=16， (1000)=例9. 设c不能被素数平方整除，若a2|b2c，则a|b证：由已知p(c)1，且p(a2)p(b2c) 2p(a)2p(b)+p(c) , p(a)p(b)+即p(a) p(b) , a|b例10. 若Mn为素数，则n一定为素数。证：若n为合数，则设n=ab，（1<a,b<n） 2ab-1=(2a)b-1=(2a-1)M为合数，与Mn为素数矛盾， n为素数。例11. 证明对任意m,n，mn, (Fn,Fm)=1。证：不妨设n>m，则Fn-2=（）（）=(Fn-1-2) （）= Fn-1Fn-2Fm- F0设（F

16、n,Fm）=d,则d|Fn, d|Fmd|2但Fn为奇数，d=1, 即证。例12. 设m,n是正整数。证明证 : 不妨设。由带余数除法得 我们有由此及得,=注意到,若,则,结论成立.若,则继续对作同样的讨论，由辗转相除法知，结论成立。显见，2用任一大于1的自然a代替，结论都成立。例13. 证明：对任意的正整数，成立如下不等式。其中是数的以10为底的对数，是的不同的素因数（正的）的个数。证：设是大于1的整数（如果=1，上述不等式显然成立，因=0）， 是的个相异的素因素。的素因数分解式为.() , 由于，从而，而，故。将上述不等式取对数（设底）,则有。特别有。例14. 试证明任意一个整数与它的数字

17、和的差必能被9整除，并且它与它的数字作任意调后换后所成整数的差也能被9整除。证： 设整数m的个位、十位、百位的数字分别为,，则可表作： 所以因为，,，都是整数，所以任一整数与其数字之和的差必能被9整除。再设将,，按任一种顺序排成,，并令，。根据前面证明的结果，知存在整数A，B，使因为，所以。由于A-B是整数，这就证明了能被9整除。注：若对某个整数，有，但当时，则此时为整数：即。如前证，此时结论正确。又当为负整数及零时，结论显然正确。Ø 第二章 不定方程一、 主要内容一次不定方程有解的条件、解数、解法、通解表示，不定方程x2+y2=z2通解公式、无穷递降法、费尔马大定理。二、 基本要求

18、1、 了解不定方程的概念，理解对“解”的认识，掌握一次不定方程有解的条件，能熟练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程有解的条件，在有解的条件下的解法。2、掌握不定方程x2+y2=z2在一定条件下的通解公式，并运用这个通解公式作简单的应用。3、对费尔马大定理应有在常识性的了解，掌握无穷递降法求证不定方程x4+y4=z2无解的方法。4、掌握证明不定方程无解的若干方法。三、难点和重点（1）重点为求解一次不定方程的方法（2）掌握第二节中引证的应用。（1） 费尔马无穷递降法。四、自学指导不定方程主要讲解以下几个问题（i）给定一类不定方程，判别在什么条件下有解。（ii）在有解的条件

19、下，有多少解（iii）在有解的条件下，求出所给的不定方程的所有解。 二元一次不定方程的一般形式为ax+by=c 。若(a ,b)c，则该二元一次不定方程一定有解，若已知一个特解，则一切解可以用公式表示出来，因此求它的通解只要求出一个特解即可。求解二元一次不定方程的一个通解有好多种方法。读者应该总结一下，各种方法都有独到之处。特别要指出用最大公因数的方法。它的根据是求（a ,b）时所得的结果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意义和位置。以免出错。多元一次不定方程也有类似的结果，但在求解的过程中将它转化二元一次不定方程组，从最后一个二元一次不定方程解起，可逐一解出x

20、1 ,x2 ,xn 。所用的方法一般选择最大公因数的方法。由于n元一次不定方程可转化为n-1个二元一次不定方程组，故在通解中依赖于n-1个任意常数。但不象二元一次不定方程那样有公式来表示。x2+y2=z2的正整数解称为勾股数，在考虑这个方程时，我们对（x ,y）作了一些限制，而这些限制并不影响其一般性。在条件x>0，y>0，z>0，（x，y）=1，2x的条件可以给出x2+y2=z2的通解公式，x=2ab，y=a2-b2，z2=a2+b2，a>b>0 , (a ,b)=1，a ,b一奇一偶。若将2x限为2y，则也有相应的一个通解公式。在证明这个通解公式的过程中，用到

21、了引理 uv=w2，u>0，v>0，（u ,v）=1，则u=a2，v=b2，w=ab 。a>0，b>0，（a ,b）=1 。利用这个结论可以求解某些不定方程。特别当w=1或素数p 。则由uv=1或uv=P 可将原不定方程转化为不定方程组。从而获得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望读者能掌握这种方法。 为了解决著名的费尔马大定理：xn+yn=zn ，n3无正整数解时，当n=4时可以用较初等的方法给出证明。证明由费尔马本人给出的，一般称为费尔马无穷递降法。其基本思想为由一组解出发通过构造得出另一组解，使得两组解之间有某种特定的关系，而且这种构造可以无限

22、重复的。从而可得到矛盾。因此无穷递降法常用来证明某些不定方程无整数解。证明一类不定方程无解是研究不定方程邻域中常见的形式，一般的要求解不定方程比证明不定方程无解要容易些。证明不定方程无解的证明方法常采用以下形式：（反证法）若A有解A1有解A2有解An有解，而An本身无解，这样来构造矛盾。从而说明原不定方程无解。对于证明不定方程的无解性通常在几种方法，一般是总的几种方法交替使用。特别要求掌握：简单同余法、因子分解法、不等式法，以及中学数学中所涉及的判别式法。五、例子选讲例1：利用整数分离系数法求得不定方程15x+10y+6z=61。解：注意到z的系数最小，把原方程化为z=令t1=，即-3x+2y

23、-6t1+1=0此时y系数最小，令t2 =,即,反推依次可解得y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2z=-2x-2y+10+t1=6-5t1+10t2原不定方程解为t1t2z.例2:证明是无理数证：假设是有理数，则存在自数数a,b使得满足即，容易知道a是偶数，设a=2a1，代入得,又得到b为偶数，设，则,这里这样可以进一步求得a2，b2且有a>b>a1>b1> a2>b2>但是自然数无穷递降是不可能的，于是产生了矛盾，为无理数。例3：证明：整数勾股形的勾股中至少一个是3的倍数。证：设N=3m±1(m为整数) ， N2=9

24、m2±6m+1=3(3m2±2m)+1即一个整数若不是3的倍数，则其平方为3k+1,或者说3k+2不可能是平方数，设x,y为勾股整数，且x,y都不是3的倍数，则x2,y2都是3k+1，但z2=x2+y2=3k+2形，这是不可能，勾股数中至少有一个是3的倍数。例4：求x2+y2=328的正整数解解： 328为偶数，x,y奇偶性相同，即x±y为偶数，设x+y=2u, x-y=2v，代入原方程即为u2+v2=164,同理令u+v=2u1,u-v=2v1有为一偶一奇，且0<u2<6u2=1，2，3，4，5代方程，有解（4，5）（5，4）原方程解x=18,y=2

25、,或x=2,y=18。例5：求x2+xy-6=0的正整数解。解：原方程等价于x(x+y)=2·3,故有 ， 即有x=2,y=1; x=1,y=5.例6：证明不定方程x2-2xy2+5z+3=0无整数解。解：若不定方程有解，则但y40，1(mod5), 对y,z ，y4-5z-32，3(mod5)而一个平方数0，1，4（mod 5） y4-5z-3不可能为完全平方，即不是整数，所以原不定方程无解。例7：证明：无整数解证：若原方程有解，则有注意到对于模8，有因而每一个整数对于模8，必同余于0，1，4这三个数。不论如何变化，只能有而，故不同余于关于模8，所以假设错误，即，从而证明了原方程无

26、解。例8:某人到银行去兑换一张d元和c分的支票，出纳员出错，给了他c元和d元，此人直到用去23分后才发觉其错误，此时他发现还有2d元和2c分，问该支票原为多少钱？解：由题意立式得：即令得令得所以为任意整数），代入得：（1）其中v是任意整数。又根据题意要求：.根据(1)，仅当v=8时满足此要求，从而因此该支票原为25元51分.Ø 第三章 同余一、 主要内容同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数2，3，4，5，6，7，8，9，11，13的整除规律二、 基本要求通过本章的学习，能够掌握同余的定义和性质，区别符号：“三”和=”之间

27、的差异。能利用同余的一些基本性质进行一些计算，深刻理解完全剩余系，简化剩余系的定义、性质及构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的值，掌握欧拉定理、费尔马小定理的内容以及证明方法。能应用这二个定理证明有关的整除问题和求余数问题。能进行循环小数与分数的互化。三、难点和重点（1）同余的概念及基本性质（2）完全剩余系和简化剩余系的构造、判别（3）欧拉函数计算、欧拉定理、费尔马小定理的证明及应用（4）循环小数与分数的互化（5）特殊数的整除规律。四、自学指导同余理论是初等数论中最核心的内容之一，由同余定义可知，若ab(mod m)，则a和b被m除后有相同的余数。这

28、里m为正整数，一般要求m大于1，称为模，同余这一思想本质上是将整数按模m分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。第一章中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例子。从同余的定理上看，同余和整除实际上是同一回事，故同余还有二个等价的定义：用整除来定义即 ma-b 。用等号来定义a=b+mt 。值得注意a和b关于m同余是个相对概念。即它是相对于模m来讲，二个整数a和b关于一个整数模m同余。则对于另一个整数模m，a和b未必会同余。从定义上看，同余和整除是同一个事情，但引进了新的符号“三”后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，

29、同时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性质后，同余符号“三”和等号“=”相比，在形式上有几乎一致的性质，这便于我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即除法的消去律不成立。为此对于同余的除法运算我们有二种除法：（i）模不改变的除法，若akbk(mod m) ，(k,m)=1，则ab(mod m)(ii)模改变的除法, 若akbk(mod m) (k,m)=d,则ab这一点读者要特别注意。完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为同余关系是一个等价关系，利用等价关系可以进行将全体整数进行分类，弄清来胧去脉，对于更深刻理

30、解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合，在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余系包含m个整数，由于二个不同的剩余类中的数关于m两两不同余，故可得判别一组数是否为模m的一个完全剩余系的条件有二条为（1） 个数=m（2） 关于m两两不同余另外要能用已知完全剩余系构造新的完全剩余系。即有定理设（a，m）=1，x为m的完全剩余系，则ax+b也是m的完全剩余系。当时，能由的完全剩余系和的完全剩余系，构造完全剩余系。为讨论简化剩余系，需要引进欧拉函数(m)，欧拉函数(m)定义为不超过m且与m互素的正整数的个数，记为(m)，要掌握(m)的计算公式，了解它的

31、性质。这些性质最主要的是当（a ,b）=1时，(ab) = (a) (b)，和现在在剩余类中把与m互素的集合分出来，从中可在各个集合中任取一个数即可构造模m的一个简化剩余系。另一方面，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系，一组完全剩余系中与m互素的的数组成的(m)个不同数的集合称为m简化剩余系。同样简化剩余系也有一个判别条件。判别一组整数是否为模m的简化剩余系的条件为（2） 个数=(m)（3） 关于m两两不同余（3） 每个数与m互素关于m的简化剩余系也能用已知完全剩余系构造新的简化剩余系。设（a，m）=1，x为m的简化剩余系，则ax也是m的简化剩余系。当时，能由的简化剩余系和的

32、简化剩余系，构造简化剩余系。欧拉定理、费尔马小定理是同余理论非常重要的定理之一。要注意欧拉定理和费尔马定理的条件和结论。欧拉定理：设m为大于1的整数，（a，m）=1，则有费尔马小定理：若p是素数，则有 除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用。就欧拉定理、费尔马小定理来讲，它在某些形如a数的整除问题应用起来显得非常方便。同余方法也是解决整除问题的方法之一。另外同余方法在证明不定方程时也非常有用，即要掌握同余“三”和相等“=”的关系：相等必同余，同余未必相等，不同余肯定不相等。对于特殊数的整除规律要求能掌握其一般定理的证明，并熟记一些特殊数的整除规律1、 一个整数被2整除的充

33、要条件是它的末位为偶数。2、 一个整数被3整除的充要条件是它的各位数字之和能被3整除。3、 一个整数被9整除的充要条件是它的各位数字之和能被9整除。4、 一个整数被5整除的充要条件是它的末位为0或5。5、 一个整数被4，25整除的充要条件是它的末二位能被4，25整除。6、 一个整数被8，125整除的充要条件是它的末三位能被8，125整除。7、 设，则7或11或13整除a的充要条件是7或11或13整除五、例子选讲例1：求3406的末二位数。解： （3，100）=1，31（mod 100）(100)= (22·52)=40, 3401(mol 100) 3406=(340)10·

34、;36(32)2·32-19×9-17129(mod 100) 末二位数为29。例2：证明（a+b）pap+bp(mod p)证：由费尔马小定理知对一切整数有：apa（p），bpb(P)，由同余性质知有：ap+bpa+b(p)又由费尔马小定理有（a+b）pa+b (p)（a+b）pap+bp(p)例3：设素数p>2，则2P-1的质因数一定是2pk+1形。证：设q是2-1的质因数，由于2-1为奇数， q2， （2·q）=1,由条件q|2p-1,即21（mod q），又 （q,2）=1，21（mod q）设i是使得21（mod p）成立最小正整数若1<i&

35、lt;p，则有i|p则与p为素数矛盾 i=p, p|q-1又 q-1为偶数，2|q-1, 2p|q-1,q-1=2pk , 即q=2pk+1例4：证明13|42n+1+3n+2证：42n+1+3n+24·16n+9·3n 3n (4+9)13×3n·0(13) 13|42n+1+3n+2例5：证明5y+3=x2无解证明：若5y+3=x2有解，则两边关于模5同余有5y+3x2(mod 5)即3x2(mod 5)而任一个平方数x20,1,4(mod 5) 30,1,4(mod 5) 即得矛盾，即5y+3=x2无解例6：求被7除的余数。解：111111被7整除

36、，11（mod 7）4（mod 7），即余数为4。例7：把化为分数。解：设b=，从而1000b=,100000b=，99000b=4263-42b=。当然也可用直化分数的方法做。例8：设一个数为62XY427是9，11的倍数，求X，Y解：因为9|62XY427所以9|6+2+X+Y+4+2+7， 即9|21+X+Y又因为11|62XY427， 有11 |（7+4+X+6-2-Y-2）即11|（X-Y+13）因为0X，Y9， 所以有21 21+X+Y39，4 X-Y+13 22，由此可知21+X+Y=27，X-Y+13=11或21+X+Y=36，X-Y+13=22X+Y=6，X-Y=-2或X+Y

37、=15，X-Y=9，解得X=2，Y=4。例9：证明：8a+7不可能是三个整数的平方和。证：由于每一个整数对于8，必同余于0，1，2，3，4，5，6，7这八个数之一注意到对于模8，有因而每一个整数对于模8，必同余于0，1，4这三个数不能如何变化，只能有而，故不同余于关于模8，从而证明了结论。Ø 第四章 同余式一、 主要内容 同余方程概念及次数、解的定义，一次同余方程axb(mod m)有解的充分必要条件，一次同余方程组，孙子定理，高次同余方程，素数模的同余方程，威尔逊定理。二、基本要求通过本章的学习要求掌握同余方程的一些基本概念，例同余方程的次数、解等，能解一次同余方程，一次同余方程组

38、，理解孙子定理并用它来解一次同余方程组，会解高次同余方程，对于以素数模的同余方程的一般理论知识能理解。三、重点和难点（1） 孙子定理的内容与证明，从中学会求出一次同余方程组的解并从中引伸更一般的情形，即模不二二互素的情形。（2） 素数模的同余方程的一些基本理论性问题，并能与一般方程所类似的性质作比较。四、自学指导同余方程和不定方程一样，我们同样要考虑以下三个问题，即有解的条件，解数及如何求解，一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入验算总解组则所需的结果。因此上述三个问题已基本解决，只不过具体到某一个同余方程计算起来困难一点而异。但对于解数，传统的结果

39、不再成立。例如一个同余方程的解数可以大于其次数。读者可以举出反例来证明这一事实。要学好同余方程这一章。必须首先弄清同余方程的概念，特别是同余方程解的概念，互相同余的解是同一个解。其次有使原同余方程和新的同余方程互相等价的若干变换。移项运算是传统的，同余方程两边也可以加上模的若干倍。相当于同余方程两边加“零”。无论是乘上一数k或除去一个数k，为了保持其同解性，必须（k ,m）=1，这一点和同余的性质有区别。一次同余方程的一般形式为axb(mod m)，我们讨论的所有内容都在这标准形式下进行的。总结一次同余方程与二元一次不定方程有相当的联系，一次同余方程的求解可以由二元一次不定方程的求解方式给出。

40、反之亦然。但要注意在对“解”的认识上是不一致的，从而导致有无穷组解和有限个解的区别。为了求axb(mod m)的一个特解，可在条件(a ,m)=1下进行。教材上有若干种求解方式，供读者在同样问题选择使用。一次同余方程组的标准形式为xb1(mod m1)xb2(mod m2) (1)xbn(mod mn)若给出的同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理及求法方法都是这一标准形式得到的。同余方程组（1）有解的条件(mi ,mj) bi-bj ，1i，jk 。在使用时一定要对所有可解进行验算，进行有解的判别求解一次同余方程组（1）有两种方法：待定系数法和孙子定理。二

41、种方法各有特长。待定系数法适应的范围较广，对模没有什么要求。孙子定理有一个具体的公式，形式也较漂亮。但对模要求是二二互素。孙子定理为下面定理：（孙子定理）两两互素，则一次同余式组 的解为 其中对待定系数法和孙子定理要有深刻的理解。体会其实质，这样不必死记硬背。次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同余方程组。然后将每一个高次同余方程的解都求出，最后利用孙子定理也可求出原同余方程的解。求高次同余方程解的基本方法有两条，一是小模，二是降次。设m=；则要求f(x) 0(mod m)的解只要求f(x) 0(mod p) (2)的解即可，其中p为素数。1 。对于（2）

42、的解的求法我们用待定系数法。 设f(x) 0(mod p)的解为xx1(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)+ 0(mod p) t1=t1+ p t2代入 x=x1+pt1=x1+p(t1+t2p2)=x2+ p2t2则 xx2(mod p2)即为f(x) 0(mod p)的解。然后重复上述过程，即可由x2得f(x) 0(mod p)的解 x3 。最后求出f(

43、x) 0(mod p)的解从上所述，关键是求素数模的同余方程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，则记b，称为形式分数。根据定义和记号，则，则有下列性质1

44、、2、若（d，m）=1，且利用形式分数的性质把分母变成1，从而一次同余式的解。例1：解一次同余式解：（17，25）=1，原同余方程有解，利用形式分数的性质，同余方程解为 例2：解同余方程组解：（12，10）|6+2，（12，15）|-2-1，（10，15）|6-1 原同余方程有解，且等位于 此时变成模两两互素由孙子定理可求得其解为：例3：解一次同余式组解: 用常规方法先求每一个一次同余式的解，得到下列一次同余式组然后用孙子定理求解，所以同余方程组有3个解，且解分别为，例4：设2p+1是素数，则 证：设n=2p+1,由假设n为素数，于是由威尔逊定理有(n-1)! -1(mod n)由于(n-1)

45、!+1(n-1)(n-2)(p+2)(p+1)p(p-1)3·2·1+11·(n-1)·2(n-2)·2(n-3)·(p-1)n-(p-1)·p·(n-p)+1p!(n-1)(n-2)(n-p)+1(p!)2(-1)p+1(mod n) (p!)2(-1)p +10(mod n) (p!)2+(-1)p0(mod 2p+1)例5：解同余方程28x21(mod 35)解： （28,35）=7|21， 原同余方程有解，且有7个解原同余方程等价于4x3(mod 5)而且4x3(mod 5)解为x2(mod 5) 原同余方

46、程解为2，7，12，17，22，27，31（mod 35）Ø 第五章 二次剩余理论一、 主要内容平方剩余与平方非剩余的概念、欧拉判别条件、勒让德符号、二次互反律、雅可比符号、素数模同余方程的解法二、基本要求通过本章的学习，掌握平方剩余与平方非剩余的概念，掌握勒让德符号的定义、性质计算及利用它来判别一个二次同余方程是否有解，对于几个较特殊的勒让德符号的值，要求能掌握它的推导方法。了解推可比符号的定义，性质及功能，会解素数的模的二次同余方程。及证明一些二次不定方程无解中的应用。三、重点和难点（1）欧拉判别定理：即a为p的平方剩余的条件。（2）勒让德符号，二次互反律。（3）素数模同余方程的

47、解法。 四、自学指导对于一般的高次同余方程的求解归纳为模为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的一个简化剩余系。因为平方剩余

48、和平方非剩余各占一半，且平方剩余与下列数列12，22，同余。这为我们提供了计算模p的平方剩余的方法，另一个为欧拉判别定理a 1(mod p)，这个定理的证明依赖于高次同余方程的素数模p，次数等于解数的条件，再结合欧拉定理即可得到，但缺点是计算量比较大。为了弥补计算量大的不足，引进了勒让德符号，根据定义可得到一系列性质，其中=1或=1的p及=-1，=-1的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、 对一些较小的素数其平方剩余和平方非剩余列表

49、如下：P 平方剩余 平方非剩余3 1 25 1，4 2，37 1，2，4 3，5，611 1，3，4，5，9 2，6，7，8，1013 1，3，4，12，9，10 2，5，6，7，8，11其余性质要理解，特别是二次互反律的条件为p，g为二个不同的奇素数。勒让德符号计算的最大困难对a要进行素因数分解，往往很烦，也很困难。为了弥补这个困难，再引进雅可比符号，由雅可比符号的定义出发可建立形式上和勒让德符号完全一致的性质。由于雅可比符号是勒让德符号的推广，因此雅可比符号在这里的主要功能是为了计算勒让德符号的值。本章主要解决以下三个问题1、已知素数p判别同余方程x2a(mod p)是否有解。即计算=1或

50、-1 。2、已知a，求所有使及=1或=-1的p的一般形式。3、在=1的条件下，如何求出x2a(mod p)的解。若x1为一个解，则另一个解为-x1 。上述已叙述了问题（1）、（2），现在只剩下解（3）解的方法。除了书上介绍的公方法，我们再补充另一个方法即高斯逐步淘汰法。五、例子选讲补充知识高斯逐步淘汰法：首先，不妨设0<a<p是0<x<，故x2<，因解同余方程x2a(mod p)（1）相当于不定方程x2=a+py，故0<y= ，因而在求y的值时，不必考虑大于的整数，这就大大缩小了讨论的范围。其次，任取素数qp，求出q的平方非剩余为a1 ,a2as并以v1 ,

51、v2,vs表示同余方程a+pya1 (mod q) ,a+pya2(mod q)，a+pyas(mod q)的解，由于平方数一定为任何模的平方剩余，故若取yvi(mod q)，则a+py是q的平方非剩余，因而a+py一定不是平方数。而不能有x2=a+py这样可淘汰满足yvi(mod g)的各个y的值。取不同的q，淘汰y的值，直至留下的数较少是计算不太麻烦时，即可直接代入并求出（1）的解。例：解同余方程x273(mod137)解 =1，x273(mod137)有二个解因为p=137，故0<y34取q=3，则2为3一平方非剩余。解同余方程73+137y3(mod3) 得y2(mod 3)，从

52、不大于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+137y2(mod5) ，73+137y3(mod5)解为y2(mod5) ,y0(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+137y3,5,6(mod7)的y0,4,6(mod7)淘汰y=4+7t,7t,6+

53、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, q|24n+3-1，即q |Mp， Mp不是素数。例2：若3是素数p平方剩余，问p是什么形式的素数？解： 由反转定律，注意到p>3，p只能为p1(mod 3)且 只能下列情况 或例3：证明形如4m+1的素数有无穷多个。证：假设形如4m+1的素数只有有限个，设为p1pk，显然(2p1pk)2+1的最小素

54、因数p是奇数，且p与p1pk不同，设p为4m+3形的素数，但p整除(2p1pk)2+1，表明(2p1pk)2+10（mod p）即x2(-1)(mod p)有解，即，但矛盾，p为4m+1形，这与4m+1的素数只有k个矛盾。例4：证明不定方程x2+23y=17无解。证：只要证x217(mod 23)无解即可， 171(mod 4) x217(mod 23)无解，即原方程无解。例5设x为整数，证明形如的整数的所有奇因数都有4h+1的形式，（其中h为整数）证：设2n+1是整数的任一奇素因数，于是有即可以证明，这时，否则有，这是不可能的。因此，由是奇素数，便有。从而，这样由费马定理，有。但是因此有由此可知，n必为偶数，记n=2h,便有2n+1=4h+1.这样便证明了整数的的所有奇素因数形式必为4h+1形式。又由于两个4h+1形式的数的乘积仍为4h+1形式的数，故形式的数的奇因数必为4h+1形式的数。证2：由上面可知，-1是模2n+1的平方剩余，