初等数论整除理论

1、第一章整除理论最大公约数，最整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法, 小公倍数，算术基本定理以及它们的一些应用。第一节数的整除性定义1设a，b是整数，b 0,如果存在整数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下面的结论成立：(i )aba b;(丘)ab，bca c;(iii)

2、bai，i =1,2, , kb a1X1a2X2akxk，此处 xi (i = 1,2, k)是任意的整数；(iv)babc ac，此处c是任意的非零整数；(v )ba，a0|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

3、> 1， e2 > 1，使得d1 = ee2，因此，e1和e2也是 a的正的非平凡约数。这与 d1的最小性矛盾。所以 d1是素数。证毕。推论 任何大于1的合数a必有一个不超过 a的素约数。证明 使用定理2中的记号，有a = d1d2，其中d1 > 1是最小的素约数，所以 d12 a。 证毕。例1 设r是正奇数，证明：对任意的正整数n，有n 2|1r 2rn r。解对于任意的正整数 a，b以及正奇数k，有akbk = (ab)(ak1ak2bak3b2bk1) = (a b)q，其中q是整数。记s = 1r 2rn r，贝U2s = 2 (2r n r)(3r (n 1)r)(

4、n r 2r) = 2 (n 2)Q,其中Q是整数。若n 2 s,由上式知n 2 2,因为n 2 > 2，这是不可能的，所以 n 2|s。例2设A = di, d2, dk 是n的所有约数的集合，则B =讣出，診也是n的所有约数的集合。解 由以下三点理由可以证得结论：(i ) A和B的元素个数相同；(ii) 若di A,即卩di n,则 | n,反之亦然；di 1(iii) 若 di dj，贝Vdi dj例3 以d(n)表示n的正约数的个数， 例如：d(1) = 1 , d(2) = 2 , d(3) = 2 , d(4) = 3 ,。 问：d(1)d(2)d(1997)是否为偶数？解

5、对于n的每个约数d，都有n = d £，因此，n的正约数d与卫是成对地出现的。dd只有当d =n，即n = d2时，d和n才是同一个数。故当且仅当n是完全平方数时，d(n)是dd奇数。因为 442 < 1997 < 452,所以在 d(1), d(2), d(1997)中恰有 44 个奇数，故 d(1)d(2)d(1997)是偶数。例4 设凸2n边形M的顶点是A1, A2, , A2n，点0在M的内部，用1,2, , 2n将M的 2n条边分别编号，又将 0A1, 0A2, , 0A2n也同样进行编号，若把这些编号作为相应的线段 的长度，证明：无论怎么编号，都不能使得三角形

6、OA1A2, OA2A3, , 0A2nA1的周长都相等。解 假设这些三角形的周长都相等，记为s。则2ns = 3(1 22n) = 3n(2n 1),即2s = 3(2n 1),因此2 3(2n 1),这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。例5设整数k1，证明：(i )若2kn <2k 1, 1 a n, a 2k，则 2k | a;(i)若3k2n1 < 3k + 1, 1 b n, 2b 1 3k,贝U 3k | 2b 1。解(i )若2k|a,则存在整数q,使得a= q2k。显然q只可能是0或1。此时a= 0或 2k，这都是不可能的，所以2k| a;(i

7、i) 若3k|2b-1，则存在整数q,使得2b-1= q3k,显然q只可能是0, 1,或2。此时 2b-仁0, 3k,或2 3k，这都是不可能的，所以3k| 2b 1。例6 写出不超过100的所有的素数。解 将不超过100的正整数排列如下:-423-45-67詣-910111213141516171819202122232425262282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293

8、949596979899100按以下步骤进行：(i )删去1，剩下的后面的第一个数是 2, 2是素数；(ii) 删去2后面的被2整除的数，剩下的2后面的第一个数是 3, 3是素数；(iii) 再删去3后面的被3整除的数，剩下的3后面的第一个数是 5, 5是素数;(iv) 再删去5后面的被5整除的数，剩下的5后面的第一个数是 7, 7是素数;照以上步骤可以依次得到素数2, 3, 5, 7, 11,。由定理2推论可知，不超过 100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。在例6中所使用的寻找素数的方法，称为 Eratosthenes筛法。

