初等数论__整除理论

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 ) a b a b;(ii) a b, b c

2、a c;(iii) b ai, i = 1,2, , k b aixi a2X2akxk,此处 xi (i = 1,2, , k)是任意的整数；(iv) b a bc ac,此处c是任意的非零整数；(v) 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。不妨

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

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

5、 2 , d(4) = 3,。 问：d(1) d(2)d(1997)是否为偶数？解 对于n的每个约数d,都有n = d ,因此，n的正约数d与上是成对地出现的。只有当d = n,即n = d2时，d和;才是同一个数。故当且仅当n是完全平方数时，d(n)是奇数。因为 442 < 1997 < 452,所以在 d(i), d(2), , d(1997)中恰有 44 个奇数，故 d(i) d(2) d(1997)是偶数。例4 设凸2n边形M的顶点是Ai, A2, , A2n,点O在M的内部，用1,2, , 2n将M的 2n条边分别编号，又将 OAi, OA2, , OA2n也同样进行编号

6、，若把这些编号作为相应的线段 的长度，证明：无论怎么编号，都不能使得三角形OA1A2, OA2A3, , OA2nAl的周长都相等。解 假设这些三角形的周长都相等，记为s。则2ns = 3(1 22n) = 3n(2n 1),即2s = 3(2n 1), 因此2 3(2n 1),这是不可能的，这个矛盾说明这些三角形的周长不可能全都相等。例5设整数k 1,证明：(i )若 2k n < 2k M 1 a n, a 2k，则 2k| a；(ii)若 3k 2n 1 < 3k+，1 b n, 2b 1 3k，则 3k 12b 1。解(i )若2k|a,则存在整数q,使得a= q2k。显然

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

