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

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

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

3、大定理。习题要求 P29: 1, 2, 4; P31 : 2, 3。第三章：同余 4 学时自学 12学时 同余的定义、性质 剩余类和完全剩余系 欧拉函数、简化剩余系 欧拉定理、费尔马小定理与在循环小数中的应用 习题要求 p43 ：2， 6； p46 ：1； p49 ： 2，3； p53 1 ，2。第四章：同余式方程 4 学时自学 12学时同余方程概念子定理 高次同余方程的解数和解法 素数模的同余方程 威尔逊定理。习题要求 p60：1； p64 ：1，2； p69 ： 1，2。第五章：二次同余式和平方剩余 4 学时自学 12 学时二次同余式单素数的平方剩余与平方非剩余勒让德符号二次互反律雅可比符

4、号、素数模同余方程的解法习题要求 p78 ：2； p81 ：1， 2， 3； p85 ：1，2； p89 ：2； p93 ： 1。 第一章：原根与指标 2 学时自学 8 学时指数的定义与根本性质原根存在的条件指标与 n 次乘余 模 2 与合数模指标组、特征函数习题要求p123: 3。? 第一章整除一、主要容整除的定义、带余除法定理、余数、最大公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、 算术根本定理、Eratosthesen筛法、x和x的性质、n!的标准分 解式。二、根本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除整除的定义以与它的根本性质，并能应用这些性质，了解

5、解决整除问题的假设干方法，熟练掌握本章中二个著名的定理： 带余除法定理和算术根本定理。 认真体会求二个数的最大公因数的求法的理论依据，掌握素数的定义以与证明素数有无穷多个的方法。能熟练求出二个整数的最大公因数和最小公倍 数，掌握高斯函数x的性质与其应用。三、重点和难点(1) 素数以与它有关的性质，判别正整数 a为素数的方法，算术根本定理与其应用(2) 素数有无穷多个的证明方法。(3) 整除性问题的假设干解决方法。(4) x的性质与其应用，n!的标准分解式。四、自学指导整除是初等数论中最根本的概念之一，b I a的意思是存在一个整数q,使得等式a=bq 成立。因此这一标准作为我们讨论整除性质的根

6、底。也为我们提供了解决整除问题的方法。 即当我们无法用整除语言来表达或讨论整除问题时，可以将其转化为我们很熟悉的等号问 题。对于整除的假设干性质，最主要的性质为传递性和线性组合性，即(1)a I b, b I c,那么有 a I c(2) a I b, a I c,贝U有 a I mb+nc读者要熟练掌握并能灵活应用。特别要注意，数论的研究对象是整数集合，比小学数学 中非负整数集合要大。本章中最重要的定理之一为带余除法定理，即为设a是整数，b是非零整数，那么存在两个整数 q, r，使得a=bq+r(0 r冋)它可以重作是整除的推广。同时也可以用带余除法定理来定义整除性，(即当余数r=0时)。带

7、余除法可以将全体整数进行分类，从而可将无限的问题转化为有限的问题。这是一种很重要的思想方法，它为我们解决整除问题提供了又一条常用的方法。同时也为我们建立同余理论建立了根底。读者应熟知常用的分类方法，例如把整数可分成奇数和偶数，特别对 素数的分类方法。例全体奇素数可以分成 4k+1, 4k+3;或6k+1, 6k+5等类型。和整除性一样，二个数的最大公约数实质上也是用等号来定义的，因此在解决此类问题时假设有必要可化为等式问题，最大公因数的性质中最重要的性质之一为a=bq+c，那么一定有(a, b) =(b, c),就是求二个整数的最大公约数的理论根据飞是解决关于最大公约数问 题的常用方法之一。读

