初等数论_第一章_整除理论

1、第一章 整除理论整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。第一节 数的整除性定义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½

2、b Û ±a½±b；() a½b，b½c Þ a½c；() b½ai，i = 1, 2, L, k Þ b½a1x1 + a2x2 + L + akxk，此处xi（i = 1, 2, L, k）是任意的整数；() b½a Þ bc½ac，此处c是任意的非零整数；() b½a，a ¹ 0 Þ |b| £ |a|；b½a且|a| < |b| Þ a = 0。证明 留作习题。定义2 若整数a &#

3、185; 0，±1，并且只有约数 ±1和 ±a，则称a是素数（或质数）；否则称a为合数。以后在本书中若无特别说明，素数总是指正素数。定理2 任何大于1的整数a都至少有一个素约数。证明 若a是素数，则定理是显然的。若a不是素数，那么它有两个以上的正的非平凡约数，设它们是d1, d2, L, dk 。不妨设d1是其中最小的。若d1不是素数，则存在e1 > 1，e2 > 1，使得d1 = e1e2，因此，e1和e2也是a的正的非平凡约数。这与d1的最小性矛盾。所以d1是素数。证毕。推论 任何大于1的合数a必有一个不超过的素约数。证明 使用定理2中的记号，有a

4、 = d1d2，其中d1 > 1是最小的素约数，所以d12 £ a。证毕。例1 设r是正奇数，证明：对任意的正整数n，有n + 21r + 2 r + L + n r。解 对于任意的正整数a，b以及正奇数k，有ak + bk = (a + b)(ak - 1 - ak - 2b + ak - 3b2 - L + bk - 1) = (a + b)q，其中q是整数。记s = 1r + 2 r + L + n r，则2s = 2 + (2 r + n r) + (3 r + (n - 1)r) + L + (n r + 2 r) = 2 + (n + 2)Q，其中Q是整数。若n +

5、 2½s，由上式知n + 2½2，因为n + 2 > 2，这是不可能的，所以n + 2s。例2 设A = d1, d2, L, 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，L 。问：d(1) + d(2) + L + d(1997)是否为偶数？解 对于n的每个约数d，都有n =

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

