初等数论 整除理论 (B)

第一章整除理论整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。第一节数的整除性定义1设a，b是整数，b0，如果存在整数c，使得a=bc成立，则称a被b整除，a是b的倍数，b是a的约数（因数或除数），并且使用记号ba；如果不存在整数c使得a=bc成立，则称a不被b整除，记为ba。显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。被2整除的整数称为偶数，不被2整除的整数称为奇数。定理1下面的结论成立：(ⅰ)abab；(ⅱ)ab，bcac；(ⅲ)bai，i=1,2,,kba1x1a2x2akxk，此处xi（i=1,2,,k）是任意的整数；(ⅳ)babcac，此处c是任意的非零整数；(ⅴ)ba，a0|b||a|；ba且|a|<|b|a=0。证明留作习题。定义2若整数a0，1，并且只有约数1和a，则称a是素数（或质数）；否则称a为合数。以后在本中若无特别说明，素数总是指正素数。定理2任何大于1的整数a都至少有一个素约数。证明若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1,d2,,dk。不妨设d1是其中最小的。若d1不是素数，则存在e1>1，e2>1，使得d1=e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。推论任何大于1的合数a必有一个不超过的素约数。证明使用定理2中的记号，有a=d1d2，其中d1>1是最小的素约数，所以d12a。证毕。例1设r是正奇数，证明：对任意的正整数n，有n21r2rnr。解对于任意的正整数a，b以及正奇数k，有akbk=(ab)(ak1ak2bak3b2bk1)=(ab)q，其中q是整数。记s=1r2rnr，则2s=2(2rnr)(3r(n1)r)(nr2r)=2(n2)Q，其中Q是整数。若n2s，由上式知n22，因为n2>2，这是不可能的，所以n2s。例2设A={d1,d2,,dk}是n的所有约数的集合，则B=也是n的所有约数的集合。解由以下三点理由可以证得结论：(ⅰ)A和B的元素个数相同；(ⅱ)若diA，即din，则n，反之亦然；(ⅲ)若didj，则。例3以d(n)示n的正约数的个数，例如：d(1)=1，d(2)=2，d(3)=2，d(4)=3，。问：d(1)d(2)d(1997)是否为偶数？解对于n的每个约数d，都有n=d，因此，n的正约数d与是成对地出现的。只有当d=，即n=d2时，d和才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。因为442<1997<452，所以在d(1),d(2),,d(1997)中恰有44个奇数，故d(1)d(2)d(1997)是偶数。例4设凸2n边形M的顶点是A1,A2,,A2n，点O在M的内部，用1,2,,2n将M的2n条边分别编号，又将OA1,OA2,,OA2n也同样进行编号，若把这些编号作为相应的线段的长度，证明：无论怎么编号，都不能使得三角形OA1A2,OA2A3,,OA2nA1的周长都相等。解假设这些三角形的周长都相等，记为s。则2ns=3(122n)=3n(2n1)，即2s=3(2n1)，因此23(2n1)，这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。例5设整数k1，证明：(ⅰ)若2kn<2k1，1an，a2k，则2ka；(ⅱ)若3k2n1<3k+1，1bn，2b13k，则3k2b1。解(ⅰ)若2k|a，则存在整数q，使得a=q2k。显然q只可能是0或1。此时a=0或2k，这都是不可能的，所以2ka；(ⅱ)若3k|2b-1，则存在整数q，使得2b-1=q3k，显然q只可能是0，1,或2。此时2b-1=0，3k，或，这都是不可能的，所以3k2b1。例6写出不超过100的所有的素数。解将不超过100的正整数排列如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以下步骤进行：(ⅰ)删去1，剩下的后面的第一个数是2，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证明：存在无穷多个正整数a，使得n4a（n=1,2,3,）都是合数。解取a=4k4，对于任意的nN，有n44k4=(n22k2)24n2k2=(n22k22nk)(n22k22nk)。因为n22k22nk=(nk)2k2k2，所以，对于任意的k=2,3,以及任意的nN，n4a是合数。例8设a1,a2,,an是整数，且a1a2an=0，a1a2an=n，则4n。解如果2n，则n,a1,a2,,an都是奇数。于是a1a2an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2n，即在a1,a2,,an中至少有一个偶数。如果只有一个偶数，不妨设为a1，那么2ai（2in）。此时有等式a2an=a1，在上式中，左端是(n1)个奇数之和，右端是偶数，这是不可能的，因此，在a1,a2,,an中至少有两个偶数，即4n。例9若n是奇数，则8n21。解设n=2k1，则n21=(2k1)21=4k(k1)。在k和k1中有一个是偶数，所以8n21。例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的问题：问题d(1)2d(2)2d(1997)2被4除的余数是多少？例10证明：方程a12a22a32=1999(1)无整数解。解若a1，a2，a3都是奇数，则存在整数A1，A2，A3，使得a12=8A11，a22=8A21，a32=8A31，于是a12a22a32=8(A1A2A3)3。由于1999被8除的余数是7，所以a1，a2，a3不可能都是奇数。由式(1)，a1，a2，a3中只能有一个奇数，设a1为奇数，a2，a3为偶数，则存在整数A1，A2，A3，使得a12=8A11，a22=8A2r，a32=8A3s，于是a12a22a32=8(A1A2A3)1rs，其中r和s是整数，而且只能取值0或4。这样a12a22a32被8除的余数只可能是1或5，但1999被8除的余数是7，所以这样的a1，a2，a3也不能使式(2)成立。综上证得所需要的结论。习题一1.证明定理1。2.证明：若mpmnpq，则mpmqnp。3.证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。4.设p是n的最小素约数，n=pn1，n1>1，证明：若p>，则n1是素数。5.证明：存在无穷多个自然数n，使得n不能表示为a2p（a>0是整数，p为素数）的形式。第二节带余数除法在本节中，我们要介绍带余数除法及其简单应用。定理1(带余数除法)设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得a=bqr，0r<|b|。(1)证明存在性若ba，a=bq，qZ，可取r=0。若ba，考虑集合A={akb；kZ},其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。在集合A中有无限多个正整数，设最小的正整数是r=ak0b，则必有0<r<|b|，(2)否则就有r|b|。因为ba，所以r|b|。于是r>|b|，即ak0b>|b|，ak0b|b|>0，这样，在集合A中，又有正整数ak0b|b|<r，这与r的最小性矛盾。所以式(2)必定成立。取q=k0知式(1)成立。存在性得证。唯一性假设有两对整数q，r与q，r都使得式(1)成立，即a=qbr=qbr，0r,r<|b|，则(qq)b=rr，|rr|<|b|，(3)因此rr=0，r=r，再由式(3)得出q=q，唯一性得证。证毕。定义1称式(1)中的q是a被b除的商，r是a被b除的余数。由定理1可知，对于给定的整数b，可以按照被b除的余数将所有的整数分成b类。在同一类中的数被b除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。以后在本书中，除特别声明外，在谈到带余数除法时总是假定b是正整数。例1设a，b，x，y是整数，k和m是正整数，并且a=a1mr1，0r1<m，b=b1mr2，0r2<m，则axby和ab被m除的余数分别与r1xr2y和r1r2被m除的余数相同。特别地，ak与r1k被m除的余数相同。解由axby=(a1mr1)x(b1mr2)y=(a1xb1y)mr1xr2y可知，若r1xr2y被m除的余数是r，即r1xr2y=qmr，0r<m，则axby=(a1xb1yq)mr，0r<m，即axby被m除的余数也是r。同样方法可以证明其余结论。例2设a1,a2,,an为不全为零的整数，以y0表示集合A={y；y=a1x1anxn，xiZ，1in}中的最小正数，则对于任何yA，y0y；特别地，y0ai，1in。解设y0=a1x1anxn，对任意的y=a1x1anxnA，由定理1，存在q,r0Z，使得y=qy0r0，0r0<y0。因此r0=yqy0=a1(x1qx1)an(xnqxn)A。如果r00，那么，因为0<r0<y0，所以r0是A中比y0还小的正数，这与y0的定义矛盾。所以r0=0，即y0y。显然aiA（1in），所以y0整除每个ai（1in）。例3任意给出的五个整数中，必有三个数之和被3整除。解设这五个数是ai，i=1,2,3,4,5，记ai=3qiri，0ri<3，i=1,2,3,4,5。分别考虑以下两种情形：(ⅰ)若在r1,r2,,r5中数0，1，2都出现，不妨设r1=0，r2=1，r3=2，此时a1a2a3=3(q1q2q3)3可以被3整除；(ⅱ)若在r1,r2,,r5中数0，1，2至少有一个不出现，这样至少有三个ri要取相同的值，不妨设r1=r2=r3=r（r=0，1或2），此时a1a2a3=3(q1q2q3)3r可以被3整除。例4设a0,a1,,anZ，f(x)=anxna1xa0，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x)=0有整数解，则3f(1)=a0a1a2(1)nan。解对任何整数x，都有x=3qr，r=0，1或2，qZ。(ⅰ)若r=0，即x=3q，qZ，则f(x)=f(3q)=an(3q)na1(3q)a0=3Q1a0=3Q1f(0)，其中Q1Z，由于f(0)不是3的倍数，所以f(x)0；(ⅱ)若r=1，即x=3q1，qZ，则f(x)=f(3q1)=an(3q1)na1(3q1)a0=3Q2ana1a0=3Q2f(1)，其中Q2Z。由于f(1)不是3的倍数，所以f(x)0。因此若f(x)=0有整数解x，则必是x=3q2=3q1，qZ，于是0=f(x)=f(3q1)=an(3q1)na1(3q1)a0=3Q3a0a1a2(1)nan=3Q3f(1)，其中Q3Z。所以3f(1)=a0a1a2(1)nan。例5证明：对于任意的整数n，f(n)=3n55n37n被15整除。解对于任意的正整数n，记n=15qr，0r<15。由例1，n2=15Q1r1，n4=15Q2r2，其中r1与r2分别是r2与r4被15除的余数。以R表示3n45n27被15除的余数，则R就是3r25r17被15除的余数，而且f(n)被15除的余数就是rR被15除的余数，记为R。当r=0时，显然R=0，即153n55n37n。对于r=1,2,3,,14的情形，通过计算列出下表：r=1,142,133,124,115,106,97,8r1=14911064r2=11611061R=0010012100R=0000000这证明了结论。例6设n是奇数，则16n44n211。解我们有n44n211=(n21)(n25)16。由第一节例题9，有8n21，由此及2n25得到16(n21)(n25)。例7证明：若a被9除的余数是3，4，5或6，则方程x3y3=a没有整数解。解对任意的整数x，y，记x=3q1r1，y=3q2r2，0r1,r2<3。则存在Q1,R1,Q2,R2Z，使得x3=9Q1R1，y3=9Q2R2，其中R1和R2被9除的余数分别与r13和r23被9除的余数相同，即R1=0，1或8，R2=0，1或8。(4)因此x3y3=9(Q1Q2)R1R2。又由式(4)可知，R1R2被9除的余数只可能是0，1，2，7或8，所以，x3y3不可能等于a。习题二1.证明：12n42n311n210n，nZ。2.设3a2b2，证明：3a且3b。3.设n，k是正整数，证明：nk与nk+4的个位数字相同。4.证明：对于任何整数n，m，等式n2(n1)2=m22不可能成立。5.设a是自然数，问a43a29是素数还是合数？6.证明：对于任意给定的n个整数，必可以从中找出若干个作和，使得这个和能被n整除。第三节最大公约数定义1整数a1,a2,,ak的公共约数称为a1,a2,,ak的公约数。不全为零的整数a1,a2,,ak的公约数中最大的一个叫做a1,a2,,ak的最大公约数（或最大公因数），记为(a1,a2,,ak)。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果(a1,a2,,ak)=1，则称a1,a2,,ak是互素的（或互质的）；如果(ai,aj)=1，1i,jk，ij，则称a1,a2,,ak是两两互素的（或两两互质的）。显然，a1,a2,,ak两两互素可以推出(a1,a2,,ak)=1，反之则不然，例如(2,6,15)=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或pa；(ⅴ)若a=bqr，则(a,b)=(b,r)。证明(ⅰ)(ⅳ)留作习题。(ⅴ)由第一节定理1可知，如果da，db，则有dr=abq，反之，若db，dr，则da=bqr。因此a与b的全体公约数的集合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相等，即(a,b)=(b,r)。证毕。由定理1可知，在讨论(a1,a2,,an)时，不妨假设a1,a2,,an是正整数，以后我们就维持这一假设。定理2设a1,a2,,akZ，记A={y；y=，xiZ，ik}。如果y0是集合A中最小的正数，则y0=(a1,a2,,ak)。证明设d是a1,a2,,ak的一个公约数，则dy0，所以dy0。另一方面，由第二节例2知，y0也是a1,a2,,ak的公约数。因此y0是a1,a2,,ak的公约数中的最大者，即y0=(a1,a2,,ak)。证毕。推论1设d是a1,a2,,ak的一个公约数，则d(a1,a2,,ak)。这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。推论2(ma1,ma2,,mak)=|m|(a1,a2,,ak)。推论3记=(a1,a2,,ak)，则=1，特别地,=1。定理3(a1,a2,,ak)=1的充要条件是存在整数x1,x2,,xk，使得a1x1a2x2akxk=1。(1)证明必要性由定理2得到。充分性若式(1)成立，如果(a1,a2,,ak)=d>1，那么由dai（1ik）推出da1x1a2x2akxk=1，这是不可能的。所以有(a1,a2,,ak)=1。证毕。定理4对于任意的整数a，b，c，下面的结论成立：(ⅰ)由bac及(a,b)=1可以推出bc；(ⅱ)由bc，ac及(a,b)=1可以推出abc。证明(ⅰ)若(a,b)=1，由定理2，存在整数x与y，使得axby=1。因此acxbcy=c。(2)由上式及bac得到bc。结论(ⅰ)得证；(ⅱ)若(a,b)=1，则存在整数x，y使得式(2)成立。由bc与ac得到abac，abbc，再由式(2)得到abc。结论(ⅱ)得证。证毕。推论1若p是素数，则下述结论成立：(ⅰ)pabpa或pb；(ⅱ)pa2pa。证明留作习题。推论2若(a,b)=1，则(a,bc)=(a,c)。证明设d是a与bc的一个公约数，则da，dbc，由式（2）得到，d|c,即d是a与c的公约数。另一方面，若d是a与c的公约数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a,bc)=(a,c)。证毕。推论3若(a,bi)=1，1in，则(a,b1b2bn)=1。证明留作习题。定理5对于任意的n个整数a1,a2,,an，记(a1,a2)=d2，(d2,a3)=d3，，(dn2,an1)=dn1，(dn1,an)=dn，则dn=(a1,a2,,an)。证明由定理2的推论，我们有dn=(dn1,an)dnan，dndn1，dn1=(dn2,an1)dn1an1，dn1dn2，dnan，dnan1，dndn2，dn2=(dn3,an2)dn2an2，dn2dn3dnan，dnan1，dnan2，dndn3，d2=(a1,a2)dnan，dnan1，，dna2，dna1，即dn是a1,a2,,an的一个公约数。另一方面，对于a1,a2,,an的任何公约数d，由定理2的推论及d2,,dn的定义，依次得出da1，da2dd2，dd2，da3dd3，ddn1，danddn，因此dn是a1,a2,,an的公约数中的最大者，即dn=(a1,a2,,an)。证毕。例1证明：若n是正整数，则是既约分数。解由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1。注：一般地，若(x,y)=1，那么，对于任意的整数a，b，有(x,y)=(xay,y)=(xay,yb(xay))=(xay,(ab1)ybx)，因此，是既约分数。例2证明：121n22n12，nZ。解由于121=112，n22n12=(n1)211，所以，若112(n1)211，(3)则11(n1)2，因此，由定理4的推论1得到11n1，112(n1)2。再由式(3)得到11211，这是不可能的。所以式(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b)23ab3(ab)23ab3(ab)23ab(5)9(ab)2。再由式(4)得到93ab3ab。因此，由定理4的推论1，得到3a或3b。若3a，由式(5)得到3b；若3b，由(5)式也得到3a。因此，总有3a且3b。由定理2的推论推出3(a,b)。例4设a和b是正整数，b>2，则2b12a1。解(ⅰ)若a<b，且2b12a1。(6)成立，则2b12a12b2a22a(2ba1)2，于是a=1，ba=1，即b=2，这是不可能的，所以式(6)不成立。(ⅱ)若a=b，且式(6)成立，则由式(6)得到2a1(2a1)22a122a122a3，于是b=a=1，这是不可能的，所以式(6)不成立。(ⅲ)若a>b，记a=kbr，0r<b，此时2kb1=(2b1)(2(k1)b2(k2)b1)=(2b1)Q，其中Q是整数。所以2a1=2kb+r1=2r(2kb11)1=2r((2b1)Q1)1=(2b1)Q(2r1)，其中Q是整数。因此2b12a12b12r1，在(ⅰ)中已经证明这是不可能的，所以式(6)不能成立。综上证得2b12a1。习题三1.证明定理1中的结论(ⅰ)—(ⅳ)。2.证明定理2的推论1,推论2和推论3。3.证明定理4的推论1和推论3。4.设x，yZ，172x3y，证明：179x5y。5.设a，b，cN，c无平方因子，a2b2c，证明：ab。6.设n是正整数，求的最大公约数。第四节最小公倍数定义1整数a1,a2,,ak的公共倍数称为a1,a2,,ak的公倍数。a1,a2,,ak的正公倍数中的最小的一个叫做a1,a2,,ak的最小公倍数，记为[a1,a2,,ak]。定理1下面的等式成立：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[a,b]=[b,a]；(ⅲ)[a1,a2,,ak]=[|a1|,|a2|,|ak|]；(ⅳ)若ab，则[a,b]=|b|。证明留作习题。由定理1中的结论(ⅲ)可知，在讨论a1,a2,,ak的最小公倍数时，不妨假定它们都是正整数。在本节中总是维持这一假定。最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。定理2对任意的正整数a，b，有[a,b]=。证明设m是a和b的一个公倍数，那么存在整数k1，k2，使得m=ak1，m=bk2，因此ak1=bk2。(1)于是。由于=1，所以由第三节定理4得到，其中t是某个整数。将上式代入式(1)得到m=t。(2)另一方面，对于任意的整数t，由式(2)所确定的m显然是a与b的公倍数，因此a与b的公倍数必是式(2)中的形式，其中t是整数。当t=1时，得到最小公倍数[a,b]=。证毕。推论1两个整数的任何公倍数可以被它们的最小公倍数整除。证明由式(2)可得证。证毕。这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另外的公倍数的约数。推论2设m，a，b是正整数，则[ma,mb]=m[a,b]。证明由定理2及第三节定理2的推论得到[ma,mb]==m[a,b]。证毕。定理3对于任意的n个整数a1,a2,,an，记[a1,a2]=m2，[m2,a3]=m3，，[mn2,an1]=mn1，[mn1,an]=mn，则[a1,a2,,an]=mn。证明我们有mn=[mn1,an]mn1mn，anmn，mn1=[mn2,an1]mn2mn1mn，anmn，an1mn1mn，mn2=[mn3,an2]mn3mn2mn，anmn，an1mn，an2mn，m2=[a1,a2]anmn，，a2mn，a1mn，即mn是a1,a2,,an的一个公倍数。另一方面，对于a1,a2,,an的任何公倍数m，由定理2的推论及m2,,mn的定义，得m2m，m3m，，mnm。即mn是a1,a2,,an最小的正的公倍数。证毕。推论若m是整数a1,a2,,an的公倍数，则[a1,a2,,an]m。证明留作习题。定理4整数a1,a2,,an两两互素，即(ai,aj)=1，1i,jn，ij的充要条件是[a1,a2,,an]=a1a2an。(3)证明必要性因为(a1,a2)=1，由定理2得到[a1,a2]==a1a2。由(a1,a3)=(a2,a3)=1及第三节定理4推论3得到(a1a2,a3)=1，由此及定理3得到[a1,a2,a3]=[[a1,a2],a3]=[a1a2,a3]=a1a2a3。如此继续下去，就得到式(3)。充分性用归纳法证明。当n=2时，式(3)成为[a1,a2]=a1a2。由定理2a1a2=[a1,a2]=(a1,a2)=1，即当n=2时，充分性成立。假设充分性当n=k时成立，即[a1,a2,,ak]=a1a2ak(ai,aj)=1，1i,jk，ij。对于整数a1,a2,,ak,ak+1，使用定理3中的记号，由定理3可知[a1,a2,,ak,ak+1]=[mk,ak+1]。(4)其中mk=[a1,a2,,ak]。因此，如果[a1,a2,,ak,ak+1]=a1a2akak+1，那么，由此及式(4)得到[a1,a2,,ak,ak+1]=[mk,ak+1]==a1a2akak+1，即=a1a2ak，显然mka1a2ak，(mk,ak+1)1。所以若使上式成立，必是(mk,ak+1)=1，(5)并且mk=a1a2ak。(6)由式(6)与式(5)推出(ai,ak+1)=1，1ik；(7)由式(6)及归纳假设推出(ai,aj)=1，1i,jk，ij。(8)综合式(7)与式(8)，可知当n=k1时，充分性成立。由归纳法证明了充分性。证毕。定理4有许多应用。例如，如果m1,m2,,mk是两两互素的整数，那么，要证明m=m1m2mk整除某个整数Q，只需证明对于每个i，1ik，都有miQ。这一点在实际计算中是很有用的。对于函数f(x)，要验证命题“mf(n)，nZ”是否成立，可以用第二节例5中的方法，验证“mf(r)，r=0,1,,m1”是否成立。这需要做m次除法。但是，若分别验证“mif(ri)，ri=0,1,,mi1，1ik”是否成立，则总共需要做m1m2mk次除法。后者的运算次数显然少于前者。完整版请手机扫描下面taobao店铺例1设a，b，c是正整数，证明：[a,b,c](ab,bc,ca)=abc。解由定理3和定理2有[a,b,c]=[[a,b],c]=，(9)由第三节定理5和定理2的推论，(ab,bc,ca)=(ab,(bc,ca))=(ab,c(a,b))=。(10)联合式(9)与式(10)得到所需结论。例2对于任意的整数a1,a2,,an及整数k，1kn，证明：[a1,a2,,an]=[[a1,,ak],[ak+1,,an]]解因为[a1,a2,,an]是a1,,ak,ak+1,,an的公倍数，所以由定理2推论，推出[a1,,ak][a1,a2,,an]，[ak+1,,an][a1,a2,,an]，再由定理3推论知[[a1,,ak],[ak+1,,an]][a1,a2,,an]。(11)另一方面，对于任意的ai（1in），显然ai[[a1,,ak],[ak+1,,an]]，所以由定理3推论可知[a1,a2,,an][[a1,,ak],[ak+1,,an]]，联合上式与式(11)得证。例3设a，b，c是正整数，证明：[a,b,c][ab,bc,ca]=[a,b][b,c][c,a]。解由定理2推论2及例2，有[a,b,c][ab,bc,ca]=[[a,b,c]ab,[a,b,c]bc,[a,b,c]ca]=[[a2b,ab2,abc],[abc,b2c,bc2],[a2c,abc,ac2]]=[a2b,ab2,abc,abc,b2c,bc2,a2c,abc,ac2]=[abc,a2b,a2c,b2c,b2a,c2a,c2b]以及[a,b][b,c][c,a]=[[a,b]b,[a,b]c][c,a]=[ab,b2,ac,bc][c,a]=[ab[c,a],b2[c,a],ac[c,a],bc[c,a]]=[abc,a2b,b2c,b2a,ac2,a2c,bc2,bca]=[abc,a2b,a2c,b2c,b2a,c2a,c2b]，由此得证。习题四1.证明定理1。2.证明定理3的推论。3.设a，b是正整数，证明：(ab)[a,b]=a[b,ab]。4.求正整数a，b，使得ab=120，(a,b)=24，[a,b]=144。5.设a，b，c是正整数，证明：。6.设k是正奇数，证明：1291k2k9k。第五节辗转相除法本节要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。定义1下面的一组带余数除法，称为辗转相除法。设a和b是整数，b0，依次做带余数除法：a=bq1r1，0<r1<|b|，b=r1q2r2，0<r2<r1，rk1=rkqk+1rk+1，0<rk+1<rk，(1)rn2=rn1qnrn，0<rn<rn-1，rn1=rnqn+1。由于b是固定的，而且|b|>r1>r2>，所以式(1)中只包含有限个等式。下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。引理1用下面的方式定义Fibonacci数列{Fn}：F1=F2=1，Fn=Fn1Fn2，n3，那么对于任意的整数n3，有Fn>n2，(2)其中=。证明容易验证2=1。当n=3时，由F3=2>=可知式(2)成立。假设式(2)对于所有的整数kn（n3）成立，即Fk>k2，kn，则Fn+1=FnFn1>n2n3=n3(1)=n32=n1，即当k=n1时式(2)也成立。由归纳法知式(2)对一切n3成立。证毕。定理1(Lame)设a,bN，a>b，使用在式(1)中的记号，则n<5log10b。证明在式(1)中，rn1，qn+12，qi1（1in），因此rn1=F2，rn12rn2=F3，rn2rn1rnF3F2=F4，br1r2Fn+1Fn=Fn+2，由此及式(2)得bn=，即log10bnlog10，这就是定理结论。证毕。定理2使用式(1)中的记号，记P0=1，P1=q1，Pk=qkPk1Pk2，k2，Q0=0，Q1=1，Qk=qkQk1Qk2，k2，则aQkbPk=(1)k1rk，k=1,2,,n。(3)证明当k=1时，式(3)成立。当k=2时，有Q2=q2Q1Q0=q2，P2=q2P1P0=q2q11，此时由式(1)得到aQ2bP2=aq2b(q2q11)=(abq1)q2b=r1q2b=r2，即式(3)成立。假设对于k<m（1mn）式(3)成立，由此假设及式(1)得到aQmbPm=a(qmQm1Qm2)b(qmPm1Pm2)=(aQm1bPm1)qm(aQm2bPm2)=(1)m2rm1qm(1)m3rm2=(1)m1(rm2rm1qm)=(1)m1rm，即式(3)当k=m时也成立。定理由归纳法得证。证毕。定理3使用式(1)中的记号，有rn=(a,b)。证明由第三节定理1，从式(1)可见rn=(rn1,rn)=(rn2,rn1)==(r1,r2)=(b,r1)=(a,b)。证毕。现在我们已经知道，利用辗转相除法可以求出整数x，y，使得axby=(a,b)。(4)为此所需要的除法次数是O(log10b)。但是如果只需要计算(a,b)而不需出使式(4)成立的整数x与y，则所需要的除法次数还可更少一些。例1设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a,b)。解下面的四个基本事实给出了证明：(ⅰ)若ab，则(a,b)=a；(ⅱ)若a=2a1，，1，则(a,b)=2(2a1,b1)；(ⅲ)若，则(a,b)=(a,b1)；(ⅳ)若。在实际计算过程中，若再灵活运用最大公约数的性质（例如第三节定理4的推论），则可使得求最大公约数的过程更为简单。例2用辗转相除法求(125,17)，以及x，y，使得125x17y=(125,17)。解做辗转相除法：125=7176，q1=7，r1=6，17=265，q2=2，r2=5，6=151，q3=1，r3=1，5=51，q4=5。由定理4，(125,17)=r3=1。利用定理2计算（n=3）P0=1，P1=7，P2=271=15，P3=1157=22，Q0=0，Q1=1，Q2=210=2，Q3=121=3，取x=(1)31Q3=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,162)=(177,81)=(96,81)=(3,81)=3。例4在m个盒子中放若干个硬币，然后以下述方式往这些盒子里继续放硬币：每一次在n（n<m）个盒子中各放一个硬币。证明：若(m,n)=1，那么无论开始时每个盒子中有多少硬币，经过若干次放硬币后，总可使所有盒子含有同样数量的硬币。解由于(m,n)=1，所以存在整数x，y，使得mxny=1。因此对于任意的自然数k，有1m(xkn)=n(kmy)，这样，当k充分大时，总可找出正整数x0，y0，使得1mx0=ny0。上式说明，如果放y0次（每次放n个），那么在使m个盒子中各放x0个后，还多出一个硬币。把这个硬币放入含硬币最少的盒子中（这是可以做到的），就使它与含有最多硬币的盒子所含硬币数量之差减少1。因此经过若干次放硬币后，必可使所有盒子中的硬币数目相同。习题五1.说明例1证明中所用到的四个事实的依据。2.用辗转相除法求整数x，y，使得1387x162y=(1387,162)。3.计算：(27090,21672,11352)。4.使用引理1中的记号，证明：(Fn+1,Fn)=1。5.若四个整数2836，4582，5164，6522被同一个大于1的整数除所得的余数相同，且不等于零，求除数和余数各是多少？6.记Mn=2n1，证明：对于正整数a，b，有(Ma,Mb)=M(a,b)。第六节算术基本定理在本节中，我们要介绍整数与素数的一个重要关系，即任何大于1的正整数都可以表示成素数的乘积。引理1任何大于1的正整数n可以写成素数之积，即n=p1p2pm，(1)其中pi（1im）是素数。证明当n=2时，结论显然成立。假设对于2nk，式(1)成立，我们来证明式(1)对于n=k1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立。如果k1是素数，式(1)显然成立。如果k1是合数，则存在素数p与整数d，使得k1=pd。由于2dk，由归纳假定知存在素数q1,q2,,ql，使得d=q1q2ql，从而k1=pq1q2ql。证毕。定理1(算术基本定理)任何大于1的整数n可以唯一地表示成n=，(2)其中p1,p2,,pk是素数，p1<p2<<pk，1,2,,k是正整数。证明由引理1，任何大于1的整数n可以表示成式(2)的形式，因此，只需证明表示式(2)的唯一性。假设pi（1ik）与qj（1jl）都是素数，p1p2pk，q1q2ql，(3)并且n=p1p2pk=q1q2ql，(4)则由第三节定理4推论1，必有某个qj（1jl），使得p1qj，所以p1=qj；又有某个pi（1ik），使得q1pi，所以q1=pi。于是，由式(3)可知p1=q1，从而由式(4)得到p2pk=q2ql。重复上述这一过程，得到k=l，pi=qi，1ik。证毕。定义1使用定理1中的记号，称n=是n的分解式，其中pi（1ik）是素数，p1<p2<<pk，i（1ik）是正整数。推论1使用式(2)中的记号，有(ⅰ)n的正因数d必有形式d=，iZ，0ii，1ik；(ⅱ)n的正倍数m必有形式m=M，MN，iN，ii，1ik。证明留作习题。推论2设正整数a与b的标准分解式是，其中pi（1ik），qi（1il）与ri（1is）是两两不相同的素数，i，i（1ik），i（1il）与i（1is）都是非负整数，则(a,b)=，i=min{i,i}，1ik，[a,b]=，i=max{i,i}，1ik。证明留作习题。为了方便，推论2常叙述为下面的形式：推论2设正整数a与b的标准分解式是，其中p1,p2,,pk是互不相同的素数，i，i（1ik）都是非负整数，则推论3设a，b，c，n是正整数，ab=cn，(a,b)=1，(5)则存在正整数u，v，使得a=un，b=vn，c=uv，(u,v)=1。证明设c=，其中p1,p2,,pk是互不相同的素数，i（1ik）是正整数。又设，其中I，i（1ik）都是非负整数。由式(5)及推论2可知min{i,i}=0，ii=ni，1ik，因此，对于每个i（1ik），等式i=ni，i=0与i=0，i=ni有且只有一个成立。这就证明了推论。证毕。例1写出51480的标准分解式。解我们有51480=225740=2212870=236435=2351287=2353429=23532143=233251113。例2设a，b，c是整数，证明：(ⅰ)(a,b)[a,b]=ab；(ⅱ)(a,[b,c])=[(a,b),(a,c)]。解为了叙述方便，不妨假定a，b，c是正整数。(ⅰ)设，其中p1,p2,,pk是互不相同的素数，i，i（1ik）都是非负整数。由定理1推论2，有由此知(a,b)[a,b]==ab；(ⅱ)设，其中p1,p2,,pk是互不相同的素数，i，i，i（1ik）都是非负整数。由定理1推论2，有，其中，对于1ik，有i=min{i,max{i,i}}，i=max{min{i,i},min{i,i}}，不妨设ii，则min{i,i}min{i,i}，所以i=min{i,i}=i，即(a,[b,c])=[(a,b),(a,c)]。注：利用定理1可以容易地处理许多像例2这样的问题。例3证明：（n2）不是整数。解设3k2n1<3k+1。对于任意的1in，2i13k，记2i1=Qi，QiZ，由第一节例5，知ik1。因为3k1Q1Q2Q2n1是整数，所以，如果N是整数，则存在整数Q，使得3k1Q1Q2Q2n1N=Q3k1Q1Q2Q2n1。由于3Q1Q2Q2n1，所以上式右端不是整数，这个矛盾说明N不能是整数。习题六1.证明定理1的推论1。2.证明定理1的推论2。3.写出22345680的标准分解式。4.证明：在1,2,,2n中任取n1数，其中至少有一个能被另一个整除。5.证明：（n2）不是整数。6.设a，b是正整数，证明：存在a1，a2，b1，b2，使得a=a1a2，b=b1b2，(a2,b2)=1，并且[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[x]；(ⅲ)若0x<1，则[x]=0；(ⅳ)[xy]=；(ⅴ)[x]=；(ⅵ){x}=。证明留作习题。定理2设a与b是正整数，则在1,2,,a中能被b整除的整数有个。证明能被b整除的正整数是b,2b,3b,，因此，若数1,2,,a中能被b整除的整数有k个，则kba<(k1)bk<k1k=。证毕。由定理2我们看到，若b是正整数，那么对于任意的整数a，有，即在带余数除法a=bqr，0r<b中有。定理3设n是正整数，n!=是n!的标准分解式，则i=。(1)证明对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则p(n!)=p(1)p(2)p(n)。以nj表示p(1),p(2),,p(n)中等于j的个数，那么p(n!)=1n12n23n3，(2)显然，nj就是在1,2,,n中满足pja并且pj+1a的整数a的个数，所以，由定理2有nj=。将上式代入式(2)，得到即式(1)成立。证毕。推论设n是正整数，则n!=，其中表示对不超过n的所有素数p求积。定理４设n是正整数，1kn1，则N。(3)若n是素数，则n，1kn1。证明由定理3，对于任意的素数p，整数n!，k!与(nk)!的标准分解式中所含的p的指数分别是。利用定理1可知，因此是整数。若n是素数，则对于1kn1，有(n,k!)=1，(n,(nk)!)=1(n,k!(nk)!)=1，由此及N，推出k!(nk)!(n1)!，从而n。证毕。例1求最大的正整数k，使得10k199!。解由定理3，199!的标准分解式中所含的5的幂指数是=47，所以，所求的最大整数是k=47。例2设x与y是实数，则[2x][2y][x][xy][y]。(4)解设x=[x]，0<1，y=[y]，0<1，则[x][xy][y]=2[x]2[y][]，(5)[2x][2y]=2[x]2[y][2][2]。(6)如果[]=0，那么显然有[][2][2]；如果[]=1，那么与中至少有一个不小于，于是[2][2]1=[]。因此无论[]=0或1，都有[][2][2]，由此及式(5)和式(6)可以推出式(4)。例3设n是正整数，则。(7)解首先，我们有所以。若上式中的等号不成立，即，(8)则存在整数a，使得，因此(2n1)21<(a22n1)2(2n1)2，所以a22n1=2n1a2=4n2。(9)但是，无论2a或2a，式(9)都不能成立，这个矛盾说明式(8)不能成立，即式(7)成立。例4设x是正数，n是正整数，则=[nx]。解设x=[x]，，0in1，则=n[x]i=n[x][n]=[n([x])]=[nx]。例5求[]的个位数。解由得===10A29976498=10A224498=10A2(251)498=10B2，（10）其中A和B都是整数。由于0<5<1，所以，由式(10)可知[]的个位数是1。注：一般地，如果A，BN，A2>B，<1，则由可以求出[]。例6设x和y是正无理数，，证明：数列[x],[2x],,[kx],与[y],[2y],,[my],(11)联合构成了整个正整数集合，而且，两个数列中的数互不相同。解显然x>1，y>1，并且xy。因此，在数列(11)中至多有一个数等于给定的正整数n，否则存在正整数k与m，使得n=[kx]=[my]。因为x与y都是无理数，所以我们有n<kx<n1，n<my<n1，n<km<n1，这是不可能的。下面证明，对于任意给定的正整数n，总可找到某个正整数k，使得n等于[kx]或者[ky]。假设不然，则存在p,qN，使得[px]<n<[(p1)x]，[qy]<n<[(q1)y]。于是（因为x和y是无理数），px<n<n1[(p1)x]<(p1)x，qy<n<n1[(q1)y]<(q1)y，，pq<n<n1<pq2，这是不可能的。习题七1.证明定理1。2.求使12347!被35k整除的最大的k值。3.设n是正整数，x是实数，证明：=n。4.设n是正整数，求方程x2[x2]=(x[x])2在[1,n]中的解的个数。5.证明：方程f(x)=[x][2x][22x][23x][24x][25x]=12345没有实数解。6.证明：在n!的标准分解式中，2的指数h=nk，其中k是n的二进制表示的位数码之和。第八节素数在第六节中我们已经证明了：每个正整数可以表示成素数幂的乘积。这就引出了一个问题：素数是否有无穷多个？如果有无穷多个，那么，作为无穷大量，素数个数具有怎样的性状？这是数论研究中的一个中心课题。本节要对这一问题作初步的研究。定义1对于正实数x，以(x)表示不超过x的素数个数。例如，(15)=6，(10.4)=4，(50)=15。定理1素数有无限多个。证明我们给出三个证明方法。证法Ⅰ假设只有k个素数，设它们是p1,p2,,pk。记N=p1p2pk1。由第一节定理2可知，N有素因数p，我们要说明ppi，1ik，从而得出矛盾。事实上，若有某个i，1ik，使得p=pi，则由pN=p1p2pk1推出p1，这是不可能的。因此在p1,p2,,pk之外又有一个素数p，这与假设是矛盾的。所以素数不可能是有限个。证法Ⅱ我们证明整数是两两互素的，从而由第六节引理1可知素数有无限多个。事实上，若m和n是整数，m>n0，则此处Q是整数。因此故证法Ⅲ假设只有有限个素数p1,p2,,pk。由第六节定理1，每个正整数可以写成n=，i1，1ik。由于，所以，对于任何正整数N，有。当N时，上式左端是一个无穷大量，右端是有限的，这个矛盾说明素数不能是有限多个。证毕。注1：形如（n=0,1,2,）的数称为Fermat数。Fermat曾经猜测它们都是素数。这是错误的，因为尽管F0，F1，F2，F3，F4都是素数，F5=却是合数。注2：将全体素数按大小顺序排列为p1=2，p2=3，p3=5，p4，，pn，，那么由第一个证明方法可以看