《初等数论总复习题及知识点总结.docx》由会员分享，可在线阅读，更多相关《初等数论总复习题及知识点总结.docx（56页珍藏版）》请在三一文库上搜索。
1、初等数论学习总结本课程只介绍初等数论的的基本内容。由于初等数论的基本知识和技巧与中学数学有着密切的关系，因此初等数论对于中学的数学教师和数学系（特别是师范院校）的本科生来说，是一门有着重要 意义的课程，在可能情况下学习数论的一些基础内容是有益的.一 方面通过这些内容可加深对数的性质的了解，更深入地理解某些他 邻近学科，另一方面，也许更重要的是可以加强他们的数学训练， 这些训练在很多方面都是有益的.正因为如此，许多高等院校，特 别是高等师范院校，都开设了数论课程。最后，给大家提一点数论的学习方法，即一定不能忽略习题的作用，通过做习题来理解数论的方法和技巧，华罗庚教授曾经说过 如果学习数论时只注意
2、到它的内容而忽略习题的作用，则相当于只身来到宝库而空手返回而异。数论有丰富的知识和悠久的历史，作为数论的学习者，应该懂得一点数论的常识，为此在辅导材料的最后给大家介绍数论中著名的 “哥 德巴赫猜想”和费马大定理的阅读材料。初等数论自学安排第一章：整数的可除性（6学时）自学18学时整除的定义、带余数除法最大公因数和辗转相除法整除的进一步性质和最小公倍数素数、算术基本定理X和X的性质及其在数论中的应用习题要求 P3 : 2, 3 ； P8 : 4 ； P12 : 1； P17 : 1 , 2 , 5； P20 : 1。第二章：不定方程（4学时）自学12学时二元一次不定方程 ax by =c多元一次
3、不定方程 a + a2x2 + anxn = c勾股数费尔马大定理。习题要求 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,则有 a I mb+nc读者要熟练掌握并能灵活应用。特别要注意，数论的研究对象是 整数集合，比小学数学中非负整数集合要大。本章中最重要的定理之一为带余除法定理，即为设a是整数，b是非零整数，则存在两个整数q，r，使得a=bq+r（0兰啊）它可以重作是整除的推广。同时也可以用带余除法定理来定义整除性，（即当余
7、数r=0时）。带余除法可以将全体整数进行分类，从而 可将无限的问题转化为有限的问题|。这是一种很重要的思想方法，它为我们解决整除问题提供了又一条常用的方法。同时也为我们建立同余理论建立了基础。读者应熟知常用的分类方法，例如把整数可分成 奇数和偶数，特别对素数的分类方法。例全体奇素数可以分成4k+1，4k+3 ;或 6k+1，6k+5 等类型。和整除性一样，二个数的最大公约数实质上也是用等号来定义 的，因此在解决此类问题时若有必要可化为等式问题，最大公因数的 性质中最重要的性质之一为a=bq+c，贝U定有（a，b） = （b，c），就是求二个整数的最大公约数的理论根据。|也是解决关于最大公约数
8、问题的常用方法之一。读者应有尽有认真体会该定理的证明过程。互素与两两互素是二个不同的概念，既有联系，又有区别。要认 真体会这些相关的性质，例如，对于任a ,b Z, 可 （ a ,b ） =d,则 a=dai ,b=db 1,贝廿(ai ,b 1) =1，于是可对 ai ,b 1使用相应的定理， 要注意，相关定理及推论中互素的条件是经常出现的。读者必须注意 定理成立的条件，也可以例举反例来进行说明以加深影响。顺便指出，若a I c, bl c, (a ,b ) =1,贝y ab I c |是我们解决当除数为合数时的 一种方法。好处是不言而喻的。最小公倍数实际上与最大公因数为对偶命题。特别要指出
9、的是a和b的公倍数是有无穷多个。所以一般地在无穷多个数中寻找一个最 小数是很困难的，为此在定义中所有公倍数中的最小的正整数。这一 点实际上是应用自然数的最小自然数原理，即自然数的任何一个子集一定有一个最小自然数有在。最小公倍数的问题一般都可以通过以下式子转化为最大公因数的问题。两者的关系为a ,b N, a ,b=黑(a,b )上述仅对二个正整数时成立。当个数大于2时，上述式子不再成立。证明这一式子的关键是寻找a , b的所有公倍数的形式，然后从中找一个最小的正整数。解决了两个数的最小公倍数与最大公因数问题后，就可以求出个数的最小公倍数与最大公因数问题，可以两个两个地求。即有下面 定理设 ai
10、, a2, an 疋 n 丨 整 数 , (ai，a2)=d2，(d2,a3)=d3, (dnj,an) = dn,贝 V(ai , a2 , a n )= d n ,设ai，a2 =m2, (m2,a3)=口3,(mn4,an)二 m.,贝V有aia?,an= m.素数是数论研究的核心，许多中外闻名的题目都与素数有关。除1外任何正整数不是质数即为合数。判断一个已知的正整数是否为质 数可用判别定理去实现。 判别定理又是证明素数无穷的关键。实际上，对于任何正整数n1,由判别定理一定知存在素数 p,使得p I n。即 任何大于1的整数一定存在一个素因数 p。素数有几个属于内在本身 的性质，这些性质
11、是在独有的，读者可以用反例来证明：素数这一条件必不可少。以加深对它们的理解。其中p I ab= p I a或p I b也是常用的性质之一。也是证明算术基本定理的基础。算术基本定理是整数理论中最重要的定理之一，即任何整数一定能分解成一些素数的乘积，而且分解是唯一的，不是任何数集都能满 足算术基本定理的，算术基本定理为我们提供了解决其它问题的理论 保障。它有许多应用，由算术基本定理我们可以得到自然数的标准分 解问题C设 a= p f1 p ,k , b= p F p fk , % A。,”则有(a, b)=Pi1 p k kmi 门何卫)莎，b= p F p=max(%,Pj例如可求最大公约数，正
12、整数正约数的个数等方面问题，对具体 的n,真正去分解是件不容易的事。对于较特殊的n,例如|n!分解还是容易的。应用x的性质，n!的标准分解式可由一个具体的公式表 示出来,这一公式结合x的性质又提供了解决带有乘除符号的整除 问题的方法。本章的许多问题都围绕着整除而展开，读者应对整除问题的解决方法作一简单的小结五、例子选讲补充知识 最小自然数原理：自然数的任意非空子集中一定存在最小自然数。 抽屉原理：（1）设n是一个自然数，有 n个盒子，n+1个物体，把n+1个物体 放进n个盒子，至少有一个盒子放了两个或两个以上物体；（2）km+1个元素，分成k组，至少有一组元素其个数大于或等于 m+1;（3）无
13、限个元素分成有限组，至少有一组其元素个数为无限。 梅森数：形如2-2的数叫梅森数，记成 M=2n-i。 费尔马数：n为非负整数，形如22 +1 |的数叫费尔马数，记成Fn=22 + 1。 设n=P11. p；k，设n的正因子个数为d（n），所有正因子之和为 二（n）， 则有d（n） =（：11） （： 21）-（ : k 1）；（n）二P22 1-1Pk -1P1 -1P2 -1 有关技巧1. 整数表示 a=ax 1Qn+a1X 10n-1+ana=2kb（b为奇数）2. 整除的常用方法a. 用定义b. 对整数按被n除的余数分类讨论c. 连续n个整数的积一定是 n的倍数d. 因式分解an-bn
14、=(a-b)M 1, an+bn=(a+b)M2, 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+1= 3(k+1)。例3.证明lg2是无理数。证：
15、假设Ig2是有理数，则存在二个正整数p, q,使得Ig2二卫，由q对数定义可得10p=2q，则有2卩5 p =2 q,则同一个数左边含因子5,右边不含因子5,与算术基本定理矛盾。 Ig2为无理数例 4.求(21n+4 , 14n+3)解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1例5.求2004!末尾零的个数。解：因为10=2X 5,而2比5多，所以只要考虑2004 !中5的幕指数，即5 (2004!)=包1)+色巴1+愆)+1磚)+色1=499I 5八25丿25丿匕4八55丿例 6.证明(n!) (n-1)! |(n!)!证：对任
16、意素数p,设(n! ) (n-1)!中素数p的指数为:,(n! ) !中p的指数B,则匕=(n -1)! k T- (nx ) _ n(x):=(n -1)! Jk =1-；：(n -1)! k 1即 -:,即左边整除右边 例 7.证明 2003| (200222+20042004-2005 )证：2002 2002= (2003-1 ) 2002=2OO3M+120042004= (2003+1) 2002=2003M+1 20022002+2004204-2005=2003 ( M+M-1 ) 由定义 2003| (20022002+20042004-2005 )例8.设d(n)为n的正因
17、子的个数，-(n)为n的所有正因子之和，求 d(1000),二(1000)。,二(1000)=解： 1000=2 3 53 d(1000)=(3+1)(3+1)=16例9.设c不能被素数平方整除，若a2|b2c,则a|b证：由已知 p(c) 1,且 p(a2) p(b 2c) 2p(a) 2p(b)+p(c) , p(a) p(b)+ 罟即 p(a) p(b) , a|b例10.若M为素数，则n 定为素数。证：若n为合数，则设n=ab, (1a,bm 贝 U Fn-2= ( 22-1 ) ( 221 ) =(Fn-1 -2)( 2一1 )=F n-1 Fn-2F m- F 0设(Fn,Fm)
18、=d,则 d|Fn, d|F gd|2但Fn为奇数， d=1,即证。例12.设m,n是正整数。证明(2m -1,2n -1) = 2(m,n) -1证：不妨设m _n。由带余数除法得m =q1n 亠r 力0Mn .我们有2m -1=2q们 门一2门：；2门1 = 2ri(2q们-1)，2门-1由此及 2n - 1| 2q1n -1得,(2m -1,2n -1) = (2n -1,2r1 -1)注意到（m,n） MnrJ ,若=0 ,则（m,n） =n ,结论成立.若0，则继续对 （2n -1,2r1 -1）作同样的讨论，由辗转相除法知，结论成立。显见， 2用 任一大于1的自然a代替，结论都成立
19、。例13.证明：对任意的正整数 n，成立如下不等式lgn _klg2。其中lgn是数n的以10为底的对数，k是n的不同的素因数（正的） 的个数。证：设n是大于1的整数（如果n=1，上述不等式显然成立，因k=0），P1.,P2，Pk是n的k个相异的素因素。n的素因数分解式为n = p11p22.pkk .（ h “i=1,2K）, 由于 pP2,（ =1,2,k），从而n 二 p11p22.pkk -211 2l2 . 2lk =2 i，而 l1 2 . lk _k，故 n _ 2将上述不等式取对数(设底 a .1 ),则有loga n_kloga2 特别有lgn _k Ig 2。例14.试证明
20、任意一个整数与它的数字和的差必能被9整除，并且它与它的数字作任意调后换后所成整数的差也能被9整除证：设整数m的个位、十位、百位的数字分别为a1 , a2，an ,则m可表作:n 1m =日1 TCB2亠100日3亠亠10 a n=(a i - a2 - a3 a) -(9a 2 99a3 -99. 9a 门)n丄个=(ai - a2 日3. an ) 一92 _11日3 -11. 1an )所以 m (a 1 +a 2 +a-. ._an) =9(a2 11a3 -11. 1an)因为 a2 , a3,-an都是整数，所以任一整数与其数字之和的差必能被9整除。再设将a 1, a 2 ,an按任
21、一种顺序排成a1 , a2 ,an，并令；:-a 1亠a2亠亠an；=a a2 . an , m =a 110a.-10nAan ,m =a 10a2 .10n ran。根据前面证明的结果，知存在整数A,B,使 m _;丁 =9A,m= 9B.因为-二，所以 m -m =cr +9A 疔-9B =9(A B )。由于A-B是整数，这就证明了 m -m能被9整除。注：若对某个整数k(k 0 ,(x ,y )作了一些限制，而这些限制并不影响其一般性。在条件y0,z0,(x,y)=1,2 I x的条件可以给出 x2+y2=z2的通解公式，x=2ab, y=a2-b2, z2=a2+b2, ab0 ,
22、 (a ,b)=1, a ,b 一奇一偶。若将 2 I x 限为2 I y，则也有相应的一个通解公式。在证明这个通解公式的过程中，用到了引理 uv=w2， u0， v0， (u ,v ) =1，贝u=a2，v=b2，w=ab。 a0，b0, (a ,b ) =1。利用这个结论可以求解某些不定方程。特别 当w=1或素数p。则由uv=1或uv=P可将原不定方程转化为不定方 程组。从而获得一些不定方程的解。上述解不定方程的方法叫 因子分解希望读者能掌握这种方法。为了解决著名的费尔马大定理：xn+yn=zn , n3无正整数解时，当n=4时可以用较初等的方法给出证明。证明由费尔马本人给出的， 一般称为
23、费尔马无穷递降法。其基本思想为由一组解出发通过构造得出另一组解，使得两组解之间有某种特定的关系，而且这种构造可以 无限重复的。从而可得到矛盾。因此无穷递降法常用来证明某些不定 方程无整数解。证明一类不定方程无解是研究不定方程邻域中常见的形式，一般的要求解不定方程比证明不定方程无解要容易些。证明不定方程无解的证明方法常采用以下形式：(反证法)若A有解=Ai有解=A有解-=A有解，而An本身无解，这 样来构造矛盾。从而说明原不定方程无解。对于证明不定方程的无解性通常在几种方法，一般是总的几种方法交替使用。特别要求 掌握：简单同余法、因子分解法、不等式法，以及中学数学中所涉及的判别式法O五、例子选讲
24、例1利用整数分离系数法求得不定方程15x+10y+6z=61解：注意到z的系数最小，把原方程化为11Z=_(5x -10y 61)- -2x -2y 10 C 2y U-1)66令二：2y 1 z，即-3x+2y-6t 1+1=0此时 y 系数最小，.y J(3x 亠-6t1 -1)=x - 3t! - -(x -1)2 2令t 2 = 1(x _1b z ,即x =2t2 -1,反推依次可解得y=x+3t 1+t 2=2t 2+1+3t 1+t 2=1+3t 计 3t 2z=-2x-2y+10+t 1 =6-5t 1+10t 24x =1 - 2t2原不定方程解为yJz 二6 - 5t1 -
25、10t 2例2:证明2是无理数证：假设、2是有理数，则存在自数数a,b使得满足 云即a2b2，容 易知道a是偶数，设a=2a，代入得b2二骞，又得到b为偶数，a 1:b ：a , 设 b =2b1，贝卩 a 1 =2b1 ,丄这里 b2 : a1这样可以进一步求得 a2, b2且有aba1b1 a2b2但是自然数无穷递降是不可能的，于是产生了矛盾， .2为无理数。例3:证明：整数勾股形的勾股中至少一个是3的倍数证：设 N=3m 1(m 为整数),/代=9吊土 6m+1=3(3nn 2m)+1即一个整数若不是3的倍数，则其平方为3k+1,或者说3k+2不可能 是平方数，设x,y为勾股整数，且 x
26、,y都不是3的倍数，则x2,y 2 都是3k+1,但z2=x2+y2=3k+2形，这是不可能，二勾股数中至少有一 个是3的倍数。例4： 求図x2+y2=328的正整数解解： 328为偶数， x,y奇偶性相同，即x y为偶数，设x+y=2u,x-y=2v，代入原方程即为u +v =164,同理令 u+v=2ui,u-v=2v 1 有2 2u 1 w =82,u ! f =2u2 ,u ! -v, =2v 2u 2 v:2 =41, u 2, v2 为 偶 奇，且 0u22，则2P-1的质因数一定是2pk+1形。证：设q是2p-1的质因数，由于2卩-1为奇数， q工2,(2 q) =1,由条件 q
27、|2p-1,即 2p 三 1 ( mod q),又t (q,2 )=1, 2p = 1 ( mod q)设i是使得2x = 1 ( mod p)成立最小正整数若1ip，则有i|p则与p为素数矛盾 i=P, - p|q-1又 q-1 为偶数，2|q-1, 2p|q-1,q-仁2pk , 即 q=2pk+1例 4:证明 13|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
28、5)而任一个平方数 x2= 0,1,4(mod 5) 3 三0,1,4(mod 5)即得矛盾，即5y+3=x2无解例6:求 被7除的余数。50解： 111111 被 7 整除， = 11 (mod7)= 4 ( mod7),即余数50为4。例7：把0.04263化为分数。解：设 b= 0.04263，从而 1000b= 42.63,100000b=4263.6 3, 99000b=4263-42 b= 4221 = 469= 99000 - 11000当然也可用直化分数的方法做例8设一个数为62XY427是9, 11的倍数，求X, 丫解：因为9Q2XY427所以 9Q+2+X+Y+4+2+7，
29、即 9|21+X+Y又因为 11|62XY427， 有 11 |( 7+4+X+6-2-Y-2)即 11| ( X-丫+13)因为0乞X，丫空9，所以有2仁21+X+Y空39，4 X-丫+13 22，由此可知21+X+Y=27, X-丫+13=11或 21+X+Y=36, X-丫+13=22X+Y=6, X-Y=-2或 X+Y=15? X-Y=9，解得 X=2，丫=4。例9:证明：8a+7不可能是三个整数的平方和。证：由于每一个整数对于8,必同余于0，1，2, 3, 4，5，6，7这八个数之一注意到对于模8,有02 三 0, 12 三 1, 22 三 4, 32 三 1,42 三 0, 52 三 1, 62 三 4, 72 三 1,因而每一个整数对于模8,必同余于0, 1, 4这三个数不能 x2,y2,z2如何变化，只能有 x2 y2 z2 = 0,1,2,3,4,5,6(mod 8) 而8a 1=1 mod 8)，故8a 7不同余于x2 y2 z2关于模8 8a 7