7、L, OA2nA1的周长都相等。解 假设这些三角形的周长都相等，记为s。则2ns = 3(1 + 2 + L + 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 -

8、 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的正整数排列如下： 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43

9、 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98 99 100按以下步骤进行：() 删去1，剩下的后面的第一个数是2，2是素数；() 删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；() 再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；() 再删去5后面的被5整除的数，剩下的5后面的第一个数是

10、7，7是素数； L L照以上步骤可以依次得到素数2, 3, 5, 7, 11, L。由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数。在例6中所使用的寻找素数的方法，称为Eratosthenes筛法。它可以用来求出不超过任何固定整数的所有素数。在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的。例7 证明：存在无穷多个正整数a，使得n4 + a（n = 1, 2, 3, L）都是合数。解 取a = 4k4，对于任意的nÎN，有n4 + 4k4 = (n2 + 2k2)2

11、- 4n2k2 = (n2 + 2k2 + 2nk)(n2 + 2k2 - 2nk)。因为n2 + 2k2 - 2nk = (n - k)2 + k2 ³ k2，所以，对于任意的k = 2, 3, L 以及任意的nÎN，n4 + a是合数。例8 设a1, a2, L, an是整数，且a1 + a2 + L + an = 0，a1a2Lan = n，则4½n。解 如果2n，则n, a1, a2, L, an都是奇数。于是a1 + a2 + L + an是奇数个奇数之和，不可能等于零，这与题设矛盾，所以2½n，即在a1, a2, L, an中至少有一个偶数。

12、如果只有一个偶数，不妨设为a1，那么2ai（2 £ i £ n）。此时有等式a2 + L + an = -a1，在上式中，左端是(n - 1)个奇数之和，右端是偶数，这是不可能的，因此，在a1, a2, L, 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 +

13、 L + 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 = 8

14、A3 + 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，证明：若

15、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中有无限多个正

16、整数，设最小的正整数是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 ¢

17、62;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是

18、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 = (a

19、1m + 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, L, an为不全为零的整数，以y0表示集合A = y；y = a1x1 + L + anxn，xiÎZ，1 £ i £ n 中的最小正数，则对于任何yÎA

20、，y0½y；特别地，y0½ai，1 £ i £ n。解 设y0 = a1x1¢ + L + anxn¢，对任意的y = a1x1 + L + anxnÎA，由定理1，存在q, r0ÎZ，使得y = qy0 + r0，0 £ r0 < y0 。因此r0 = y - qy0 = a1(x1 - qx1¢) + L + an(xn - qxn¢)ÎA。如果r0 ¹ 0，那么，因为0 < r0 < y0，所以r0是A中比y0还小的正数，这与y0的定义矛盾。

21、所以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, L, r5中数0，1，2都出现，不妨设r1 = 0，r2 = 1，r3 = 2，此时a1 + a2 + a3 = 3(q1 + q2 + q3) + 3可以被3整除；(

22、) 若在r1, r2, L, 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, L, anÎZ，f(x) = anxn + L + a1x + a0 ，已知f(0)与f(1)都不是3的倍数，证明：若方程f(x) = 0有整数解，则3½f(-1) = a0 - a1 + a2 - L + (-1)nan 。解 对任何整数x，都有x = 3q + r，r = 0，1或2，qÎZ。

23、() 若r = 0，即x = 3q，qÎZ，则f(x) = f(3q) = an(3q)n + L + 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 + L + a1(3q + 1) + a0= 3Q2 + an + L + a1 + a0 = 3Q2 + f(1)，其中Q2ÎZ。由于f(1)不是3的倍数，所以f(x) ¹ 0。因此若

24、f(x) = 0有整数解x，则必是x = 3q + 2 = 3q¢ - 1，q ¢ÎZ，于是0 = f(x) = f(3q ¢ - 1) = an(3q ¢ - 1)n + L + a1(3q ¢ - 1) + a0= 3Q3 + a0 - a1 + a2 - L + (- 1)nan = 3Q3 + f(-1)，其中Q3ÎZ。所以3½f(-1) = a0 - a1 + a2 - L + (-1)nan 。例5 证明：对于任意的整数n，f(n) = 3n5 + 5n3 + 7n被15整除。解 对于任意的正整数n，记

25、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, L, 14的情形，通过计算列出下表： r = 1, 14 2, 13 3, 12 4, 11 5, 10 6, 9 7, 8r1

26、 = 1 4 9 1 10 6 4r2 = 1 1 6 1 10 6 1R = 0 0 10 0 12 10 0R¢= 0 0 0 0 0 0 0这证明了结论。例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 = 3

27、q2 + 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 +

28、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, L, ak的公共约数称为a1, a2, L, ak的公约数。不全为零的整数a1, a2, L, ak的公约数中最大的一个叫做a1, a2, L, ak的最大公约数（或最大公因数），记为(a1, a2

29、, L, ak)。由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。如果(a1, a2, L, ak) = 1，则称a1, a2, L, ak是互素的（或互质的）；如果(ai, a j) = 1，1 £ i, j £ k，i ¹ j，则称a1, a2, L, ak是两两互素的（或两两互质的）。显然，a1, a2, L, ak两两互素可以推出(a1, a2, L, ak) = 1，反之则不然，例如(2, 6, 15) = 1，但(2, 6) = 2。定理1 下面的等式成立：() (a1, a2, L, ak) = (|a1|, |a2|,

30、L, |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

31、, r)。证毕。由定理1可知，在讨论(a1, a2, L, an)时，不妨假设a1, a2, L, an是正整数，以后我们就维持这一假设。定理2 设a1, a2, L, akÎZ，记A = y；y =，xiÎZ，1 £ i £ k 。如果y0是集合A中最小的正数，则y0 = (a1, a2, L, ak)。证明 设d是a1, a2, L, ak的一个公约数，则d½y0，所以d £ y0。另一方面，由第二节例2知，y0也是a1, a2, L, ak的公约数。因此y0是a1, a2, L, ak的公约数中的最大者，即y0 = ( a1,

32、a2, L, ak)。证毕。推论1 设d是a1, a2, L, ak的一个公约数，则d½(a1, a2, L, ak)。这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。推论2 (ma1, ma2, L, mak) = |m|(a1, a2, L, ak)。推论3 记d = (a1, a2, L, ak)，则= 1，特别地, = 1。定理3 (a1, a2, L, ak) = 1的充要条件是存在整数x1, x2, L, xk，使得a1x1 + a2x2 + L + akxk = 1。 (1)证明 必要性 由定理2得到。充分性 若式(1

33、)成立，如果 (a1, a2, L, ak) = d > 1，那么由d½ai（1 £ i £ k）推出d½a1x1 + a2x2 + L + akxk = 1，这是不可能的。所以有(a1, a2, L, 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

34、 = 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&#

35、189;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, b1b2Lbn) = 1。证明 留作习题。定理5 对于任意的n个整数a1, a2, L, an，记(a1, a2) = d2，(d2, a3) = d3，L，(dn - 2, an - 1) = dn - 1，(dn - 1, an) = dn，则dn = (a1, a2, L, an)。证明

36、 由定理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 -

37、 2，dn½dn - 3，L L d2 = (a1, a2) Þ dn½an，dn½an - 1，L，dn½a2，dn½a1，即dn是a1, a2, L, an的一个公约数。另一方面，对于a1, a2, L, an的任何公约数d，由定理2的推论及d2, L, dn的定义，依次得出 d½a1，d½a2 Þ d½d2， d½d2，d½a3 Þ d½d3，L Ld½dn - 1，d½an Þ d½dn，因此dn是a1, a

38、2, L, an的公约数中的最大者，即dn = (a1, a2, L, 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 = (

39、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 + 3

40、ab Þ 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 +

41、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，这是不可能的，所以式(

42、6)不成立。() 若a > b，记a = kb + r，0 £ r < b，此时2kb - 1 = (2b - 1)(2(k - 1)b + 2(k - 2)b + L + 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)不

43、能成立。综上证得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, L, ak的公共倍数称为a1, a2, L, ak的公倍数。a1, a2, L, ak的正公倍数中的最小的一个叫做a1, a2, L, ak的最小公倍数，记为

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

45、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 = ma, b。证明 由定理2及第三节定理2的推论得到ma, mb = ma, b

46、。证毕。定理3 对于任意的n个整数a1, a2, L, an，记a1, a2 = m2，m2, a3 = m3，L，mn-2, an-1 = mn-1，mn-1, an = mn，则a1, a2, L, 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½

47、mn，an-1½mn，an-2½mn，L L m2 = a1, a2 Þ an½mn，L，a2½mn，a1½mn，即mn是a1, a2, L, an的一个公倍数。另一方面，对于a1, a2, L, an的任何公倍数m，由定理2的推论及m2, L, mn的定义，得m2½m，m3½m，L，mn½m。即mn是a1, a2, L, an最小的正的公倍数。证毕。推论 若m是整数a1, a2, L, an的公倍数，则a1, a2, L, an½m 。证明 留作习题。定理4 整数a1, a2, L, an两两

48、互素，即(ai, aj) = 1，1 £ i, j £ n，i ¹ j的充要条件是a1, a2, L, an = a1a2Lan 。 (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,

49、 a2 =Þ (a1, a2) = 1，即当n = 2时，充分性成立。假设充分性当n = k时成立，即a1, a2, L, ak = a1a2Lak Þ (ai, aj) = 1，1 £ i, j £ k，i ¹ j。对于整数a1, a2, L, ak, ak + 1，使用定理3中的记号，由定理3可知a1, a2, L, ak, ak + 1 = mk, ak + 1。 (4)其中mk = a1, a2, L, ak。因此，如果a1, a2, L, ak, ak + 1 = a1a2Lakak + 1，那么，由此及式(4)得到a1, a2, L

50、, ak, ak + 1 = mk, ak + 1 = a1a2Lakak + 1，即= a1a2Lak ，显然mk £ a1a2Lak，(mk, ak + 1) ³ 1。所以若使上式成立，必是(mk, ak + 1) = 1， (5)并且mk = a1a2Lak 。 (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时，充分性成立。由归纳

51、法证明了充分性。证毕。定理4有许多应用。例如，如果m1, m2, L, mk是两两互素的整数，那么，要证明m = m1m2Lmk整除某个整数Q，只需证明对于每个i，1 £ i £ k，都有mi½Q。这一点在实际计算中是很有用的。对于函数f(x)，要验证命题“m½f(n)，nÎZ”是否成立，可以用第二节例5中的方法，验证“m½f(r)，r = 0, 1, L, m - 1”是否成立。这需要做m次除法。但是，若分别验证“mi½f(ri)，ri = 0, 1, L, mi - 1，1 £ i £ k”是否成立，

52、则总共需要做m1 + m2 + L + mk次除法。后者的运算次数显然少于前者。例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, L, an及整数k，1 £ k £ n，证明：a1, a2, L, an = a1, L, ak,ak + 1, L, an解 因为a1,

53、 a2, L, an是a1, L, ak, ak + 1, L, an的公倍数，所以由定理2推论，推出a1, L, ak½a1, a2, L, an，ak + 1, L, an½a1, a2, L, an，再由定理3推论知a1, L, ak, ak + 1, L, an½a1, a2, L, an。 (11)另一方面，对于任意的ai（1 £ i £ n），显然ai½a1, L, ak, ak + 1, L, an，所以由定理3推论可知a1, a2, L, an½a1, L, ak, ak + 1, L, an，联合上式与式(

54、11)得证。例3 设a，b，c是正整数，证明：a, b, cab, bc, ca = a, bb, cc, a。解 由定理2推论2及例2，有a, b, cab, 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= abc, a2b, a2c, b2c, b2a, c2a, c2b以及a, bb, cc, a = a, bb, a, bcc, a= ab, b2, ac, bcc, a=

55、 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, b = 144。5. 设a，b，c是正整数，证明：。 6. 设k是正奇数，证明：1 + 2 + L + 9½1k + 2k + L + 9k。第五节 辗转相

56、除法本节要介绍一个计算最大公约数的算法辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。定义1 下面的一组带余数除法，称为辗转相除法。设a和b是整数，b ¹ 0，依次做带余数除法： a = bq1 + r1， 0 < r1 < |b|， b = r1q2 + r2， 0 < r2 < r1 ，L L rk - 1 = rkqk + 1 + rk + 1，0 < rk + 1 < rk ， (1)L L rn - 2 = rn - 1qn + rn， 0 < rn < rn-1 ， rn - 1

57、= rnqn + 1 。由于b是固定的，而且|b| > r1 > r2 > L ，所以式(1)中只包含有限个等式。下面，我们要对式(1)所包含的等式的个数，即要做的带余数除法的次数进行估计。引理1 用下面的方式定义Fibonacci数列Fn：F1 = F2 = 1，Fn = Fn - 1 + Fn - 2，n ³ 3，那么对于任意的整数n ³ 3，有Fn > a n - 2， (2)其中a =。证明 容易验证a 2 = a + 1。当n = 3时，由F3 = 2 >= a可知式(2)成立。假设式(2)对于所有的整数k £ n（n &#

58、179; 3）成立，即Fk > a k - 2，k £ n，则Fn + 1 = Fn + Fn - 1 > a n - 2 + a n - 3 = a n - 3(a + 1) = a n - 3a 2 = a 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）

59、，因此rn ³ 1 = F2 ，rn - 1 ³ 2rn ³ 2 = F3 ，rn - 2 ³ rn - 1 + rn ³ F3 + F2 = F4 ，L Lb ³ r1 + r2 ³ Fn + 1 + Fn = Fn + 2 ，由此及式(2)得b ³ an =，即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, L, n 。 (3)证明 当k = 1时，式(3)成立。当k = 2时，有Q2 =