8、475767778798081828384858687888990919293949596979899100按以下步骤进行：(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的

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

10、数，且a1 a2an = 0, a1a2 an = n,贝U 4 n。解 如果21 n,则n, a1, a2, , an都是奇数。于是a a2an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以 2 n,即在a1, a2, , an中至少有一个偶数。如果只有一个 偶数，不妨设为a1，那么2|ai (2 i n)。此时有等式a2an = 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中有一

11、个是偶数，所以 8 n2 1。例9的结论虽然简单，却是很有用的。例如，使用例3中的记号，我们可以提出下面的 问题：问题 d(1)2 d(2)2d(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,所以ab a2, a3不可能都是奇数。由式(1), a1，a2, a3中只能有一个奇数，设 a1为奇数，a2, a3

12、为偶数，则存在整数 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,贝U m p mq np。3 .证明：任意给定的连续 39个自然数，其中至少存在一个自然数，使得这个自然数 的数字和能被11整除。4 .设p是n的最小素约

13、数，n = pn1, m > 1,证明：若p >3,'n ,则m是素数。5 .证明：存在无穷多个自然数n,使得n不能表示为a2 p(a >。是整数，p为素数) 的形式。第二节带余数除法在本节中，我们要介绍带余数除法及其简单应用。定理1(带余数除法)设a与b是两个整数，b 0,则存在唯一的两个整数 q和r,使a = bq r, 0 r < |b|。证明 存在性 若b a, a = bq, q Z,可取r = 0。若b | a,考虑集合A = a kb； k Z ,其中 Z 表示所有整数的集合，以后，仍使用此记号，并以N 表示所有正整数的集合。在集合A中有无限多个正

14、整数，设最小的正整数是r = a kob,则必有0 < r < |b|，(2)否则就有 r |b|° 因为 b | a,所以 r |b|。于是 r > |b|,即 a kob > |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 | &

15、lt; |b|，(3)因此 r r = o， 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 =a1mr1，or1 <m，b =b1mr2，or2 <m，则ax by和ab被m除的余数分别与rx r2y和门r2被m

16、除的余数相同。特别地，ak与 d被 m 除的余数相同。解由ax by = (a1m r1)x (b1m r2)y = (a1x b1y)m r1x r2y可知，若r1x 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 设a1, a2, , an为不全为零的整数，以yo表示集合A = y； y = a1x1anxn， xi Z， 1 i n 中的最小正数，则对于任何y A, yo y；特别地，yo ai, 1 i n。解设

17、yo =a1x1anxn,对任意的 y = a1xanxnA,由定理 1,存在 q,roZ ,使得y = qyo ro， o ro < yo 。因此ro = y qyo = a1(x1 qx1 )an(xn qxn ) A。如果ro o,那么，因为o < ro < yo,所以ro是A中比yo还小的正数，这与 yo的定义矛盾。所以ro = o,即 yo y。显然ai A (1 i n),所以yo整除每个ai (1 i n)。例 3 任意给出的五个整数中，必有三个数之和被3 整除。解 设这五个数是ai， i = 1, 2, 3, 4, 5，记ai = 3qiri， 0 ri &l

18、t; 3， i = 1, 2, 3, 4, 5。分别考虑以下两种情形：(i ) 若在ri, r2, , r5中数0, 1, 2都出现，不妨设 ri = 0, r2 = 1, r3 = 2,此时a1 a2 a3 = 3(q1 q2 q3) 3可以被 3 整除；(ii)若在ri, r2, , r5中数0, 1, 2至少有一个不出现，这样至少有三个门要取相同的值，不妨设r1=r2 =r3 =r(r = 0，1 或2)，此时a1 a2 a3 = 3(q1 q2 q3) 3r可以被 3 整除。例 4 设ao,ai,anZ, f(x) =anxnaixao,已知 f(0)与f(1)都不是 3的倍数，证明：

19、若方程f(x) = 0 有整数解，则3 f( i) = a0 aia2( i)nan 。解对任何整数x,都有x = 3qr， r = 0， i 或2， q Z。(i ) 若 r = 0,即 x = 3q, q Z ,贝Uf(x) = f(3q) = an(3q)nai(3q)a0 = 3Qi a0 = 3Qi f(0) ，其中Qi Z,由于f(0)不是3的倍数，所以f(x) 0;(11) 若 r = 1,即 x = 3q 1, q Z,则f(x) = f(3q i) = an(3qi)nai(3q i) a0= 3Q2 ana1 a0 = 3Q2 f(1)，其中Q2 Zo由于f(1)不是3的倍

20、数，所以f(x) 0。因此若f(x) = 0有整数解x,则必'是x = 3q 2 = 3q 1, q Z ,于是 0 = f(x) = f(3q 1) = an(3q1)na1(3q1)a0= 3Q3 a0 a1 a2( 1)nan = 3Q3 f( 1)，其中 Q3 Z。所以 3 f( 1) = a0 ai a2( 1)nan。例 5 证明：对于任意的整数n， f(n) = 3n5 5n3 7n 被 15 整除。解 对于任意的正整数n ，记n = 15qr， 0 r < 15。由例1，n2 = 15Q1 r1， n4 = 15Q2 r2，其中ri与r2分别是r2与r4被15除的

21、余数。以 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) 1

22、6。由第一节例题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 门，y = 3q2 r2, 0 门，r2 < 3。则存在Q1, R1, Q2, R2 Z,使得 33x = 9Q1 R1, y = 9Q2 R2 ,其中R1和R2被9除的余数分别与 门3和r23被9除的余数相同，即R1 = 0, 1 或 8, R2 = 0, 1 或 8。(4)因此x3 y3 = 9(Q1 Q2) R1 R2。又由式(4)可知，R R2被9除的余数只可能是 0

23、, 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的公约数中最大的一个

24、叫做a1, a2, , ak的最大公约数(或最大公因数)，记为(a1，a2,ak) o由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果(a1，a2, , ak) = 1,则称a1，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) = (|a1|,

25、 |a2|, , |ak|);(ii) (a, 1)= 1, (a, 0) = |a|, (a, a) = |a|;(iii) (a, b) = (b, a);(iv)若p是素数，a是整数，则(p, a) = 1或p a;(v) 若 a = bq r,贝U (a, b) = (b, r)。证明(i) (iv)留作习题。(v)由第一节定理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)o证毕。由定理1可知，在讨论(a

26、i, a2, , an)时，不妨假设ai, a2, , an是正整数，以后我们就维 持这一假设。定理2设ai, a2, , ak Z ,记kA = y；y = aixi , Xi Z, i k 。i 1如果yo是集合A中最小的正数，则 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,