9、它可以用来求出不超过任 何固定整数的所有素数。 在理论上这是可行的； 但在实际应用中，这种列出素数的方法需要 大量的计算时间，是不可取的。例7证明：存在无穷多个正整数a,使得n4 a (n = 1,2, 3,)都是合数。解取a = 4 k4，对于任意的n N,有n4 4k4 = (n2 2 k2)2 4n 2k2 = (n2 2 k2 2nk)( n2 2k2 2n k)。因为n22 k2 2nk = (n k)2 k2 k2,所以，对于任意的 k = 2, 3,以及任意的nN, n4 a是合数。例8 设a1, a2, an是整数，且a1 a2an = 0, a1a2 an = n,则4 n。

10、解 如果2丨n,则n, a1, a2, , an都是奇数。于是a1 a2an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2 n,即在a1, a2, , an中至少有一个偶数。如果只有一个偶数，不妨设为a1,那么2 | ai (2 i n )。此时有等式a2an = a1,在上式中，左端是(n1)个奇数之和，右端是偶数，这是不可能的，因此，在a1, a2, , an中至少有两个偶数，即 4 n。 例9若n是奇数，则8 n2解设n = 2k 1,则n21。1= (2 k1)2 1=4k(k1)。在k和k 1中有一个是偶数，所以8 n21。例9的结论虽然简单，却是很有用的。例如，使用例3中的记

11、号，我们可以提出下面的问题：d(1997)2被4除的余数是多少?问题 d(1)2d(2)2例10证明：方程无整数解。解 若ai, a2, a3都是奇数，则存在整数2 2 2ai2 a22 a32 = 1999Ai, A2, A3,使得(1)于是ai2 = 8Ai 1， a22 = 8A21， a32 = 8A31，ai2 a22 a32 = 8(Ai A2 A3)3。由于1999被8除的余数是7,所以ai，a2，a3不可能都是奇数。由式(1)，ai，a2，a3中只能有一个奇数，设 ai为奇数，a2，a3为偶数，则存在整数Ai,A2，A3,使得ai = 8Ai 1, a2 = 8A2 r, a3

12、 = 8A3 s,于是ai2 a22 a32 = 8(Ai A2 A3)其中r和s是整数，而且只能取值0或4。这样ai2 a221 rs,a32被8除的余数只可能是但1999被8除的余数是 乙所以这样的ai, a2, a3也不能使式(2)成立。综上证得所需要的结论。1. 证明定理1。2. 证明：若 m p mn pq，贝U m p mq np。3. 证明：任意给定的连续39个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被11整除。4. 设p是n的最小素约数，n = pni, ni > 1,证明：若p >3 n，则ni是素数。5. 证明：存在无穷多个自然数n,使得n不能表

13、示为a2 p ( a > 0是整数，p为素数)的形式。第二节带余数除法在本节中，我们要介绍带余数除法及其简单应用。定理1(带余数除法)设a与b是两个整数，b 0,则存在唯一的两个整数 q和r，使证明 存在性 若b a, a = bq, q乙可取r = 0。若b | a，考虑集合A = a kb；k Z ,其中Z表示所有整数的集合，以后，仍使用此记号，并以N表示所有正整数的集合。在集合A中有无限多个正整数，设最小的正整数是r = a kob，则必有0 < r < |b|,(2)否则就有 r |b|o 因为 b | a，所以 r |b|。于是 r > |b|，即卩 a ko

14、b > |b|， a kob |b| > 0，这样，在集合A中，又有正整数 a kob |b| < r，这与r的最小性矛盾。所以式(2)必定成立。 取q = ko知式(1)成立。存在性得证。唯一性 假设有两对整数 q ， r 与 q ， r 都使得式 (1)成立，即a = q b r = q b r ， o r , r < |b|，则(q q )b = r r ， |r r | < |b|，(3)因此 r r = o， r = r ，再由式 (3)得出 q = q ，唯一性得证。证毕。定义 1 称式(1)中的 q 是 a 被 b 除的商， r 是 a 被 b 除的

