初等数论第一章整除理论

第一章 整除理论整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。第一节 数的整除性定义1设，b是整数，b0，如果存a在整数c，使得a= bc成立，则称 a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号 b a；如果不存在整数 c使得a=bc成立，则称

a

不被b整除，记为

b|

a。显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。被2整除的整数称为偶数，不被2整除的整数称为奇数。定理1下面的结论成立：(ⅰ)abab；(ⅱ)ab，bcac；(ⅲ)bi，i=1,2,,kb11aaxa2x2akxk，此处xi（i=1,2,,k）是任意的整数；(ⅳ)babcac，此处c是任意的非零整数；(ⅴ)ba，a0|b||a|；ba且|a|<|b|a=0。证明留作习题。定义2若整数a0，1，并且只有约数1和，则称a是素数（或质数）；否则a称a为合数。以后在本书中若无特别说明，素数总是指正素数。定理2任何大于1的整数a都至少有一个素约数。证明若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d,d,,d。不妨设d112k是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。推论任何大于1的合数a必有一个不超过的素约数。证明使用定理2中的记号，有a=d1d2，其中d1>1是最小的素约数，所以d12a。证毕。例1设r是正奇数，证明：对任意的正整数n，有n 2|1r 2r nr。解对于任意的正整数a，b以及正奇数k，有akbk=(ab)(ak1ak2bak3b2bk1)=(ab)q，其中q是整数。记s=1r2rnr，则2s=2(2rnr)(3r(n1)r)(r2r)=2(n2)，nQ其中Q是整数。若n2s，由上式知n22，因为n2>2，这是不可能的，所以n2|s。例2设A={1,2,,d}是n的所k有约数的集合，则B={n,n,,n}d1d2dk也是n的所有约数的集合。解由以下三点理由可以证得结论：(ⅰ)A和B的元素个数相同；(ⅱ)若diA，即din，则n|n，反之di亦然；(ⅲ)若didj，则nn。didj例3以d(n)表示n的正约数的个数，例如：(1)=1，(2)=2，(3)=2，(4)=3，。dddd问：(1)d(2)d(1997)d是否为偶数解 对于

n的每个约数

d，都有

n=d

n