27、 , ak)。这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的， 而且是所有公约数的倍数。推论 2 (mai, ma2, , mak) = |m|(ai, a2, , ak)。推论 3 记=(ai, a2, , ak),则特别地，(，_b_) = i。(a,b) (a,b)定理3 (ai, a2, , ak) = i的充要条件是存在整数xi, X2, , xk,使得aixi a2X2akXk = i。(i)证明 必要性 由定理2得到。充分性 若式(i)成立，如果(ai, a2, , ak) = d > i,那么由d ai (i i k)推出d aixi a2X2

28、 akxk = i,这是不可能的。所以有 (ai, a2, , ak) = I。证毕。定理4 对于任意的整数 a, b, c,下面的结论成立：(i) 由b ac及(a, b) = I可以推出b c;(ii)由 b c, a c 及(a, b) = i 可以推出 ab c。证明(i )若(a, b) = i,由定理2,存在整数x与y,使得ax by = i。因此acx bcy = c。(2)由上式及b ac得到b c。结论(i )得证；(ii) 若(a, b) = i,则存在整数x, y使得式(2)成立。由b c与a c得到ab ac, ab bc, 再由式(2)得到ab c。结论(ii)得证。

29、证毕。推论i若p是素数，则下述结论成立：(i) p ab p a或 p b;(ii) p a2 pa。证明留作习题。推论 2 若(a, b) = i,则(a, bc) = (a, c)。证明 设d是a与bc的一个公约数，则 d a, d bc,由式(2)得到，d|c,即d是a与c的公约数。另一方面，若 d是a与c的公约数，则它也是 a与bc的公约数。因此, 的公约数的集合，就是 a与bc的公约数的集合，所以(a, bc) = (a, c)。证毕。推论 3 若(a, bi) = 1, 1 i n,则(a, bib2 bn) = 1 o证明留作习题。定理5对于任意的n个整数ai, a2, , an

30、,记(ai, a2)=d2,(d2,a3)= d3, (dn 2, an 1) = dn 1, (dn1,an)=dn,则dn = (a1, a2, , an)。dn = (dn 1, an) dn 1 = (dn 2, an 1)dn 2 = (dn 3, an 2)证明由定理2的推论，我们有dnan,dndn1 ,dn1an1,dn1dn2,dnan,dnan1 ,dndn2,dn2an2,dn2dn3dnan,dnan1 ,dnan2,dn dn 3,d2=(a1, a2)dn an, dn an 1, , dn a2, dn a1,即dn是a1, a2, , an的一个公约数。依次另一

31、方面，对于 a1, a2, , an的任何公约数d,由定理2的推论及d2, , dn的定义, 得出da1,da2dd2,dd2,da3dd3,d dn 1, d and dn,因此dn是a1, a2, , an的公约数中的最大者，即dn = (a1, a2, , an)。证毕。例1证明：若n是正整数，则21n 4是既约分数。 14n 3解由定理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

32、, (ab 1)y bx),因此，一xay一 是既约分数。(ab 1)y bx例 2 证明：121 | n2 2n 12, n Z。解 由于 121 = 112, n2 2n 12 = (n 1)2 11,所以，若 112 (n 1)2 11,则11 (n 1)2,因此，由定理 4的推论1得到11 n 1, 112 (n 1)2。再由式得到112 11,这是不可能的。所以式(3)不能成立。注：这个例题的一般形式是：设p是素数，a, b是整数，则pk|(an b)k pk 1c,其中 c 是不被 p 整除的任意整数，k 是任意的大于1 的整数。例 3 设 a， b 是整数，且9 a2 ab b2

33、，(4)则 3 (a, b)。解 由式 (4)得到9 (a b)2 3ab 3 (a b)23ab3 (a b)23 a b(5)9 (a b)2。再由式(4)得到9 3ab 3 ab。因此，由定理4 的推论 1 ，得到3 a 或 3 b。若3 a,由式 得到3 b;若3 b,由(5)式也得到 3 a。因此，总有 3 a且3 b。由定理 2 的推论推出3 (a, b)。例4 设a和b是正整数，b > 2,则2b 112a 1。a < b,且2b1 2a 1 。(6)成立，则a = 1， b(ii)若 a2b 1 2a 12b 2a 2a = 1 ，即 b = 2，这是不可能的，所以