15、余数。由定理1可知，对于给定的整数 b,可以按照被b除的余数将所有的整数分成b类。在同一类中的数被 b 除的余数相同。 这就使得许多关于全体整数的问题可以归化为对有限个整 数类的研究。以后在本书中，除特别声明外，在谈到带余数除法时总是假定b 是正整数。例1 设a, b, x, y是整数，k和m是正整数，并且a =a1mr1， o r1 < m，b =b1mr2， o r2 < m，则 ax by 和 ab 被 m 除的余数分别与r1xr2y和门r2被m除的余数相同。特别地，ak与 r1被 m 除的余数相同。 解由ax by = (a1m r1)x (b1m r2)y = (a1x

16、b1y)m r1x r2y 可知，若rix r2y被m除的余数是r，即r1x r2y = qm r, o r < m,则ax by = (a1x b1y q)m r, o r < m,即 ax by 被 m 除的余数也是 r。 同样方法可以证明其余结论。例2设ai, a2, , an为不全为零的整数，以yo表示集合A = y；y = a1x1anxn, xi Z, 1 i n 中的最小正数，则对于任何 y A，yo y;特别地，yo a， 1 i n。解设 yo = a1X1anxn，对任意的 y = a1X1anxn A，由定理 1，存在 q, ro Z，使得y = qyoro，

17、 oro < yo 。因此ro = yqyo= a1(x1qx1 )an(xnqxn ) A。如果roo ，那么，因为o <ro < yo，所以ro是A中比yo 还小的正数，这与 yo 的定义矛盾。所以ro=o，即 yoy。显然aiA( 1in)，所以yo整除每个ai (1 i n)。例 3 任意给出的五个整数中，必有三个数之和被 3 整除。 解 设这五个数是 ai，i = 1, 2, 3, 4, 5，记ai = 3qi分别考虑以下两种情形：(i )若在 ri, r2,ri，0 ri < 3， i = 1, 2, 3, 4, 5。, r5 中数 0 ，a11，a22 都

18、出现，不妨设 a3 = 3(q1 q2 q3)r1 = 0，r2 = 1，r3 = 2，此时3这样至少有三个r i 要取相同的值，不妨设 r1 = r2 = r3 = r(r= 0， 1 或 2)，此时a1a2a3= 3(q1 q2q3)3r可以被 3 整除。例 4 设 a0, a1, an Z，f(x) = an nxa1xa0，已知f(0)与-明：若方程 f(x) = 0 有整数解，则3f( 1) =a0a1a2( 1)n an 。解对任何整数X，都有x = 3qr， r= 0， 1 或 2，qZ。(i ) 若 r = 0，即 x = 3q， q Z，则f(x) = f(3q) = an(

19、3q)na1(3q) a0 =3Q1a0 = 3Q1其中Q1 Z，由于f(0)不是3 1的倍数，所以f(x)0；(i ) 若 r = 1，即 x = 3q1， qZ，则f(x) = f(3q 1) =an(3q1)na1(3q1)a0= 3Q2 ana1a0 =3Q2f(1)，, r5 中数 0，2至少有一个不出现，1，其中 Q2f(1) 都不是 3 的倍数，证f(0)，可以被 3 整除；(ii)若在 ri, r2,Z。由于f(1)不是3的倍数，所以f(x) 0。因此若f(x) = 0有整数解x,则必是x = 3q 2 = 3q0 = f(x) = f(3q 1) = an(3q1)na1(3

20、q1)= 3Q3 a0 a1 a2( 1)nan = 3Q3 f( 1),其中 Q3 Z。所以 3 f( 1) = ao a1 a2( 1)nan。例5证明：对于任意的整数n，f(n) = 3n5 5n3 7n被15整除。解对于任意的正整数 n，记0 r < 15 。n = 15q r，1 ， q Z ，于是 a0n2 = 15Q1 r1其中ri与r2分别是r2与r4被15除的余数。以 R 表示 3n4 5n2 7 被 i5 除的余数， 被15除的余数就是rR被15除的余数，记为当r = 0时，显然R = 0，即对于n4 = 15Q2 r2，r = 1, 2, 3, 14 的情形，则 R

21、 就是 3r2R。15 3n5 5n3 7n。通过计算列出下表：5r1 7被 15除的余数，而且 f(n)由例 1，r =1, 142, 133, 124, 115, 106, 97, 8r1 =14911064r2 =11611061R =0010012100R=0000000这证明了结论。例6设n是奇数，则16 n4 4n2 11。解我们有n4 4n211 = (n21)( n25)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 =