，d因此，n的正约数d与n是成对地出现的。 只有d当d=n，即n=d2时，d和n才是同一个数。dnd()是奇数。故当且仅当是完全平方数时，dn因为442<1997<452，所以在d(1),d(2),,d(1997)中恰有44个奇数，故(1)(2)ddd(1997)是偶数。例4设凸2n边形的顶点是1,2,,MAAA2n，点O在M的内部，用1,2,,2n将M的2n条边分别编号，又将12,2nOA,OA,OA也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2,OA2A3,,OA2A1的周长都相等。n解假设这些三角形的周长都相等，记为s。则2ns=3(122n)=3n(2n1)，即2s=3(2n1)，因此23(2n1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。例5设整数k1，证明：kn<2k1，1an，a(ⅰ)若22k，则2k|a；(ⅱ)若3k2n1<3k+1，1bn，2b13k，则3k|2b1。解(ⅰ)若k|a，则存在整数q，使得a=2kkq2。显然q只可能是0或1。此时a=0或2，这都是不可能的，所以2k|a；(ⅱ)若3k|2b-1，则存在整数q，使得2b-13k，显然q只可能是0，1,或2。此时=q2b-1=0，3k，或23k，这都是不可能的，所以k。3|2b1例6写出不超过100的所有的素数。解将不超过100的正整数排列如下：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677a，使得78798081 82 83 84 85 86 8788899091 92 93 94 95 96 979899100按以下步骤进行：(ⅰ) 删去1，剩下的后面的第一个数是 2，是素数；(ⅱ)删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；(ⅲ)再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；(ⅳ)再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数；照以上步骤可以依次得到素数2,3,5,7,11,。由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。在例6中所使用的寻找素数的方法，称为Eratosthenes 筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。例7 证明：存在无穷多个正整数n4 a（n=1,2,3, ）都是合数。解取a=4k4，对于任意的nN，有n44k4=(n22k2)24n2k2=(n22k22nk)(n22k22nk)。因为n22k22nk=(nk)2k2k2，所以，对于任意的k=2,3,以及任意的nN，n4设a是合数。n是整数，且例8a1,2,,aaa1a2an=0，a1a2an=n，则4n。解如果2|n，则n,a,a,,a都是12n奇数。于是a1a2an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在a1,a2,,an中至少有一个偶数。如果只有一个偶数，不妨设为a，那么2|a（2i1in）。此时有等式a2an=a1，在上式中，左端是(n1)个奇数之和，右端是偶数，这是不可能的，因此，在1,2,,an中至少有两个偶数，即4n。例9若n是奇数，则8n21。解设n=2k1，则n21=(2k1)21=4k(k1)。在k和k1中有一个是偶数，所以8n21。例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题：问题d(1)2d(2)2d(1997)2被4除的余数是多少例10 证明：方程222=1999a1a2a3(1)无整数解。解若a1，a2，a3都是奇数，则存在整数A1，A2，A3，使得a2=8A1，a2=8A1，a2=8A1，231123于是a1222=8(A1A2A3)3。a2a3由于1999被8除的余数是7，所以a1，a2，a3不可能都是奇数。由式(1)，1，2，3中只能有一个奇数，设aaaa1为奇数，a2，a3为偶数，则存在整数A1，A2，A，使得3a12=8A12=8A22=8A3s，1，a2r，a3于是a1222A2A3)1ra2a3=8(A1s，其中r和s是整数，而且只能取值0或4。这样a12221或5，a2a3被8除的余数只可能是但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。综上证得所需要的结论。习题一证明定理1。证明：若mpmnpq，则mpmq。np3.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。设p是n的最小素约数，n=pn1，n1>1，证明：若 p>3n，则n1是素数。证明：存在无穷多个自然数n，使得n不能表示为2a p（a>0是整数，p为素数）第二节 带余数除法在本节中，我们要介绍带余数除法及其简单应用。定理1(带余数除法)设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得a=bqr，0r<||。b(1)证明存在性若ba，a=，Z，bqq可取r=0。若b|a，考虑集合A={akb；kZ},其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。在集合A中有无限多个正整数， 设最小的正整数是r=a0，则必有kb0<r<|b|，(2)否则就有r|b|。因为b|a，所以r|b|。于是r>|b|，即ak0b>|b|，ak0b|b|>0，这样，在集合A中，又有正整数ak0b|b|<r，这与r的最小性矛盾。所以式(2)必定成立。取q=k0知式(1)成立。存在性得证。唯一性假设有两对整数q，r与q，r都使得式(1)成立，即a=qbr=qbr，0r,r<|b|，则(qq)b=rr，|rr|<|b|，(3)因此rr=0，r=r，再由式(3)得出q=q，唯一性得证。证毕。定义1称式(1)中的q是a被b除的商，r是a被b除的余数。由定理1可知，对于给定的整数，可以按b照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。以后在本书中，除特别声明外，在谈到带余数除法时总是假定b是正整数。例1设a，，，y是整数，k和是正整bxm数，并且a=1r1，0r1<，ammb=1r2，0r2<，bmm则axby和ab被m除的余数分别与r1xr2y和r1r2被m除的余数相同。特别地，ak与r1k被m除的余数相同。解由axby=(a1mr1)xr(b1mr2)y=(a1xby)mxry112可知，若12被除的余数是r，即rxrymr1xr2y=qmr，0r<m，则axby=(a1xb1yq)mr，0r<，m即axby被m除的余数也是r。同样方法可以证明其余结论。例2设a1,a2,,an为不全为零的整数，以y0表示集合A={y；y=a1x1ax，xiZ，1nnin}中的最小正数，则对于任何y，0y；特别Ay地，y0ai，1in。解设y0=11ax，对任nn意的y=a1x1anxnA，由定理1，存在,r0Z，使得qy=qy0r0，0r0<y0。因此qy=a(xqx)a(xr=yn00111nqxn)A。如果r00，那么，因为0<r0<0，所y以r0是A中比y0还小的正数，这与y0的定义矛盾。所以r0=0，即y0y。显然a（1），所以y0整除每i个ai（1in）。例3任意给出的五个整数中，必有三个数之和被3整除。解设这五个数是ai，i=1,2,3,4,5，记rr<3，i=1,2,3,4,a=3qi，0iii5。分别考虑以下两种情形：(ⅰ)若在r1,r2,,r5中数0，1，2都出现，不妨设r1=0，r2=1，r3=2，此时12a3=3(1q2q3)3aaq可以被3整除；(ⅱ)若在r1,r2,,r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1=r2=r3=r（r=0，1或2），此时a1a2a3=3(q1q2q3)3r可以被3整除。Z，f(x)=anxn例4设a0,a1,,an1a0，已知f(0)与f(1)都不是3的ax倍数，证明：若方程f(x)=0有整数解，则n3(1)=(1)。fa0a12an解对任何整数x，都有x=3qr，r=0，1或2，qZ。(ⅰ)若r=0，即x=3q，qZ，则f(x)=f(3q)=an(3q)na1(3q)a0=310=31f(0)，QaQ其中Q1Z，由于f(0)不是3的倍数，所以f(x)；(ⅱ)若r=1，即x=3q1，qZ，则nf(x)=f(3q1)=a(3q1)na1(3q1)a0aa=3Qa102n=3Q2f(1)，其中QZ。由于f(1)不是3的倍数，所以f(x)20。因此若f(x)=0有整数解x，则必是x=3q2=3q1，qZ，于是0=f(x)=f(3q1)=an(3q1)na1(3q1)a01)nan=3Q3a0a1a2(=3Qf(1)，3其中Q3Z。所以3f(1)=a0a1a2(nn1)a。n，f(n)=3n5例5证明：对于任意的整数5n37n被15整除。解对于任意的正整数n，记n=15qr，0r<15。由例1，n2=15Q1r1，n4=15Q2r2，其中r1与r2分别是r2与r4被15除的余数。以R表示3n45n27被15除的余数，则R就是3r25r17被15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R。当r=0时，显然R=0，即15355n3n7n。对于r=1,2,3,,14的情形，通过计算列出下表：r=1,142,133,124,115,106,97,8r1=14911064r2=11611061R=0010012100R=0000000这证明了结论。例6设n是奇数，则16n44n211。解我们有n44n211=(n21)(n25)16。由第一节例题9，有8n21，由此及2n25得到16(n21)(n25)。例7证明：若a被9除的余数是3，4，5或6，则方程x3y3=a没有整数解。解对任意的整数x，y，记x=3q1r1，y=32r2，0r1,r2<3。q则存在Q1,R1,Q2,R2Z，使得x3=9Q1R1，y3=9Q2R2，其中R和R被9除的余数分别与r3和r312被912除的余数相同，即1=0，1或8，2=0，1或8。(4)RR因此x3y3=9(12)12。QQRR又由式(4)可知，R1 R2被9除的余数只可能是3 30，1，2，7或8，所以，x y不可能等于 a。习题二1.证明：12n42n311n210n，nZ。设3a2b2，证明：32.a且3b。3.设n，k是正整数，证明：kk+4的n与n个位数字相同。4.证明：对于任何整数，，等式222nmn(n1)=2不可能成立。m5.设a是自然数，问a43a29是素数还是合数证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被

n

整除。答案第三节 最大公约数定义1整数a1,a2,,ak的公共约数称为1,2,,a的公约数。不全为零的整数1,ka2,,ak的公约数中最大的一个叫做a1,a2,,a的最大公约数（或最大公因数），记为(1,2,kak)。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果(a1,a2,,ak)=1，则称a1,a2,,a是互素的（或互质的）；如果k(ai,aj)=1，1i,jk，ij，则称a,a,,a是两两互素的（或两两互质12k的）。a两两互素可以推出(a,显然，a,a,,12k12,,ak)=1，反之则不然，例如(2,6,15)a=1，但(2,6)=2。定理1下面的等式成立：(ⅰ)(a1,a2,,ak)=(|a1|,|a2|,,|ak|)；(ⅱ)(a,1)=1，(a,0)=|a|，(a,a)=|a|；(ⅲ)(a,b)=(b,a)；(ⅳ)若p是素数，a是整数，则(p,a)=1或pa；(ⅴ)若a=bqr，则(a,b)=(b,r)。证明(ⅰ)(ⅳ)留作习题。(ⅴ)由第一节定理1可知，如果da，db，则有dr=a，反之，若d，bqbdr，则da=bqr。因此a与b的全体公约数的集合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相等，即(a,b)=(b,r)。证毕。a,,a)时，由定理1可知，在讨论(a,12n不妨假设a1,a2,,an是正整数，以后我们就维持这一假设。定理2设a1,a2,,akZ，记A={y；y=kaixi，xZ，ik}。ii1如果y0是集合A中最小的正数，则y0=(a1,a2,k,a)。设d是a1,a2,a的一个公约数，证明,则dy，所以dky。另一方面，由第二节例002知，y0也是a1,a2,,k的公约数。因此y0a是a1,a2,,ak的公约数中的最大者，即y0=(a1,a2,,ak)。证毕。推论1设d是a1,a2,,ak的一个公约数，则d(a1,a2,,ak)。这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。推论212k12(ma,ma,,ma)=|m|(a,a,k,a)。推论3记=(a1,a2,,ak)，则(a1,a2, ,ak)=1，特别地,(a,b)=1。(a,b)(a,b)定理3(a1,a2,,ak)=1的充要条件是存在整数x,x,,x，使得12ka1x1a2x2akxk=1。(1)证明必要性由定理2得到。充分性若式(1)成立，如果(1,2,,a)=kd>1，那么由da（1ik）推出11ia2x2a,akxk=1，这是不可能的。所以有(a,,a)=1。证毕。12k定理4对于任意的整数a，b，c，下面的结论成立：(ⅰ)由bac及(a,b)=1可以推出bc；(ⅱ)由bc，ac及(a,b)=1可以推出abc。证明(ⅰ)若(a,b)=1，由定理2，存在整数x与y，使得axby=1。因此acxbcy=c。(2)由上式及bac得到bc。结论(ⅰ)得证；(ⅱ)若(a,b)=1，则存在整数x，y使得式(2)成立。由bc与ac得到abac，abbc，再由式(2)得到abc。结论(ⅱ)得证。证毕。推论1若p是素数，则下述结论成立：(ⅰ)pabpa或pb；(ⅱ)pa2pa。证明留作习题。推论2若(a,b)=1，则(a,bc)=(a,c)。证明设d是a与bc的一个公约数，则a，dbc，由式（2）得到，d|c,即d是a与c的公约数。另一方面，若d是a与c的公约数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a,bc)=(a,c)。证毕。in，则推论3若(a,b)=1，1(a,b1b2b)=1。in证明留作习题。a2,a，定理5对于任意的n个整数a1,,n记,2)=2，(2,3)=3，，(n2,(1ddanaadad1)=dn1，(dn1,an)=dn，则dn=(a1,a2,,an)。证明由定理2的推论，我们有dn=(dn1,an)dnan，dndn1，d1=(d2,ad1an1)n1，dnnn1d2，nndnan，dnan1，dndn2，dn2=(dn3,an2)dn2an2，dn2dn3dnan，dnan1，dnan2，dndn3，d2=(a1,a2)dnan，dnan1，，dna2，dna1，即d是a,a,,a的一个公约数。n12n另一方面，对于a1,a2,,an的任何公约数，由定理2的推论及2,,d的定义，依n次得出da1，d2d2，addd2，d3d3，adddn，dadd，因此d是a1,a2,1nn,a的公约数中的最大者，即dna,n=(a,,a)。证毕。n12n例1证明：若n是正整数，则21n4是14n3既约分数。解 由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1。注：一般地，若(x,)=1，那么，对于任y意的整数a，b，有(x,y)=(xay,y)=(xay,yb(xay))=(xay,(ab1)ybx)，因此，xay是既约分数。(ab1)ybx例2证明：121|n22n12，nZ。解由于121=112，2212=(n1)2nn11，所以，若112(n1)211，1)2，因此，由定理(3)则11(n4的推论1得到1，1121)2。11n(n再由式(3)得到11211，这是不可能的。所以式(3)不能成立。注：这个例题的一般形式是：设p是素数，a，b是整数，则pk|(an b)k pk 1c，其中c是不被p整除的任意整数， k是任意的大于1的整数。例3设a，b是整数，且9 a2 ab b2，(4)则3(a,b)。解由式(4)得到9(a)23ab3(a)2bb3abb)23(a3ab(5)9(ab)2。再由式(4)得到93ab3ab。因此，由定理4的推论1，得到3a或3b。若3a，由式(5)得到3b；若3b，由(5)式也得到3a。因此，总有3a且3b。由定理2的推论推出3(,b)。a，则2b例4设a和b是正整数，b>21|2a1。解(ⅰ)若a<b，且2b12a1。(6)成立，则b1a1ba2ab22222(2a1)2，于是a=1，ba=1，即b=2，这是不可能的，所以式(6)不成立。(ⅱ)若a=b，且式(6)成立，则由式(6)得到2a1(2a1)22a122a122a3，于是b=a=1，这是不可能的，所以式(6)不成立。(ⅲ)若a>b，记a=kbr，0r<，此时b2kb1=(2b1)(21)=(2其中Q是整数。所以

(k1)b2(k2)bb1)Q，2a 1=2kb+r 1=2r(2kb 11=2r((2b1)Q1)1=b1)Qr1)，(2(2其中Q是整数。因此2b12a12b12r1，在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立。综上证得b1a1。2|2习题三证明定理1中的结论(ⅰ)—(ⅳ)。证明定理2的推论1,推论2和推论3。证明定理4的推论1和推论3。4. 设x，y Z，17 2x 3y，证明：17 9x5y。设a，b，cN，c无平方因子，a2b2c，证明：ab。6. 设n是正整数，求C12n,C32n, ,C22nn1的最大公约数。第四节 最小公倍数定义1整数a,a,,a的公共倍数称12k为a1,a2,,ak的公倍数。a1,a2,,ak的正公倍数中的最小的一个叫做a,a,,a的最12k小公倍数，记为[a1,a2,,ak]。定理1下面的等式成立：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[,]=[,]；abbaa|,|a|(ⅲ)[a,a,,a]=[|,12k12|k|]；a(ⅳ)若ab，则[a,b]=|b|。证明留作习题。由定理1中的结论(ⅲ)可知，在讨论a,a,12ak的最小公倍数时，不妨假定它们都是正整数。在本节中总是维持这一假定。最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。定理2对任意的正整数a，b，有[a,b]=ab。(a,b)证明设m是a和b的一个公倍数，那么存在整数k1，2，使得=ak1，=bk2，因此kmmak1=bk2。(1)于是ak1bk2。(a,b)(a,b)由于(a,b)=1，所以由第三节定理4得(a,b)(a,b)到b|k1，即k1bt，(a,b)(a,b)其中t是某个整数。将上式代入式(1)得到m=abt。(2)(a,b)另一方面，对于任意的整数t，由式(2)所确定的显然是a与b的公倍数，因此a与b的m公倍数必是式(2)中的形式，其中t是整数。当t=1时，得到最小公倍数[a,b]=ab。(a,b)证毕。推论1两个整数的任何公倍数可以被它们的最小公倍数整除。证明由式(2)可得证。证毕。这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。推论2设，，b是正整数，则[,]mamamb=m[a,b]。证明由定理2及第三节定理2的推论得到[,]=m2abm2abmab=m[a,mamb(ma,mb)m(a,b)(a,b)b]。证毕。定理3对于任意的n个整数a1,a2,,an，记[a1,a2]=m2，[m2,a3]=m3，，[mn2,an1]=m1，[m1,a]=，nnnn则[1,2,,a]=。nn证明我们有mn=[mn1,an]mn1mn，anmn，m=[m,an]mmm，n1n21n2n1nanmn，an1mn1mn，mmmm2=[m3,an2]32nnnnn，anmn，an1mn，an2mn，m2=[a1,2]nn，，2n，aamama1mn，a,,a的一个公倍数。即m是a,n12n另一方面，对于a1,a2,,an的任何公倍数m，由定理2的推论及m,,m的定义，得m2m，m32nm，，mm。即m是a,a,n,a最小的正的公倍数。证毕。n12n推论若是整数a1,a2,,n的公倍数，ma则[a1,a2,,an]m。证明留作习题。定理4整数a1,a2,,an两两互素，即(ai,aj)=1，1i,jn，ij的充要条件是[a,a,,a]=aaa。12n12n因为(a,a)=1(3)证明必要性，由定理122得到[1,2]=a1a2=12。aa(a1,a2)aa由(a1,a3)=(2,3)=1及第三节定理4推论aa得到(a1a2, a3)=1 ，由此及定理 3得到[a1,a2,a3]=[[a1,a2], a3]=[a1a2,a3]=a1a2a3。如此继续下去，就得到式 (3)。充分性用归纳法证明。当n=2时，式(3)成为[a1,a2]=12。由定理2aaaa=[a,aa1a2(a,a)=1，1212(a1,a2)12即当n=2 时，充分性成立。假设充分性当 n= k时成立，即[a1,a2,,ak]=a1a2ak(a,a)=1，ij对于整数11,i,j,k，ij。aa2,k,k+1，使用定理3中aa的记号，由定理3可知[1,2,,ak,ak+1]=[k,ak+1]。aam(4)其中mk=[a1,a2,,ak]。因此，如果[a1,a2,,ak,ak+1]=a1a2akak+1，那么，由此及式(4)得到[a,a,,a,ak+1]=[m,a]=mkak1=12kkk+1(mk,ak1)a1a2akak+1，即mk=aaa，(mk,ak1)12k显然k12k，(k,k+1)1。所以若maaama使上式成立，必是(mk,ak+1)=1，(5)并且mk=a1a2ak。(6)由式(6)与式(5)推出(ai,ak+1)=1，1ik；(7)由式(6)及归纳假设推出(ai,aj)=1，1i,jk，ij。(8)综合式(7)与式(8)，可知当n=k1时，充分性成立。由归纳法证明了充分性。证毕。定理4有许多应用。例如，如果m1,m2,,m是两两互素的整数，那么，要证明m=mmmk12k整除某个整数，只需证明对于每个i，1iQk，都有miQ。这一点在实际计算中是很有用的。对于函数f(x)，要验证命题“mf(n)，nZ”是否成立，可以用第二节例5中的方法，验证“mf(r)，r=0,1,,m1”是否成立。这需要做 m次除法。但是，若分别验证“mf(r)，ri=0,1,,m1，1iiiik”是否成立，则总共需要做m1m2m次除法。后者的运算次数显然少于前者。k例1设a，b，c是正整数，证明：[a,b,c](ab,bc,ca)=abc。解由定理3和定理2有[a,b,c]=[[a,b],c]=[a,b]c，([a,b],c)(9)由第三节定理5和定理2的推论，(ab,bc,ca)=(ab,(bc,ca))=(ab,c(a,b))=(ab,abc)(ab[a,b],abc)ab([a,b],c)[a,b][a,b][a,b]。(10)联合式(9)与式(10)得到所需结论。例2对于任意的整数a1,a2,,an及整数k，1kn，证明：aa]][a1,a2,,a]=[[a1,,a],[+1,,nkk,an解因为[a,a,,a]是a,,ak12n1+1,,a的公倍数，所以由定理2推论，推出na][a,a,a]，[a,,,[1,kn][11,22,,nk+1,aaan]，aa再由定理3推论知[[1,,k],[ak+1,,an]][1,2,,aaaaan]。(11)另一方面，对于任意的ai（1in），显然[[a,,aaa]]，ai],[k+1,,1kn所以由定理3推论可知,a],[a,a]]，[a,a,,a][[a,,12n1kk+1n联合上式与式(11)得证。例3设a，b，c是正整数，证明：[,,][,,]=[a,][,c][c,]。abcabbccabba解由定理2推论2及例2，有[,,c][,bc,]=[[a,,],[,ababcabcabab,c]bc,[a,b,c]ca]=[[2,2,],,abababcabcb2c,bc2],[a2c,abc,ac2]]=[a2b,ab2,abc,abc,2bc22abc,2bc,,ac,ac]=[abc,a2b,a2c,b2c,b2a,c2a,c2b]以及[a,b][,c][c,a]=[[a,b]b,[,bab]c][c, a]=[ab,b2,ac,bc][c,a]2a],=[ab[c,a],b[c,ac[c, a], bc[c, a]]=[abc,a2b,b2c,b2a,ac2,a2c,bc2, bca]=[abc,a2b,a2c,b2c,b2a,c2a,c2b]，由此得证。习题四证明定理1。证明定理3的推论。3.设a，b是正整数，证明：(ab)[a,b]=a[b,ab]。4.求正整数a，b，使得ab=120，(a,b)=24，[a,b]=144。设a，b，c是正整数，证明：[a,b,c]2(a,b,c)2[a,b][b,c][c,a]。(a,b)(b,c)(c,a)6.设k是正奇数，证明：1291k2k9k。第五节 辗转相除法本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。定义1下面的一组带余数除法，称为辗转相除法。设a和b是整数，b0，依次做带余数除法：a=bq1r1，0<r1<||，bb=r1q2r2，0<r2<r1，rk1=rqrk+1，0<rkkk+1+1<rk，(1)rn2=rn1qnrn，0<rnrn-1，rn 1= rnqn+1。由于b是固定的，而且|b|> r1>r2> ，所以式(1)中只包含有限个等式。下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。引理1 用下面的方式定义 Fibonacci 数列{Fn}：1=2=1，F=F1F2，n3，nnn那么对于任意的整数n3，有F>n2，(2)n其中=15。2证明容易验证2=1。当n=3时，由F3=2>15=2可知式(2)成立。假设式(2)对于所有的整数 k n（n 3）成立，即kk2，kn，F>则n2n3=Fn+1=FnFn1>n3(1)=n32=n1，即当k=n 1时式(2)也成立。由归纳法知式对一切n3成立。证毕。定理1(Lame)设a,bN，a>b，使用在式(1)中的记号，则n<5log10b。证明在式(1)中，rn1，qn+12，qi1（1in），因此rn1=F2，r12r2=3，nnrn2rn1rnF3F2= F4，b r1 r2 Fn+1 FnFn+2，由此及式(2)得bn=(15)n，2即log10bnlog10151n，25这就是定理结论。证毕。定理2使用式(1)中的记号，记PP=1，P=q，P=qP011kkk1k2，k2，QQ=0，Q=1，Q=qQ101kkkk2，k2，则kaQkbPk=(1)1rk，k=1,2,,n。(3)证明当k=1时，式(3)成立。Q当k=2时，有PqPPqqqQQq2，=2=210=2=210211，此时由式(1)得到b(qq1)=(abq)qaQbP=aq1222221b=r1q2b=r2，即式(3)成立。假设对于k<m（1mn）式(3)成立，由此假设及式(1)得到aQbP=a(qQ1Q2)b(qPmmmmmmm1Pm2)=(aQbP)q(aQ11mbPmmm22)m=(1)m2rm1m(1)m3rmq2m1=(1)(rm2rm1m1)m1rm，q)=(即式(3)当k=m时也成立。定理由归纳法得证。证毕。定理3使用式(1)中的记号，有rn=(a,)。br证明由第三节定理1，从式(1)可见,r)n=(rn1,r)=(rn2,rn1)==(r1n2=(b, r1)=( a, b)。证毕。现在我们已经知道，利用辗转相除法可以求出整数x，y，使得axby=(,b)。a(4)为此所需要的除法次数是O(log10b)。但是如果只需要计算(a,b)而不需要求出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。例1 设a和b是正整数，那么只使用被 2除的除法运算和减法运算就可以计算出 (a, b)。解 下面的四个基本事实给出了证明：(ⅰ) 若a b，则(a, b)= a；(ⅱ) 若a=2a1，2|a1，b 2 b1，2|b1，，则(,b)=2(2a1,b1)；a(ⅲ)若2|a，b2b1，2|b1，则(a,b)=(a,b1)；(ⅳ)若2|a，2|b，则(a,b)(|ab,b。2|)在实际计算过程中，若再灵活运用最大公约数的性质（例如第三节定理4的推论），则可使得求最大公约数的过程更为简单。例2用辗转相除法求(125,17)，以及x，y，使得125x17y=(125,17)。解做辗转相除法：125=7176，q1=7，r1=6，17=265，q2=2，r2=5，6=151，q3=1，r3=1，5=51，q4=5。由定理4，(125,17)=r3=1。利用定理2计算（n=3）P0=1，P1=7，P2=271=15，P3=1157=22，Q=0，Q=1，Q=210=2，0123=121=3，Q取x=(1)31Q3=3，y=(1)3P3=22，则125 3 17 ( 22)=(125,17)=1 。例3求(12345,678)。解(12345,678)=(12345,339)=(12006,339)=(6003,339)(5664,339)=(177,339)=(177,=(177,81)=(96,81)=(3,81)=3 。例4在m个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n（n<）个盒子中各放一个硬币。证明：若(,mmn)=1，那么无论开始时每个盒子中有多少硬币，经过若干次放硬币后，总可使所有盒子含有同样数量的硬币。使得

解 由于(m,mx ny=1

n)=1，所以存在整数。因此对于任意的自然数

x，y，k，有1

m(

x

kn)=

n(km

y)，这样，当

k充分大时，总可找出正整数

x0，y0，使得1

mx0=

ny0。上式说明，如果放 y0次（每次放 n个），那么在使m个盒子中各放x0个后，还多出一个硬币。把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1。因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同。习题五说明例1证明中所用到的四个事实的依据。用辗转相除法求整数x，y，使得1387x162y=(1387,162) 。3. 计算：(27090,21672,11352) 。使用引理1中的记号，证明：(Fn+1,Fn)1。若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少6.记Mn1，证明：对于正整数a，=2nb，有(Ma, Mb)=M(a,b)。第六节 算术基本定理在本节中，我们要介绍整数与素数的一个重要关系，即任何大于1的正整数都可以表示成素数的乘积。引理1任何大于1的正整数n可以写成素数之积，即p，n=pp(1)12m其中i（1i）是素数。pm证明当n=2时，结论显然成立。假设对于2nk，式(1)成立，我们来证明式(1)对于n=k1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立。如果k1是素数，式(1)显然成立。如果k1是合数，则存在素数p与整数d，使得k1=pd。由于2dk，由归纳假定知存在素数q,q,,q，使得d=q1q2q，从而k12ql1=pq1q2。证毕。ll定理1(算术基本定理)任何大于1的整数可以唯一地表示成n=p11p22pkk，(2)其中1,2,,p是素数，1<p2<<p，kk1,2,,k是正整数。证明由引理1，任何大于1的整数n可以表示成式(2)的形式，因此，只需证明表示式 (2)的唯一性。ik）与q（1jl）假设p（1ij都是素数，pqqqpp221k，1l，(3)并且n=p1p2pk=q1q2ql，(4)则由第三节定理4推论1，必有某个qj（1jl），使得p1qj，所以p1=qj；又有某个pi（1ik），使得qp，所以q=pi。于1i1是，由式(3)可知p1=q1，从而由式(4)得到2p=q2q。lk重复上述这一过程，得到k=l，pi=qi，1ik。证毕。定义1 使用定理 1中的记号，称n=p11p22pkk是n的标准分解式，其中pi（1ik）是素数，p1<p2<<p，i（1ik）k是正整数。推论1使用式(2)中的记号，有(ⅰ)n的正因数d必有形式d=p11p22pkk，iZ，0i k；

ii，1(ⅱ) n的正倍数m必有形式m=p11p22 pkkM，M N， i N， i i，ik。证明留作习题。推论2设正整数a与b的标准分解式是ap1pkq1ql，bp1pkr1rss1k1l1k1，其中pi（1ik），qi（1il）与ri（1is）是两两不相同的素数，i，i（1ik），i（1il）与i（1is）都是非负整数，则(a,b)=p11pkk，i=min{i,i}，1ik，[a,b]=p11pkkq11qllr11rss，i=max{i,i}，1ik。证明留作习题。为了方便，推论2常叙述为下面的形式：推论2设正整数a与b的标准分解式是ap11p22pkk，bp11p21pkk，其中p,p,,p是互不相同的素数，i，12ki（1ik）都是非负整数，则(a,b)p11p21pkk，i[a,b]p11p21pkk，i

min{i,i}，1ik，max{i,i}，1ik。推论3设a，b，c，n是正整数，ab=cn，(a,b)=1，(5)则存在正整数u，v，使得nb=nc=uv，(u,v)=1。a=u，v，证明设c=p1p2pkk，其中p,p,,1112pk是互不相同的素数，i（1ik）是正整数。又设ap11p22pkk，bp11p21pkk，其中I，i（1ik）都是非负整数。由式(5)及推论2可知min{i,i}=0，ii=ni，1ik，因此，对于每个i（1ik），等式i=ni，i=0与i=0，i=ni有且只有一个成立。这就证明了推论。证毕。例1写出51480的标准分解式。解我们有51480=2212870=2325740=264352323=51287=5342923322332=5143=51113。例2设a，b，c是整数，证明：(ⅰ)(,b)[a,]=；abab(ⅱ)(a,[b,c])=[(a,b),(a,c)]。解为了叙述方便，不妨假定，，c是正ab整数。(ⅰ)设ap11p22pkk，bp11p21pkk，其中p1,p2,,p是互不相同的素数，i，ki（1ik）都是非负整数。由定理1推论2，有(a,b)p11p21pkk，i[a,b]p11p21pkk，i由此知

min{i,i}，1ik，max{i,i}，1ik。(a,b)[a,b]=kki,i}max{i,i}ki=iimin{ipipipiai1i1i1b；(ⅱ) 设kkkapii，bpii，cpii，i1i1i1其中p1,p2,,p是互不相同的素数，i，ki，i（1ik）都是非负整数。由定理1推论2，有kk(a,[b,c])pii，[(a,b),(a,c)]pii，i1i1其中，对于1ik，有i=min{i,max{i,i}}，i=max{min{i,i},min{i,i}}，不妨设ii，则min{i,i}min{i,i}，所以i=min{i,i}=i，即(a,[b,c])=[(a,b),(a,c)]。注：利用定理1可以容易地处理许多像例2这样的问题。例3证明：N1111（n352n12）不是整数。解设3k2n1<3k+1。3k，记对于任意的1in，2i121=ii，i，3QQZ由第一节例5，知k1。因为k12ni312QQQ1是整数，所以，如果N是整数，则存在整数Q，使得3k1122n1N=Q3k1122n11。QQQQQQ3k由于3|QQQ，所以上式右端不是整数，这122n1个矛盾说明 N不能是整数。习题六证明定理1的推论1。证明定理1的推论2。写出的标准分解式。4.证明：在1,2,,2n中任取n1数，其中至少有一个能被另一个整除。5.证明：111（n2）不是整2n数。6.设a，b是正整数，证明：存在a1，a2，b1，b2，使得a=12，b=12，(a2,b2)=1，aabb并且[a,b]=a2b2。第七节 函数[x]与{x}本节中要介绍函数[x]，它在许多数学问题中有广泛的应用。定义1 设x是实数，以[x]表示不超过 x的最大整数，称它为x的整数部分，又称{x}=x[x]为x的小数部分。定理

1

设x与

y是实数，则(ⅰ)

x

y

[

x]

[

y]；(ⅱ)(ⅲ)

若m是整数，则[m x]=m若0 x<1，则[x]=0 ；

[x]；(ⅳ)[xy]=[x][y]若{x}{y}1；[x][y]1若{x}{y}1(ⅴ)[]=[x]若xZ；x[x]1若xZ(ⅵ){x}=0若xZ。1{x}若xZ证明留作习题。定理2设a与b是正整数，则在1,2,,a中能被b整除的整数有[a]个。b证明能被b整除的正整数是b,2,3,bb，因此，若数1,2,,a中能被b整除的整数有k个，则kba<(k1)bka<k1bk=[a]。b证毕。由定理2我们看到，若b是正整数，那么对于任意的整数a，有ab[a]b{a}，bb即在带余数除法a=bqr，0r<b中有q[a]，rb{a}。bb定理3设n是正整数，n!=p11p22pkk是n!的标准分解式，则i=[n]。rpir1(1)证明对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则p(n!)=p(1)p(2)p(n)。以n表示p(1),p(2),,p(n)中等于j的个j数，那么(!)=1n12233，pnnn,n中满足pj(2)显然，nj就是在1,2,a并且pj+1|a的整数a的个数，所以，由定理2有nj=[npj

][n]。将上式代入式(2)，得到p(n!)1n[n])2([n([p]p2p2[nr]。r1p即式(1)成立。证毕。

] [n]) 3([np3 p3

] [n])p4推论设n是正整数，则[n]n!=pr1pr，pn其中表示对不超过n的所有素数p求积。pn定理４设n是正整数，1kn1，则Cnkn!k)!N。k!(n(3)若n是素数，则nCnk，1kn1。证明由定理3，对于任意的素数p，整数n!，k!与(nk)!的标准分解式中所含的p的指数分别是r1[nr]，[kr]与[nprk]。pr1pr1利用定理1可知r1[nr][kr]r[nprk]，pr1p1因此Cnk是整数。若n是素数，则对于1kn1，有(,k!)=1，(,(nk)!)=1(n,k!(nnnk)!)=1，由此及Cnkn(n1)!N，k!(nk)!推出k!(nk)!(n1)!，从而nCnk。证毕。k例1 求最大的正整数 k，使得10 199!。解 由定理3，199!的标准分解式中所含的的幂指数是[1991991995][52][53]=47，所以，所求的最大整数是k=47。例2设x与y是实数，则[2x][2y][x][xy][y]。(4)解设x=[x]，0<1，y=[y]，0<1，则[x][xy][y]=2[x]2[y][]，(5)[2x][2y]=2[x]2[y][2][2]。(6)如果[]=0，那么显然有[][2][2]；如果[]=1，那么与中至少有一个不小于1，于是2[2][2]1=[]。因此无论[]=0或1，都有[][2][2]，由此及式(5)和式(6)可以推出式(4)。例3设n是正整数，则[nn1][4n2]。(7)解首先，我们有[nn1]nn12n12n(n1)2n12n14n2，所以[nn1][4n2]。若上式中的等号不成立，即[ n n 1] [ 4n 2]，(8)则存在整数 a，使得[nn1]a[4n2]，因此2n12n(n1)a24n2，2n2na22n12n1，(2n1)21<(a22n1)2(2n1)2，所以a22n1=2n1a2=4n2。(9)但是，无论2a或2|a，式(9)都不能成立，这个矛盾说明式(8)不能成立，即式(7)成立。例4设x是正数，n是正整数，则[x][x1][x2][xn1]=[nx]。nnn解设x=[x]，ii1，0nnn1，则[x][x1][x2][xn1]nnn=[]i=[][n]=nxnx[n([x])]=[nx]。例5求[(32)1992]的个位数。解由(32)2526得(32)1992(32)1992=(526)996(526)996=2(5996C9962599422629966498)=10A29976498=10A224498=10A2(251)498=10B2，（10）其中A和B都是整数。由于0<526<1，所以，由式(10)可知[(32)1996]的个位数是1。注：一般地，如果，N，2>，AB<ABAB1，则由(AB)k(AB)k2(AkCk2Ak2B)可以求出[(AB)k]。例6设x和y是正无理数，111，证xy明：数列[x],[2x],,[kx],与[y],[2y],,[my],(11)联合构成了整个正整数集合，而且，两个数列中的数互不相同。解显然x>1，y>1，并且xy。因此，在数列(11)中至多有一个数等于给定的正整数，否则存在正整数k与，使得nmn=[kx]=[]。my因为x与y都是无理数，所以我们有n<kx<n1，n<my<n1，k1k，m1m，n1xnn1ynkm111km，n1xynn<km<n1，这是不可能的。下面证明，对于任意给定的正整数n，总可找到某个正整数k，使得n等于[kx]或者[ky]。假设不然，则存在p,qN，使得[px]<n<[(p 1)x]，[qy]<n<[(q 1)y]。于是（因为x和y是无理数），px<n<n1[(p1)x]<(p1)x，qy<n<n1[(q1)y]<(q1)y，pq111pq2，nxyn1pq<n<n1<pq2，这是不可能的。习题七证明定理1。k求使12347!被35整除的最大的k值。设n是正整数，x是实数，证明：[n2r12r]=n。r1设n是正整数，求方程x2[x2]=(x[x])2在[1,n]中的解的个数。证明：方程f(x)=[x][2x][22x][23x][24x][25x]=12345没有实数解。证明：在n!的标准分解式中，2的指数h=nk，其中k是n的二进制表示的位数码之和。第八节 素 数在第六