34、式= b ，且式(6)成立，则由式(6)得到2a(2b a 1) 2， (6)不成立。2a 1 (2a 1) 22a 1 22a1 22a 3，b = a = 1，这是不可能的，所以式(6)不成立。(iii)若 a > b,记 a = kb其中 Q 是整数。所以2a其中 Q 是整数。因此2kb1所以1 = 2kb + r= 2r(2b因此= (2br， 01)(21 = 2r(2kb1)Q 1)r < b,此时(k 1)b2(k 2)b1)= (2b11)Q(2r1) =(2b 1)Q，1)，2b 1在(i )中已经证明这是不可能的，所以式2a2b2r1，(6)不能成立。综上证得2

35、b 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, 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, ,

36、 ak。定理i下面的等式成立：(i) a, i = |a|, a, a = |a|;(ii) a, b = b, a;(iii) ai, a2, , ak = |ai|,|a2| , |ak|;(iv)若 a b,则a, b = |b|。证明留作习题。由定理i中的结论(iii)可知，在讨论ai, a2, , ak的最小公倍数时，不妨假定它们都是正 整数。在本节中总是维持这一假定。最小公倍数和最大公约数之间有一个很重要的关系，即下面的定理。定理2对任意的正整数a, b,有aba, b=。(a,b)证明 设m是a和b的一个公倍数，那么存在整数ki, k2,使得m = aki, m = bk2,因a

37、ki = bk2。于是b ,k2 °(a,b)由于(一a,b-) = i,所以由第三节定理4得到(a, b) (a,b)bb即 ki 1 ,(a, b) 1(a, b)其中t是某个整数。将上式代入式(i)得到(2)abm =t 。(a, b)另一方面，对于任意的整数 t,由式(2)所确定的m显然是a与b的公倍数，因此a与b 的公倍数必是式(2)中的形式，其中t是整数。当t = i时，得到最小公倍数aba, b =°(a,b)证毕。推论i两个整数的任何公倍数可以被它们的最小公倍数整除。证明 由式(2)可得证。证毕。这个推论说明：两个整数的最小公倍数不但是最小的正倍数，而且是另

38、外的公倍数的约推论2 设m, a, b是正整数，则ma, mb = ma, b。证明由定理2及第三节定理2的推论得到2 ,2 ,m abm abmabma, mb = = ma, b。(ma, mb) m(a, b) (a, b)证毕。定理3对于任意的n个整数ai, a2, , an,记ai, a2 = m2,m2,a3 = m3,mn2, an1 =mn1, mn 1,an = mn,ai, a2, , an = mn。证明我们有mn = mn 1, anmn 1 mn, an mn,mn 1 = mn 2, an 1mn 2 = mn 3, an 2mn 2 mn 1 mn, an mn,

39、 an 1mn 3 mn 2 mn, anmn, an 1m2 = a1, a2an mn,a2 mn, a1 mn,mn 1 mn,mn, an 2 mn,mn是a1, a2, , an的一个公倍数。2的推论及m2, , mn的定义，得另一方面，对于 a1, a2, , an的任何公倍数 m,由定理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的充要条件

40、是a1, a2, , an = aa2 an 。证明 必要性因为(a1, a2)= 1 ,由定理2得到a1 a2a1, a2 = a1a2。(a1 , a2)由(a1，a3)= (a2, a3)= 1及第三节定理 4推论3得到(a1a2, a3)= 1,由此及定理3得到a1, a2, a3 = a，a2, a3 = a a2, a3 = a1a2a3 。如此继续下去，就得到式(3)。充分性用归纳法证明。当 n = 2时，式(3)成为a，a2 = a1a2。由定理2a1a2aa2 = a1, a2 = (a1，a2) = 1,(a1 , a2 )即当n = 2时，充分性成立。假设充分性当n= k

41、时成立，即a1, a2, , ak = aa2 ak(ai, aj) = 1 , 1 i, j k, i j。对于整数a1, a2, , ak, ak + 1,使用定理3中的记号，由定理 3可知(4)a1, a2, , ak, ak + 1 = mk, ak + 1。其中mk = a1, a2, , ak。因此，如果a1, a2, , ak, ak + 1 = a1a2 akak + 1,那么，由此及式(4)得到mkak 1a1, a2, , ak, ak + 1 = mk, ak + 1 = a1a2 akak + 1,(mk,ak 1)mk=aia2 ak , (mk, ak i)显然mk