22、3q1 门，y = 3q2 r2， 0 门，r2 < 3。则存在Q1, R1, Q2, R2 Z，使得x3 = 9Q1 R1，y = 9Q2 R2，其中R1和R2被9除的余数分别与 门3和23被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的个位数字

23、相同。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,

24、 a2, , ak是互素的(或互质的)；如果(ai, a j) = 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下面的等式成立：(i ) (a1, a2, , ak) = (|aU, |a2|, , |ak|);(ii) (a, 1)=1，(a, 0) = |a|，(a, a) = |a|;(iii) (a, b) = (b, a);(iv) 若p是素数，a是整数，则(p, a) = 1或

25、p a;(V ) 若 a = bq r，则(a, b) = (b, r)。证明(i )(iv )留作习题。(v )由第一节定理1可知，如果d a, d b，则有dr = a bq,反之，若d b, dr, 则d a = bq r。因此a与b的全体公约数的集合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相等，即(a, b) = (b, r)。证毕。由定理1可知，在讨论(ai, a2, , an)时，不妨假设ai, a2, , an是正整数，以后我们就维 持这一假设。定理2设ai, a2, ak Z，记kA = y; y =aiXi ，Xi z， i k 。i 1如果yo是集合A中最小

26、的正数，则 yo = (ai, a2, , ak)。证明 设d是ai, a2, , ak的一个公约数，则 d yo，所以d yo。另一方面，由第二节例 2知，yo也是ai, a2, , ak的公约数。因此yo是ai, a2, , ak的公约数中的最大者，即yo = ( ai,a2, ak)。证毕。推论I 设d是ai, a2, , ak的一个公约数，则 d (ai, a2, , ak)。这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的, 而且是所有公约数的倍数。推论 2 (mai, ma2, , mak) = |m|(ai, a2, , ak)。推论 3 记=(ai,

27、a2, ak)，贝U特别地,(a , b ) = i。(a,b) (a,b)定理3 (ai, a2, , ak) = i的充要条件是存在整数xi, X2, , xk,使得aixi a2x2akXk = i。(i)证明 必要性 由定理2得到。充分性 若式成立，如果(ai,a2, ak)= d > i,那么由dai(i ik)推出daixia2X2akxk= i，这是不可能的。所以有 (ai, a2, , ak) = i。证毕。定理4 对于任意的整数 a, b, c,下面的结论成立：(i ) 由b ac及(a, b) = 1可以推出b c;(ii)由 b c, a c 及(a, b) = 1

28、 可以推出 ab c。证明(i )若(a, b) = 1，由定理2,存在整数x与y,使得ax by = 1。因此acx bcy = c。(2)由上式及b ac得到b c。结论(i )得证；(i) 若(a, b) = 1,则存在整数x, y使得式 成立。由b c与a c得到ab ac, ab bc, 再由式 得到ab c。结论(i )得证。证毕。推论1若p是素数，则下述结论成立：(i ) p ab p a 或 p b;(i) p a2pa。证明留作习题。推论 2 若(a, b) = 1，则(a, bc) = (a, c)。证明 设d是a与bc的一个公约数，则 d a, d bc,由式(2)得到，

29、d|c,即d是a与c的公约数。另一方面，若d是a与c的公约数，则它也是 a与be的公约数。因此,的公约数的集合，就是a与be的公约数的集合，所以(a, be) = (a, e)。证毕。推论 3 若(a, bi) = 1， 1 i n,则(a, bib2 bn) = 1。 证明留作习题。依次定理5对于任意的n个整数ai, a2, , an,记(a1, a2)=d2， (d2, a3):=d3，(dn2, an1)=dn 1， (dndn =(a1, a2,an)。证明由定理2的推论，我们有dn=(dn 1, an)dnan，dndn1，dn1 =(dn2, an 1)dn1 an1， dn 1d

30、n2，dnan， dnan 1，dndn2，dn2 =(dn3, an 2)dn2 an2， dn 2dn3dnan， dnan 1，dnan2， dn dn 3，d2 =(a1, a2)dnan， dnan 1，dna2， dn a1，dn 是 a1,a2,an的一个公约数。则即1, an) = dn，另一方面，对于 a1, a2, , an的任何公约数d，由定理2的推论及d2, , dn的定义, 得出da1，da2dd2,dd2，da3dd3,d dn 1， d an d dn，因此dn是a1, a2, , an的公约数中的最大者，即dn = (a1, a2, , an)。证毕。例1证明：