8、者应有尽有认真体会该定理的证明过程。互素与两两互素是二个不同的概念,既有联系，又有区别。要认真体会这些相关的性质， 例如，对于彳匚意 a ,b Z, 可设(a ,b ) =d，贝U a=dai ,b=db 1,贝U( ai ,b 1) =1，于是可对 ai ,b i使用相应的定理，要注意，相关定理与推论中互素的条件是经常出现的。读者必须注 意定理成立的条件，也可以例举反例来进行说明以加深影响。顺便指出，假设|a I c,b I c,(a小 =1,那么ab I C是我们解决当除数为合数时的一种方法。好处是不言而喻的。最小公倍数实际上与最大公因数为对偶命题。特别要指出的是a和b的公倍数是有无穷多个

9、。所以一般地在无穷多个数中寻找一个最小数是很困难的，为此在定义中所有公倍数中的最小的正整数。这一点实际上是应用|自然数的最小自然数原理即自然数的任何一个子集 一定有一个最小自然数有在。最小公倍数的问题一般都可以通过以下式子转化为最大公因数 的问题。两者的关系为a ,b N, a ,b=-2a, b上述仅对二个正整数时成立。当个数大于2时，上述式子不再成立。证明这一式子的关 键是寻找a , b的所有公倍数的形式，然后从中找一个最小的正整数。解决了两个数的最小公倍数与最大公因数问题后，就可以求出|n个数的最小公倍数与最大公因数问题，可以两个两个地求。即有下面定理设 ai,a2, an 是 n 个整

10、数，(印®) d2，(d2,a3) d?, (dni,aQ dn,那么(aa?, an) = dn,|设aia? m2，(m2,a3) m3, (m. i,an) m.,那么有印月2, an=mn，素数是数论研究的核心，许多中外闻名的题目都与素数有关。除1外任何正整数不是质数即为合数。判断一个的正整数是否为质数可用判别定理去实现。判别定理又是证明素数无穷的关键。实际上，对于任何正整数 n>1,由判别定理一定知存在素数 p,使得p I n 即任何大于1的整数一定存在一个素因数p。素数有几个属于在本身的性质，这些性质是在 独有的，读者可以用反例来证明：素数这一条件必不可少。以加深对

11、它们的理解。|其中p Iab p I a或p I b也是常用的性质之一 |。也是证明算术根本定理的根底。算术根本定理是整数理论中最重要的定理之一，即任何整数一定能分解成一些素数的乘积，而且分解是唯一的，不是任何数集都能满足算术根本定理的，算术根本定理为我们提供 了解决其它问题的理论保障。它有许多应用，由算术根本定理我们可以得到自然数的标准分解问题设 a= P i 1 P k k ，b= p 1 1 p k k， i 0, i 0那么有(a，b)= p 11 . p kk i min( i, i)a，b= p 1 1 p k k i max( i,例如可求最大公约数，正整数正约数的个数等方面问题

12、，对具体的n,真正去分解是件不容易的事。对于较特殊的 n，例如|n!分解还是容易的。应用x的性质，n!的标准分解式可由一个具体的公式表示出来，这一公式结合x的性质又提供了解决带有乘除符号的整 除问题的方法。本章的许多问题都围绕着整除而展开，读者应对整除问题的解决方法作一简单的小结。五、例子选讲补充知识 最小自然数原理：自然数的任意非空子集中一定存在最小自然数。 抽屉原理：(1) 设n是一个自然数，有n个盒子，n+1个物体，把n+1个物体放进n个盒子，至少 有一个盒子放了两个或两个以上物体；(2) km+1个元素，分成k组，至少有一组元素其个数大于或等于m+1；(3) 无限个元素分成有限组，至少

13、有一组其元素个数为无限。 梅森数：形如pn-i |的数叫梅森数，记成 M=2n-i I。° n 费尔马数：n为非负整数，形如221的数叫费尔马数，记成Fn=221。 设n=Pi1Pkk，设n的正因子个数为d(n)，所有正因子之和为(n )，贝U有d(n) (i 1) ( 21).( k 1)1，k 1 a/ 、 P11 P21 Pk 1(n )-P11P21 Pk 1 有关技巧1. 整数表示 a=aoX 10n+a1X 10n-1+an，a=2kb(b为奇数)2. 整除的常用方法a. 用定义b. 对整数按被n除的余数分类讨论c. 连续n个整数的积一定是n的倍数d. 因式分解疋bn=(

14、a-b)M,an+bn=(a+b) M,2 * ne. 用数学归纳法f. 要证明a|b，只要证明对任意素数p, a中p的幕指数不超过b中p的幕指数即可,用p(a)表示a中p的幕指数，贝U a|b p(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=3k，显然 成立，a=3k+1 时，a+2=3(k+1) , a=3k+2 时，a+仁3(k+1)。例3.证明Ig2是无理数。证：假设Ig2是有理数，那

15、么存在二个正整数 p, q，使得Ig2= p，由对数定义可得10p=2q , q那么有2p 5p =2q,那么同一个数左边含因子5,右边不含因子5,与算术根本定理矛盾。Ig2为无理数。例 4.求(21 n+4, 14n+3)解：原式=(21 n+4,14 n+3)=(7 n+1,14 n+3)=(7 n+1,7 n+2)=(7 n+1,1)=1例5.求2004!末尾零的个数 解：因为10=2X 5,而2比5多，所以只要考虑2004!中5的幕指数，即5 (2004!) = 200452004252004200412554200455例 6.证明(n! ) (n-1)! |( n!)!证：对任意素

16、数p,设(n! ) (n-1)!中素数p的指数为(n! ) !中p的指数B，那么(n(n1)!k 1(nx ) n (x )n!k 1 pkn(n 1)!k 1 pkk1(n.n!orp(n1!k1n!即，即左边整除右边例 7.证明 2003| (20022002+20042004-2005) 证： 2002 2002= (2003-1 ) 2002=2OO3IU+1 2OO42004= (2003+1) 2002=2OO3M+1 2OO22OO2+2OO4"OO4-2OO5=2OO3 (M1+M2-1 ) 由定义 2003| (2002"002+20042004-2005

17、)例8.设d(n)为n的正因子的个数，(n)为n的所有正因子之和，求d(1000)，33解：1000=2 5(1000)。 d(1000)=(3+1)(3+1)=16 ，(1000)= 2 454例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) ,.alb例10.假设M为素数，那么n定为素数。证：假设n为合数，那么设n=ab，(1<a,b<n)2 ab-仁(2 ) b-1=(2 a-1)

18、 M为合数，与M为素数矛盾, n为素数。例 11.证明对任意 m,n，m# n,( Fn,F"=1。n 1 n 1 n 1证：不妨设 n>m 那么 Fn-2= ( 21 ) ( 221) =(Fn-i-2)( 221)设( Fn,F m) =d, 那么 d|Fn, d|Fm d|2 但Fn为奇数，d = 1,即证。例 12. 设 m,n 是正整数。证明(2m 1,2n 1)2(m,n)1证 : 不妨设 m n 。由带余数除法得mq1nr1 , 0 r1n.我们有2m 1 2q1n r1 2r12r1 12r1 (2q1n 1) 2r1 1由此与 2n 1| 2q1n1 得 ,

19、(2m1,2n 1)=(2n 1,2r1 1)注意到 (m,n ) (n,r1) , 假设 r10 , 那么 (m,n )n , 结论成立 . 假设 r1 0 , 那么继续对 (2n 1,2r1 1) 作同样的讨论，由辗转相除法知，结论成立。显见， 2 用任一大于 1 的自然 a 代替，结论都成立。例 13. 证明：对任意的正整数 n ，成立如下不等式 lg n k lg 2 。其中lgn是数n的以10为底的对数，k是n的不同的素因数(正的)的个数。证：设n是大于1的整数(如果n =1，上述不等式显然成立，因k=0)，卩仆卩?,，pk是n的k个 相异的素因素。 n 的素因数分解式为n p11p

20、22.pkk .( li ti U.-k),由于 Pi 2,(i 1,2., k)，从而n p1l1pl22.pklk 2l1 2l2 . 2lk 2l1 l2 . lk ，而 l1 l2 . lk k ，故 n 2 k 。将上述不等式取对数(设底a 1),那么有log a n kloga 2。特别有 lg n k lg 2 。例 14. 试证明任意一个整数与它的数字和的差必能被 9 整除，并且它与它的数字作任意调后 换后所成整数的差也能被 9 整除。证：设整数m的个位、十位、百位的数字分别为ai,a2，an，那么m可表作:n1m a110a 2100a 3.10 ann 1个(a1 a2 a

21、 3an ) (9a2 99a399. 9a n )n 1个(a1a 2 a 3an ) 9(a2 11a311. 1a n )所以 m (a1 a 2 a 3an)9(a211a3n 1个11. 1a n )因为a2 , a3,，an都是整数，所以任一整数与其数字之和的差必能被 9整除再设将 a1 , a2 ，an 按任一种顺序排成 a'1, a'2， a'n，并令a1 a2. aa'1 a'2 . a'n ，m a 110a 2101an ，m' a'1 10a'2 . 10n 1a'n 。根据前面证明的结果，

22、知存在整数 A，B,使m 9A,m'' 9B.因为 ' ，所以 m m ' 9A ' 9B 9(A B ) 。由于A-B是整数，这就证明了 m m'能被9整除。注：假设对某个整数k(1 k n)，有a'k 0，但当k i n时，a'i 0，那么此时m'为整数:m' a'1 10a'2 .10k 1 a'k ,即 m' a'k .a'2 a'1。如前证，此时结论正确。又当 m 为负整数与零时，结论显然正确? 第二章 不定方程、主要容x2+y2=z2 通解公式、无

23、穷一次不定方程有解的条件、解数、解法、通解表示，不定方程 递降法、费尔马大定理。、根本要求1、了解不定方程的概念，理解对“解的认识，掌握一次不定方程ax by c 有解的条件，能熟练求解一次不定方程的特解，正整数解与通解。了解多元一次不定方程a1x1 a2 x2anXn c有解的条件，在有解的条件下的解法2、掌握不定方程x2+y2=z2在一定条件下的通解公式，并运用这个通解公式作简单的应用。3、对费尔马大定理应有在常识性的了解，掌握无穷递降法求证不定方程x4+y4=z2无解的方法。4、掌握证明不定方程无解的假设干方法。、难点和重点1重点为求解一次不定方程的方法2掌握第二节中引证的应用。1费尔马

24、无穷递降法。四、自学指导不定方程主要讲解以下几个问题i 给定一类不定方程，判别在什么条件下有解。ii 在有解的条件下，有多少解iii 在有解的条件下，求出所给的不定方程的所有解。元一次不定方程的一般形式为 ax+by=c。假设a ,b I c，那么该二元一次不定方程一定有解,假设一个特解，那么一切解可以用公式表示出来，因此求它的通解只要求出一个特解即可。求解二元一次不定方程的一个通解有好多种方法。读者应该总结一下，各种方法都有独到之 处。特别要指出用最大公因数的方法。它的根据是求 a ,b 时所得的结果。由于注意通解 公式x=xo-bit，y=yo+ait中ai，bi的意义和位置。以免出错。多

25、元一次不定方程a1x1 a2x2anxn c也有类似的结果，但在求解的过程中将它转化二元一次不定方程组，从最后一个二元一次不定方程解起，可逐一解出X1,X2 ,Xn。所用的方法一般选择最大公因数的方法。 由于n元一次不定方程可转化为n-1个二元一次不定 方程组，故在通解中依赖于n-1个任意常数。但不象二元一次不定方程那样有公式来表示。x2+y2=z2的正整数解称为勾股数，在考虑这个方程时，我们对x ,y 作了一些限制，而这些限制并不影响其一般性。在条件x>0,y>0,z>0, (x,y)=1,2 I x的条件可以给出x2+y2=z2 的通解公式，x=2ab，y=a2-b2，z

26、2=a2+b2， a>b>0 , (a ,b)=1，a ,b 一奇一偶。假设将 2 I x 限为2 I y，那么也有相应的一个通解公式。在证明这个通解公式的过程中，用到了引理uv=w2,u>0, v>0, (u ,v ) =1,贝U u=a2, v=b2, w=ab。 a>0, b>0, (a ,b ) =1。利用这个结论可以 求解某些不定方程。特别当 w=1或素数p。那么由uv=1或uv=P可将原不定方程转化为不定方程组。从而获得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望读者能掌 握这种方法。为了解决著名的费尔马大定理：xn+yn=zn ,

27、n?3无正整数解时，当n=4时可以用较初等 的方法给出证明。证明由费尔马本人给出的，一般称为费尔马无穷递降法。其根本思想为由 一组解出发通过构造得出另一组解， 使得两组解之间有某种特定的关系， 而且这种构造可以 无限重复的。从而可得到矛盾。因此无穷递降法常用来证明某些不定方程无整数解。证明一类不定方程无解是研究不定方程邻域中常见的形式，一般的要求解不定方程比证明不定方程无解要容易些。证明不定方程无解的证明方法常采用以下形式：(反证法)假设A有解 Ai有解 A有解 A有解，而A本身无解，这样来构造矛盾。从而 说明原不定方程无解。对于证明不定方程的无解性通常在几种方法，一般是总的几种方法交替使用。

28、特别要求 掌握：简单同余法、因子分解法、不等式法，以与中学数学中所涉与的判别式法。五、例子选讲例1:利用整数别离系数法求得不定方程15x+10y+6z=61。解：注意到z的系数最小，把原方程化为11Z=( 15x10y61) 2x 2y 10( 3x 2y 1)66令 t 1= -( 3x 2y 1) z，即-3 x+2y-6 11 + 1=06此时 y 系数最小，y 1(3x6t1 1) x 3t1 -1(x 1)令t 2=严1) z ,即x 2t2 1,反推依次可解得y=x+3t 1+t 2=2t 2+1+3t 1+t 2=1+3t 1+3t 2z=-2x-2y+10+t1=6-5t 1+

29、10t2x12t2y13ti3t2 t it 2 Zz65ti10t2原不定方程解为例2:证明.2是无理数证：假设2是有理数，那么存在自数数a,b使得满足X2 2y2即a2 2b2，容易知道a是偶数, 设a=2ai，代入得b2 2a1 ,又得到b为偶数，ay b a，设b 2S，那么aj 2bf ,这里b? ay 这样可以进一步求得 a2，b2且有a>b>ai>bi> a2>b>但是自然数无穷递降是不可能的，于是产生了矛盾，,2为无理数。例3:证明：整数勾股形的勾股中至少一个是 3的倍数。证：设 N=3n± 1(m为整数)，代=9吊±6叶

30、 1=3(3mi±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=2ui, u- v=2vi 有2 2ui vi 82,u i vi 2u 2, ui vi 2v 2u2 v； 4i, u2,v2 为一偶一奇，且 0

31、<u2<6u2=i, 2, 3, 4, 5 代方程，有解(4, 5) (5, 4)原方程解 x=i8,y=2,或 x=2,y=18。例5:求x2+xy-6=0的正整数解。解：原方程等价于x(x+y)=2 3,故有即有 x=2,y=1;x=1,y=5. x2, x3, x1, x6,xy3, xy2, xy6, xy1. 例6:证明不定方程x2-2xy2+5z+3=0无整数解。解：假设不定方程有解，那么x y2.y4 5z 3但 y4=0, 1(mod5), 对 y,z, y4-5z-3 = 2, 3(mod5)而一个平方数三0, 1, 4 (mod 5) y4-5z-3不可能为完全

32、平方，即y4 5z 3不是整数，所以原不定方程无解。例7:证明：x2y2 z2 8a 7无整数解证：假设原方程有解，那么有x2 y2 z2 8a 7(mod 8)注意到对于模8,有02 0, 12 1,224,321,42 0,52 1, 62 4, 721,因而每一个整数对于模8,必同余于0, 1, 4这三个数。不管 x2, y2, z2 如何变化，只能有 x2 y2 z2 0,1,2,3,4,5,6(mod8)而8a 7 7(mod8)，故8a 7不同余于x2y2 z2关于模8，所以假设错误，即8a 7 x2 y2z2，从而证明了原方程无解。例8:某人到银行去兑换一 d元和c分的支票，出纳

33、员出错，给了他 c元和d元，此人直到 用去23分后才觉察其错误，此时他发现还有2d元和2c分，问该支票原为多少钱？解：由题意立式得：108 d 23 100 2d 2c即 98c199d23.令 u c 2d 得 98u 3d 23,令 v 33u d 得 3v u 23.所以u 3v 23(v为任意整数)，代入得：d33u v98v3323,( 1)cu 2d199v6723,其中V是任意整数。又根据题意要求：d 0,0 c 100 .根据，仅当V=8时满足此要求，从而d 25, c 51.因此该支票原为25元51分.AVV*第二早同余、主要容同余的定义、性质、剩余类和完全剩余系、欧拉函数、

34、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数 2, 3, 4，5, 6，7, 8, 9，11，13的整除规律二、根本要求通过本章的学习，能够掌握同余的定义和性质，区别符号：“三和=之间的差异。能利用同余的一些根本性质进行一些计算，深刻理解完全剩余系，简化剩余系的定义、性质与 构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的 值，掌握欧拉定理、费尔马小定理的容以与证明方法。能应用这二个定理证明有关的整除问 题和求余数问题。能进行循环小数与分数的互化。三、难点和重点(1) 同余的概念与根本性质(2) 完全剩余系和简化剩余系的构造、判别(3) 欧拉函数计算、欧

35、拉定理、费尔马小定理的证明与应用(4) 循环小数与分数的互化(5) 特殊数的整除规律。四、自学指导同余理论是初等数论中最核心的容之一，由同余定义可知，假设a= b(mod m),贝U a和b被m除后有一样的余数。这里 m为正整数，一般要求m大于1,称为模，|同余这一思想本质是将整数按模m分类，然后讨论每一个类中整数所具有的共性与不同类之间的差异。第同余还有二个等价的定义：用整除章中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例子。 从同余的定理上看，同余和整除实际上是同一回事，故来定义即m I a-b。用等号来定义a=b+mt。值得注意a和b关于m同余是个相对概念即它

36、是相对于模m来讲，二个整数a和b关于一个整数模m同余。那么对于另一个整数模 m， a和b未必会同余。从定义上看，同余和整除是同一个事情，但引进了新的符号“三后，无论从问题的叙 述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引 进了同余的代数性质和自身性质后，同余符号“三和等号“=相比，在形式上有几乎致的性质，这便于我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即 除法的消去律不成立。为此对于同余的除法运算我们有二种除法：(i )模不改变的除法，假设 ak = bk(mod m) ，(k,m)=1，贝U a= b(mod m)(ii)模改变的除法,

37、 假设 ak = bk(mod m) (k,m)=d,贝U a= b mod a这一点读者要特别注意。完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为 同余关系是一个等价关系，利用等价关系可以进行将全体整数进行分类，弄清来胧去脉，对 于更深刻理解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合， 在每个剩余类各取一个数组成的 m个不同数的集合，故一组完全剩余系包含 m个整数，由于 二个不同的剩余类中的数关于 m两两不同余，故可得判别一组数是否为模m的一个完全剩余 系的条件有二条为(1) 个数=m(2) 关于m两两不同余另外要能用完全剩余系构造新的完

38、全剩余系。即有定理设(a，m) =1，x为m的完全剩余系，那么ax+b也是m的完全剩余系当(g,m2)1时，能由 mi的完全剩余系和 m?的完全剩余系，构造 mim?完全剩余系。为讨论简化剩余系，需要引进欧拉函数© (m),欧拉函数© (n)定义为不超过m且与m互素的正整数的个数，记为© (m,要掌握© (m)的计算公式，了解它的性质。这些性质最主要1的是当(a ,b ) =1 时，© (ab) = © (a) © (b)，和(p ) p p现在在剩余类中把与 m互素的集合分出来，从中可在各个集合中任取一个数即可构造模 m的

39、一个简化剩余系。另一方面，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系，一组完全剩余系中与 m互素的的数组成的© (n)个不同数的集合称为 m简化剩余系。同 样简化剩余系也有一个判别条件。判别一组整数是否为模m的简化剩余系的条件为(2) 个数=© (m)(3) 关于m两两不同余(3) 每个数与m互素关于m的简化剩余系也能用完全剩余系构造新的简化剩余系。设(a, m) =1, x为m的简化剩余系，贝U ax也是m的简化剩余系。当(m, m2) 1时，能由g的简化剩余系和m2的简化剩余系，构造口!口2简化剩余系。欧拉定理、费尔马小定理是同余理论非常重要的定理之一。要注意

40、欧拉定理和费尔马定 理的条件和结论。欧拉定理：设 m为大于 1的整数，(a，m) =1，那么有a (m) 1(modm)费尔马小定理：假设p是素数，那么有就欧拉定理、费同余方法也是解ap a(mod p)除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用尔马小定理来讲，它在某些形如 an数的整除问题应用起来显得非常方便决整除问题的方法之一。另外同余方法在证明不定方程时也非常有用，即要掌握同余“三和相等“=的关系:相等必同余，同余未必相等，不同余肯定不相等。对于特殊数的整除规律要求能掌握其一般定理的证明，并 熟记一些特殊数的整除规律1、一个整数被2整除的充要条件是它的末位为偶数2、一个

41、整数被3整除的充要条件是它的各位数字之和能被3整除3、一个整数被9整除的充要条件是它的各位数字之和能被9整除4、一个整数被5整除的充要条件是它的末位为0或55、一个整数被4, 25整除的充要条件是它的末二位能被 4, 25整除6、一个整数被8, 125整除的充要条件是它的末三位能被 8, 125整除。7 设a an1000n k "000“ 1a。，那么7或11或13整除a的充要条件是7或 科假设1<i <p,那么有i | p那么与p为素数矛盾i=p,二 p|q-1又v q-1为偶数,2|q-1, 2 p| q-1, q-1= 2pk,即 q=2pk+1例 4:证明 13

42、|42n+1+3n+2证：42n+1+3n+J 4 16n+93nnn -三3 (4+9)三 13X3 三0(13) 13|4 2n+1+3n+2例5：证明5y+3=x2无解证明：假设5y+3=x2有解，那么两边关于模5同余有 5y+3=x2(mod 5)即 3=x2(mod 5)而任一个平方数 x = 0,1,4(mod 5) 30,1,4(mod 5)即得矛盾，即5y+3=x2无解例6:求111被7除的余数。50解:v 111111 被 7 整除, 11 1 = 11 (mod 7)= 4 (mod 7),即余数为 450例7:把0.042 63化为分数。解：设 b=0.042 63，从而

43、 1000b=42. 63,100000b=4263.63 , 99000b=4263-42._4221 _ 469b一=。9900011000当然也可用直化分数的方法做。例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)因为 0 X, Y 9，所以有 2121+X+Y 39，4X-Y+1322,由此可知21+X+Y=27 X-Y+13=11或 21+X+Y=36 X-Y+13=22X+Y=6 X-

44、Y=-2或 X+Y=15 X-Y=9,解得 X=2, Y=4例9:证明：8a+7不可能是三个整数的平方和。证：由于每一个整数对于 8,必同余于0 , 1 , 2 , 3 , 4 , 5 , 6 , 7这八个数之一 注意到对于模8,有020,121,224,321,420,521, 624, 721,因而每一个整数对于模8,必同余于0 , 1 , 4这三个数不能 x2,y2,z2如何变化，只能有 x2 y2 z2 0,1,2,3,4,5,6(mod8)而8a 7 7mod8),故8a 7不同余于x2 y2 z2关于模88a 7 x2 y2 z2 ,从而证明了结论。?第四章同余式、主要容同余方程概

45、念与次数、解的定义,一次同余方程ax= b(modm)有解的充分必要条件，一次同余方程组，子定理，高次同余方程，素数模的同余方程，威尔逊定理 二、根本要求通过本章的学习要求掌握同余方程的一些根本概念，例同余方程的次数、解等，能解一次 同余方程，一次同余方程组，理解子定理并用它来解一次同余方程组，会解高次同余方程， 对于以素数模的同余方程的一般理论知识能理解。三、重点和难点(1) 子定理的容与证明，从中学会求出一次同余方程组的解并从中引伸更一般的情形，即 模不二二互素的情形。(2) 素数模的同余方程的一些根本理论性问题，并能与一般方程所类似的性质作比拟。四、自学指导同余方程和不定方程一样，我们同

46、样要考虑以下三个问题，即|有解的条件，解数与如何求解，一般地说，对于一般的同余方程，由于仅有有限个解，只要把模m的一个完全剩余系一一代入验算总解组那么所需的结果。因此上述三个问题已根本解决，只不过具体到某一个 同余方程计算起来困难一点而异。但对于解数，传统的结果不再成立。例如一个同余方程的 解数可以大于其次数。读者可以举出反例来证明这一事实。要学好同余方程这一章。必须首先弄清同余方程的概念，特别是同余方程解的概念，互 | 一样余的解是同一个解。其次有使原同余方程和新的同余方程互相等价的假设干变换。 移项运 算是传统的，同余方程两边也可以加上模的假设干倍。相当于同余方程两边加“零 。|无论是乘上

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

48、同余方程组不是标准形式，必须注意化为标准形式，同时我们得到的有解的判别定理与求法方法都是这一标准形式得到的。同余方程组(1) 有解的条件(mi ,mj) I bi-bj，1w i , j w k。在使用时一定要对所有可解进行验算，进行有解的判别求解一次同余方程组(1)有两种方法：待定系数法和子定町。二种方法各有特长。待 定系数法适应的围较广，对模没有什么要求。子定理有一个具体的公式，形式也较漂亮。但 对模要二二互素。子定理为下面定理：(子定理)k 2,m1,m2,.,mk 两两互素，m mim2.mk ,m mjMj,i 1,2,.k 那么一次同余式组x b1 (mod m1), x b2(m

49、od m2),.x bk (mod mk)的解为x M1M M 2M 2b2.M kM kbk (modm),其中 MjM； 1(modm),i 1,2,.k.对待定系数法和子定理要有深刻的理解。体会其实质，这样不必死记硬背。次数大于1的同余方程称为高次同余方程，一般地高次同等方程可转化一系列的高次同 余方程组。然后将每一个高次同余方程的解都求出， 最后利用子定理也可求出原同余方程的 解。求高次同余方程解的根本方法有两条，一是小模，二是降次|。1k. -I-设|m= PP k | ;贝卩要求 f(x) 三0(mod m)的解只要求 f(x) 三0(mod p a )| (2)的解即可，其中p为

50、素数。a > 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 )的一个解。方法如下：将 x=xi+pti 代入 f(x)= O(mod p2)有f(x i+pt i) = O(mod p ) f(x i)+pt f ' (x i) = O(mod p)f xL+bflxJ = O(mod p)ti=ti' + p t 2p代入 x=x 1 +pt 1=xi +p(t 1 ' +t 2p)=X

51、 2+ p2t 2那么x = X2(mod p2)即为f(x) = O(mod p2)的解。然后重复上述过程，即可由X2得f(x) = O(mod p a )的解X 3。最后求出f(x) = O(mod p a )的解x从上所述，关键是求素数模的同余方程f(x) = O(mod p)的解。f(x) = O(mod p)的性质(1)同余方程的解与f(x)的分解之间的关系，这一点和代数方程几乎一样。注意素数p的条件必不可少。解数w次数。这一点和代数方程也一样。此时,(2)同余方程的解数与次数之间有关系素数p的条件也必不可少本节的辅产品是著名的wilsom定理P为素数，那么有(p-1) !三-1(m

52、od p),例1:解一次同余式17x19(mod25)解：(17, 25) =1，原同余方程有解，利用形式分数的性质,同余方程解为196 187x7(mod 25)178 241x 2(mod12)例2:解同余方程组 x 6(mod10)x 1(mod15)解：(12, 10) |6+2 , (12, 15) |-2-1 , (10, 15) |6-1-原同余方程有解，且等位于x2(mod 4)x2(mod3)x2(mod 4)x6(mod2)x1 (mod 3)此时变成模两两互素x6(mod5)x1(mod 5)x1(mod3)x(mod5)由子定理可求得其解为：x 46(mod 60)例3

53、:解一次同余式组51x 57(mod 75)3x 1(mod4)解：用常规方法先求每一个一次同余式的解，得到以下一次同余式组x 7,32,57(mod75)x 3(mod 4)然后用子定理求解，所以同余方程组有3个解，且解分别为x 7(mod 300) , x 107 (mod 300) , x 207(mod 300)例 4:设 2p+1 是素数，那么(P!)2( 1)P 0(mod 2p 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 -

54、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) J 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)?第五章二次剩余理论、

55、主要容平方剩余与平方非剩余的概念、欧拉判别条件、勒让德符号、二次互反律、雅可比符号、 素数模同余方程的解法根本要求通过本章的学习，掌握平方剩余与平方非剩余的概念，掌握勒让德符号的定义、性质计算 与利用它来判别一个二次同余方程是否有解，对于几个较特殊的勒让德符号的值， 要求能掌握它的推导方法。了解推可比符号的定义，性质与功能，会解素数的模的二次同余方程。与 证明一些二次不定方程无解中的应用。三、重点和难点(1) 欧拉判别定理：即a为p的平方剩余的条件。(2) 勒让德符号，二次互反律。(3) 素数模同余方程的解法。四、自学指导对于一般的高次同余方程的求解归纳为模为 p"的情形。对于同余方程f(x) = O(mod p") 的求解依赖于f(x) = o(mod p)的解。而且对于一般的f(x)，求解f(x) = O(mod p)的解是很 困难的。本章讨论f(x)为一个整系数的二次三项式