42、 aia2 ak, (mk, ak + 1) 1。所以若使上式成立，必是(mk, ak + i) = 1 ,(5)并且mk = aia2 ak 。(6)由式(6)与式推出(ai, ak + i) = 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。这一点在实际计算中的方法，验

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

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

45、, a2,n),显然,ak, ak + 1, an,an o(11)所以由定理3推论可知a1, , ak, ak + 1, , an,a1, a2, , an联合上式与式(11)得证。例3 设a, b, c是正整数，证明：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, ac2=a2b, ab2, abc, abc, b2c, bc2, a2c, abc, ac2=ab

46、c, a2b, a2c, b2c, b2a, c2a, c2b以及a, bb, cc, a = a, bb, a, bcc, a=ab, b2, ac, bcc, a=abc, a, b2c, 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 = 120, (a, b) = 24 , a

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

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

49、 3)成立，即Fk > k 2, k n,n 2Fn + 1 = F n F n 1 >即当k = n 1时式(2)也成立。n 3 = n 3（1） = n 3由归纳法知式（2）对一切n2 = n 1,3成立。证毕。当n = 3时，由定理1 （Lame）设a, b N, a > b,使用在式（1）中的记号，则n < 510g 1obo证明在式(1)中，rn1,qn+ 12,qi1(1 in),因此rn 1 = F2 ,rn 1 2rn 2 = F3 ,rn 2 rn 1 rn F3 F2 = F4 ,br 12 Fn + 1 Fn = Fn + 2 ,由此及式(2)得b

50、n=()' 2 7 即1og1ob n1og10- - n ,这就是定理结论。证毕。定理2使用式(1)中的记号，记Po = 1, P1 = q1, Pk = qkPk 1 Pk 2, k 2,Qo = 0, Q1 = 1, Qk = qkQk 1 Qk 2, k 2,则aQk bPk = ( 1)k 1rk, k = 1,2, , n。证明当k = 1时，式（3）成立。当k=2时，有Q2 = q2Q1 Qo = q2, P2 = q2P1 Po = q2q1 1,此时由式(1)得到aQ2 bP2 = aq2 b(q2q1 1) = (a bq1)q2 b = r1q2 b = r2,

51、即式(3)成立。假设又行1 k < m (1 m n)式(3)成立，由此假设及式 得到aQm bPm= a(qmQm 1 Qm 2) b(qmPm 1 Pm 2)=(aQm 1 bPm 1)qm (aQm 2 bPm 2)=(1) m2rm1qm (1)m3rm2=(1)m1(rm2 rm1qm)= (1)m 1rm,即式(3)当k = m时也成立。定理由归纳法得证。证毕。定理3使用式(1)中的记号，有rn = (a, b)o证明 由第三节定理1,从式(1)可见rn = (rn i, rn) = (rn 2, rn i)=(门，=(b, ri) = (a, b)。证毕。现在我们已经知道，

52、利用辗转相除法可以求出整数x, V,使得ax by = (a, b) 。(4)为此所需要的除法次数是O(logiob)。但是如果只需要计算(a, b)而不需要求出使式(4)成立的整数x与y,则所需要的除法次数还可更少一些。例1设a和b是正整数，那么只使用被2除的除法运算和减法运算就可以计算出(a, b)o解 下面的四个基本事实给出了证明：(i )若 a b,则(a, b) = a;(ii)若 a = 2 a1, 2 | q , b 2 b1, 2 | « ,1,则(a, b) = 2 (2a1, b1);(iii)若 2|a, b 2 b1, 2 |b1，贝U(a, b) = (a,

53、 b1)；a b 、(iv) 右 2|a, 2|b,则(a,b) (|2 |,b)。在实际计算过程中，若再灵活运用最大公约数的性质(例如第三节定理4的推论)，则可使得求最大公约数的过程更为简单。例2用辗转相除法求(125,17),以及x, V,使得125x 17y = (125, 17)。解做辗转相除法：125 = 717 6,中=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)Po= 1 , P1 = 7, P2 = 2 7 1 = 15, P3 = 1 15 7 = 22,Qo = 0, Q1 = 1,Q2 = 2 1 0 = 2,Q3 = 1 2 1 = 3,取 x = ( 1)3 1Q3 = 3, y =