31、若n是正整数，则 空 4是既约分数。 14n 3解由定理1得到(21 n 4, 14n 3) = (7 n 1, 14n 3) = (7 n 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)，因此， 1_翌是既约分数。(ab 1)y bx例 2 证明：121 |n2 2n 12，n Z。解 由于 121 = 112，n2 2n 12 = (n 1)211，所以，若112 (n 1)211，则11 (n 1)2，因此，由定理 4的推论1得到11 n

32、 1，112 (n 1)2。再由式得到112 11，这是不可能的。所以式(3)不能成立。注：这个例题的一般形式是：设p是素数，a，b是整数，则pk | (an b)k pk 1e，其中 c 是不被 p 整除的任意整数， k 是任意的大于 1 的整数。例 3 设 a， b 是整数，且9 a2abb2，(4)则 3 (a, b)。解 由式 (4) 得到9 (a b)2 3ab 3 (a b)2 3ab3 (ab)23 a b (5)9 (ab)2。再由式 (4)得到9 3ab 3 ab 。 因此，由定理 4 的推论 1，得到3 a 或 3 b。若3 a,由式 得到3 b;若3 b,由 式也得到3

33、a。因此，总有 3 a且3 b。 由定理 2 的推论推出 3 (a, b)。例 4 设 a 和 b 是正整数, b > 2,则 2b 1 | 2a 1。解(i )成立,则于是 a = 1 , b若 a < b,且2b1 2a1。2b 1 2a 12b 2a 22a(2ba 1) 2,2a1 (2a1) 22a 122a122a 3，于是 b = a = 1 ，这是不可能的，所以式(6)不成立。(iii)若 a> b，记 a =kb r ， 0r < b，此时2kb 1 =(2b1)(2(k 1)b 2(k 2)b1) = (2b 1)Q，其中 Q 是整数。所以2a1 =

34、 2kb + r1= 2r(2kb1 1)1= 2r(2b1)Q 1)1 = (2b1)Q(2r1)，其中 Q 是整数。因此2b 12a 12b1 2r 1，a = 1,即 b = 2,这是不可能的,所以式 (6)不成立。(ii)若a = b,且式成立，则由式(6)得到在(i )中已经证明这是不可能的，所以式不能成立。(6)综上证得 2b 1 |2a 1。习题三1. 证明定理1中的结论(i ) (iv )。2. 证明定理 2的推论 1, 推论 2 和推论 3。3. 证明定理 4 的推论 1 和推论 3。4. 设x,y Z, 17 2x 3y,证明：17 9x 5y。5. 设a,b, c N ,

35、 c无平方因子，a2 b2c,证明：a b。132n 16. 设 n 是正整数，求 C12n,C32n, ,C22nn 1的最大公约数。第四节最小公倍数定义1 整数ai, a2,中的最小的一个叫做定理,ak的公共倍数称为 ai, a2, , ak的公倍数。ai, a2, , ak的正公倍数 ai, a2, , ak的最小公倍数，记为ai, a2, , ak。1下面的等式成立：(i )(丘)(iii)(iv) 证明a, 1 = |a|，a, a = |a|;a, b = b, a；ai, a2, , ak = | ai|, |a2| , |ak|；若 a b，则a, b = |b|。留作习题。由

36、定理1中的结论(iii)可知，在讨论ai, a2, , ak的最小公倍数时，不妨假定它们都是正 整数。在本节中总是维持这一假定。最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。定理2对任意的正整数a, b,有ab a, b=(a,b)证明 设m是a和b的一个公倍数，那么存在整数ki, k2，使得m = aki, m = bk2，因此(1)aki = bk2。亠2。(a,b)由于(聶，盘=1，所以由第三节定理4得到盏1ki，即ki盏/，其中t是某个整数。将上式代入式 (1)得到abm = t。(a, b)另一方面，对于任意的整数t,由式(2)所确定的m显然是a与b的公倍数，因此a与b

37、的公倍数必是式 中的形式，其中t是整数。当t=1时，得到最小公倍数aba, b=(a,b)证毕。推论1两个整数的任何公倍数可以被它们的最小公倍数整除。 证明由式(2)可得证。证毕。而且是另外的公倍数的约这个推论说明：两个整数的最小公倍数不但是最小的正倍数， 数。推论2 设m, a, b是正整数，则ma, mb = ma, b。证明由定理2及第三节定理2的推论得到2 2m abm abmabma, mb = ma, b。(ma, mb) m(a, b) (a, b)证毕。定理ai, a2 = m2,m2, a3=:m3,，mn2, an i=mn i，mn i, anai,a2, an=mn。证

38、明我们有mn = mn i, anmn imn，an mn，mni = mn 2, an imn 2mn imn，anmn，ani mn imn，mn2 = mn 3, an 2mn 3mn 2mn，anmn，ani mn，an 2mn，m2 = ai, a2an mna2mn，ai mn，3对于任意的则=mn,n个整数ai, a2, an,记mn是ai, a2, an的一个公倍数。另一方面，对于 ai, a2, an的任何公倍数 m，由定理2的推论及m2, mn的定义，得m2 m， m3 m， mn m。mn是ai, a2, an最小的正的公倍数。证毕。推论 若m是整数ai, a2, an的

39、公倍数，则ai, a2, an m。留作习题。证明定理4整数ai, a2, an两两互素，即（ai, aj） = i，i i, j n，i j的充要条件是ai, a2, , an = aia2 an。 证明 必要性因为(ai, a2) = i，由定理2得到a a?ai, a2 = aia2。(ai,a2)由(ai, a3)= (a2, a3)= i及第三节定理 4推论3得到(aia2, a3)= i，由此及定理3得到ai, a2, a3 = ai, a2, a3 = ai a2, a3 = aia2a3 。如此继续下去，就得到式（3）。充分性 用归纳法证明。当 n = 2时，式 成为ai, a

40、2 = aia2。由定理2aa2aia2 = ai, a2 =(ai, a2) = i，(ai, a2 )即当n = 2时，充分性成立。假设充分性当n= k时成立，即ai, a2, ak = aia2对于整数ai, a2, ak, ak + i，使用定理ak(ai, aj) = i， i i, j k， i j。3中的记号，由定理 3可知ai, a2, ak, ak + i = mk, ak + i。其中 mk = ai, a2, ak。因此，如果ai, a2,ak, ak + i = aia2 akak + i,mkak i那么，由此及式（4）得到ai, a2,ak, ak + i = mk

41、, ak + i = aia2 akak + i，(mk , ak i )显然 mk a1a2 ak， (mk, ak + 1)1。所以若使上式成立，必是(mk, ak + 1) = 1，并且mk = a1a2 ak。由式(6)与式(5)推出(ai, ak + 1) = 1， 1 ik；由式及归纳假设推出(ai, aj) = 1，1 i, j k，i j。(8)综合式(7)与式(8)，可知当n =k 1时，充分性成立。由归纳法证明了充分性。证毕。mk=aia2 ak ,(mk, ak 1 )定理4有许多应用。例如，如果mi, m2, mk是两两互素的整数，那么，要证明m =i， 1 ik，都有

42、mi Q。这一点在实际计算m f(n)，n Z ”是否成立，可以用第二节例5若分别m1m2 mk整除某个整数 Q，只需证明对于每个 中是很有用的。对于函数f(x)，要验证命题“中的方法，验证"m f(r)，r = 0, 1, m验证“ mi f(门)，门=0, 1, mi 1， 1除法。后者的运算次数显然少于前者。例1 设a， b， c是正整数，证明：解由定理3和定理2有1”是否成立。这需要做 m次除法。但是,k”是否成立，则总共需要做 m1 m2a, b, c(ab, be, ca) = abc。a,bc a, b, c = a, b, c=(a,b, c)由第三节定理5和定理2的

43、推论，(ab, bc, ca) = (ab, (bc, ca) = (ab, c(a, b)= (ab,巫) a,b7(aba, b, abc)a, bab(a,b, c)a,bmk次(9)(10)联合式(9)与式(10)得到所需结论。对于任意的整数a1, a2,a1, a2,因为a1, a2, , an是 a1,an及整数k， 1,an = a1,ak, ak + 1,k n,证明：,ak,ak+ 1, an,an的公倍数，所以由定理2推论，推出再由定理3推论知另一方面，对于任意的所以由定理3推论可知a1,ak + 1,ai( 1aiia1,a1, a2, 联合上式与式(11)得证。例3 设

44、a， b， c是正整数，证明:,an,ak a1, a2, an，,an a1, a2, an，a1, ak, ak + 1, an a1, a2,n)，显然,ak, ak+ 1, an，a1, ak, ak + 1, an，a, b, cab, bc, ca = a, bb, cc, a。解由定理2推论2及例2,有a, b, c ab, bc, ca = a, b, cab, a, b, cbc, a, b, cca=a2b, ab2, abc, abc, b2c, bc2, a2c, abc, ac22222 22=a b, ab , abc, abc, b c, bc , a c, ab

45、c, ac ,an。(11)=abc, a2b, a2c, b2c, b2a, c2a, c2b以及a, bb, cc, a = a, bb, a, bcc, a2=ab, b , ac, bcc, a=abc, a, b c, a, acc, a, bcc, 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 = ab, a b。4. 求正整数 a， b，使得 a b = 12

46、0， (a, b) = 24， a, b = 144。5. 设a，b， c是正整数，证明：2 2a,b, c(a,b,c)。a, bb,cc, a (a,b)(b, c)(c, a)6. 设k是正奇数，证明：1 29 1k 2k9k。第五节辗转相除法本节要介绍一个计算最大公约数的算法一一辗转相除法，又称 中的一个重要方法，在其他数学分支中也有广泛的应用。定义1下面的一组带余数除法，称为辗转相除法。设a和b是整数，b 0,依次做带余数除法：a = bq1 r1，0 < r1 < |b|,b = aq2 2，0 <2 < r1，Euclid算法。它是数论rk 1 = rkq

47、k + 1rk + 1， 0 < rk + 1 < rk，(1)rn 2 = rn 1qn rn，0 < rn < rn-1 ，rn 1 = rnqn + 1。由于b是固定的，而且|b| > 门 > r2 >，所以式(1)中只包含有限个等式。下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。弓I理1用下面的方式定义 Fib on acci数列 Fn:F1 = F2 = 1， Fn = Fn 1Fn 2， n 3，那么对于任意的整数n 3,有n 2Fn >其中1,52证明容易验证当n = 3时，由1。2可知式(2)成立。假

48、设式(2)对于所有的整数k n (n 3)成立，即Fk > k 2，k n，Fn + 1 = Fn Fn 1 >3(1)=即当k = n 1时式也成立。由归纳法知式 对一切n 3成立。证毕。定理1 (Lame)设a, b N， a > b，使用在式(1)中的记号，则n < 5log 10b。证明在式中，G 1，qn + 12,(qi1 ( 1 in)，因此rn1=F2，rn 12rn 2 =F3，rn 2rn1 rnF3F2 = F4，br1r2Fn + 1Fn = Fn + 2 ，由此及式得bn=(1-5)2丿n即1、.51log10bn log 102n，5这就是定

49、理结论。证毕。定理2使用式(1)中的记号,记P0 =1，P1 =:5，Pk =:qkPk1 Pk 2，k2，Qo =:0，Q1 :=1,Qk =:qkQk1 Qk 2，k2，则aQk bPk = ( 1)k 1rk，k = 1,2, , n。Q2=q2Q1Qo = q2， P2 = q2P1P0=q2q11，此时由式(1)得到aQ2bP2 :=aq2b(q2q11)=(a bq1)q2b = r1q2 b = r2,即式成立。假设对于k < m(1m n)式成立,由此假设及式(1)得到证明当k = 1时，式成立。当k = 2时，有aQmbPm= a(qmQm 1Qm 2) b(qmPm 1Pm 2)=(aQm 1 bPm 1)qm (aQm 2 bPm 2)=(1)m2rm1qm( 1)m 3rm2=(1)m1(rm2rm 1qm) = (1)m 1rm，即式