1、第一章整除理論最大公約數(shù)，最整除性理論是初等數(shù)論的基礎(chǔ)。本章要介紹帶余數(shù)除法，輾轉(zhuǎn)相除法, 小公倍數(shù)，算術(shù)基本定理以及它們的一些應(yīng)用。第一節(jié)數(shù)的整除性定義1設(shè)a，b是整數(shù)，b 0,如果存在整數(shù)c,使得a = bc成立，則稱a被b整除，a是b的倍數(shù)，b是a的約數(shù)(因數(shù)或除數(shù))，并且使用記號(hào) b a； 如果不存在整數(shù) c使得a = bc成立，則稱a不被b整除，記為b | a。顯然每個(gè)非零整數(shù) a都有約數(shù) 1， a，稱這四個(gè)數(shù)為a的平凡約數(shù)，a的另外的約數(shù) 稱為非平凡約數(shù)。被2整除的整數(shù)稱為偶數(shù)，不被 2整除的整數(shù)稱為奇數(shù)。定理1下面的結(jié)論成立：(i )aba b;(丘)ab，bca c;(iii)

2、bai，i =1,2, , kb a1X1a2X2akxk，此處 xi (i = 1,2, k)是任意的整數(shù)；(iv)babc ac，此處c是任意的非零整數(shù)；(v )ba，a0|b|a|； b a 且|a| < |b|a = 0。證明留作習(xí)題。定義2若整數(shù)a 0，1，并且只有約數(shù) 1和 a，則稱a是素?cái)?shù)(或質(zhì)數(shù))；否則稱a為合數(shù)。以后在本書中若無特別說明，素?cái)?shù)總是指正素?cái)?shù)。定理2 任何大于1的整數(shù)a都至少有一個(gè)素約數(shù)。證明 若a是素?cái)?shù)，則定理是顯然的。若a不是素?cái)?shù)，那么它有兩個(gè)以上的正的非平凡約數(shù)，設(shè)它們是d1, d2, , dk。不妨設(shè)d1是其中最小的。若 d1不是素?cái)?shù)，則存在 e1

3、> 1， e2 > 1，使得d1 = ee2，因此，e1和e2也是 a的正的非平凡約數(shù)。這與 d1的最小性矛盾。所以 d1是素?cái)?shù)。證畢。推論 任何大于1的合數(shù)a必有一個(gè)不超過 a的素約數(shù)。證明 使用定理2中的記號(hào)，有a = d1d2，其中d1 > 1是最小的素約數(shù)，所以 d12 a。 證畢。例1 設(shè)r是正奇數(shù)，證明：對(duì)任意的正整數(shù)n，有n 2|1r 2rn r。解對(duì)于任意的正整數(shù) a，b以及正奇數(shù)k，有akbk = (ab)(ak1ak2bak3b2bk1) = (a b)q，其中q是整數(shù)。記s = 1r 2rn r，貝U2s = 2 (2r n r)(3r (n 1)r)(

4、n r 2r) = 2 (n 2)Q,其中Q是整數(shù)。若n 2 s,由上式知n 2 2,因?yàn)閚 2 > 2，這是不可能的，所以 n 2|s。例2設(shè)A = di, d2, dk 是n的所有約數(shù)的集合，則B =訃出，診也是n的所有約數(shù)的集合。解 由以下三點(diǎn)理由可以證得結(jié)論：(i ) A和B的元素個(gè)數(shù)相同；(ii) 若di A,即卩di n,則 | n,反之亦然；di 1(iii) 若 di dj，貝Vdi dj例3 以d(n)表示n的正約數(shù)的個(gè)數(shù)， 例如：d(1) = 1 , d(2) = 2 , d(3) = 2 , d(4) = 3 ,。 問：d(1)d(2)d(1997)是否為偶數(shù)？解

5、對(duì)于n的每個(gè)約數(shù)d，都有n = d £，因此，n的正約數(shù)d與衛(wèi)是成對(duì)地出現(xiàn)的。dd只有當(dāng)d =n，即n = d2時(shí)，d和n才是同一個(gè)數(shù)。故當(dāng)且僅當(dāng)n是完全平方數(shù)時(shí)，d(n)是dd奇數(shù)。因?yàn)?442 < 1997 < 452,所以在 d(1), d(2), d(1997)中恰有 44 個(gè)奇數(shù)，故 d(1)d(2)d(1997)是偶數(shù)。例4 設(shè)凸2n邊形M的頂點(diǎn)是A1, A2, , A2n，點(diǎn)0在M的內(nèi)部，用1,2, , 2n將M的 2n條邊分別編號(hào)，又將 0A1, 0A2, , 0A2n也同樣進(jìn)行編號(hào)，若把這些編號(hào)作為相應(yīng)的線段 的長度，證明：無論怎么編號(hào)，都不能使得三角形

6、OA1A2, OA2A3, , 0A2nA1的周長都相等。解 假設(shè)這些三角形的周長都相等，記為s。則2ns = 3(1 22n) = 3n(2n 1),即2s = 3(2n 1),因此2 3(2n 1),這是不可能的，這個(gè)矛盾說明這些三角形的周長不可能全都相等。例5設(shè)整數(shù)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,則存在整數(shù)q,使得a= q2k。顯然q只可能是0或1。此時(shí)a= 0或 2k，這都是不可能的，所以2k| a;(i

7、i) 若3k|2b-1，則存在整數(shù)q,使得2b-1= q3k,顯然q只可能是0, 1,或2。此時(shí) 2b-仁0, 3k,或2 3k，這都是不可能的，所以3k| 2b 1。例6 寫出不超過100的所有的素?cái)?shù)。解 將不超過100的正整數(shù)排列如下:-423-45-67詣-910111213141516171819202122232425262282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293

8、949596979899100按以下步驟進(jìn)行：(i )刪去1，剩下的后面的第一個(gè)數(shù)是 2, 2是素?cái)?shù)；(ii) 刪去2后面的被2整除的數(shù)，剩下的2后面的第一個(gè)數(shù)是 3, 3是素?cái)?shù)；(iii) 再刪去3后面的被3整除的數(shù)，剩下的3后面的第一個(gè)數(shù)是 5, 5是素?cái)?shù);(iv) 再刪去5后面的被5整除的數(shù)，剩下的5后面的第一個(gè)數(shù)是 7, 7是素?cái)?shù);照以上步驟可以依次得到素?cái)?shù)2, 3, 5, 7, 11,。由定理2推論可知，不超過 100的合數(shù)必有一個(gè)不超過10的素約數(shù)，因此在刪去7后面被7整除的數(shù)以后，就得到了不超過100的全部素?cái)?shù)。在例6中所使用的尋找素?cái)?shù)的方法，稱為 Eratosthenes篩法。

9、它可以用來求出不超過任 何固定整數(shù)的所有素?cái)?shù)。 在理論上這是可行的； 但在實(shí)際應(yīng)用中，這種列出素?cái)?shù)的方法需要 大量的計(jì)算時(shí)間，是不可取的。例7證明：存在無窮多個(gè)正整數(shù)a,使得n4 a (n = 1,2, 3,)都是合數(shù)。解取a = 4 k4，對(duì)于任意的n N,有n4 4k4 = (n2 2 k2)2 4n 2k2 = (n2 2 k2 2nk)( n2 2k2 2n k)。因?yàn)閚22 k2 2nk = (n k)2 k2 k2,所以，對(duì)于任意的 k = 2, 3,以及任意的nN, n4 a是合數(shù)。例8 設(shè)a1, a2, an是整數(shù)，且a1 a2an = 0, a1a2 an = n,則4 n。

10、解 如果2丨n,則n, a1, a2, , an都是奇數(shù)。于是a1 a2an是奇數(shù)個(gè)奇數(shù)之和，不可能等于零，這與題設(shè)矛盾，所以2 n,即在a1, a2, , an中至少有一個(gè)偶數(shù)。如果只有一個(gè)偶數(shù)，不妨設(shè)為a1,那么2 | ai (2 i n )。此時(shí)有等式a2an = a1,在上式中，左端是(n1)個(gè)奇數(shù)之和，右端是偶數(shù)，這是不可能的，因此，在a1, a2, , an中至少有兩個(gè)偶數(shù)，即 4 n。 例9若n是奇數(shù)，則8 n2解設(shè)n = 2k 1,則n21。1= (2 k1)2 1=4k(k1)。在k和k 1中有一個(gè)是偶數(shù)，所以8 n21。例9的結(jié)論雖然簡單，卻是很有用的。例如，使用例3中的記

11、號(hào)，我們可以提出下面的問題：d(1997)2被4除的余數(shù)是多少?問題 d(1)2d(2)2例10證明：方程無整數(shù)解。解 若ai, a2, a3都是奇數(shù)，則存在整數(shù)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除的余數(shù)是7,所以ai，a2，a3不可能都是奇數(shù)。由式(1)，ai，a2，a3中只能有一個(gè)奇數(shù)，設(shè) ai為奇數(shù)，a2，a3為偶數(shù)，則存在整數(shù)Ai,A2，A3,使得ai = 8Ai 1, a2 = 8A2 r, a3

12、 = 8A3 s,于是ai2 a22 a32 = 8(Ai A2 A3)其中r和s是整數(shù)，而且只能取值0或4。這樣ai2 a221 rs,a32被8除的余數(shù)只可能是但1999被8除的余數(shù)是 乙所以這樣的ai, a2, a3也不能使式(2)成立。綜上證得所需要的結(jié)論。1. 證明定理1。2. 證明：若 m p mn pq，貝U m p mq np。3. 證明：任意給定的連續(xù)39個(gè)自然數(shù)，其中至少存在一個(gè)自然數(shù)，使得這個(gè)自然數(shù)的數(shù)字和能被11整除。4. 設(shè)p是n的最小素約數(shù)，n = pni, ni > 1,證明：若p >3 n，則ni是素?cái)?shù)。5. 證明：存在無窮多個(gè)自然數(shù)n,使得n不能表

13、示為a2 p ( a > 0是整數(shù)，p為素?cái)?shù))的形式。第二節(jié)帶余數(shù)除法在本節(jié)中，我們要介紹帶余數(shù)除法及其簡單應(yīng)用。定理1(帶余數(shù)除法)設(shè)a與b是兩個(gè)整數(shù)，b 0,則存在唯一的兩個(gè)整數(shù) q和r，使證明 存在性 若b a, a = bq, q乙可取r = 0。若b | a，考慮集合A = a kb；k Z ,其中Z表示所有整數(shù)的集合，以后，仍使用此記號(hào)，并以N表示所有正整數(shù)的集合。在集合A中有無限多個(gè)正整數(shù)，設(shè)最小的正整數(shù)是r = a kob，則必有0 < r < |b|,(2)否則就有 r |b|o 因?yàn)?b | a，所以 r |b|。于是 r > |b|，即卩 a ko

14、b > |b|， a kob |b| > 0，這樣，在集合A中，又有正整數(shù) a kob |b| < r，這與r的最小性矛盾。所以式(2)必定成立。 取q = ko知式(1)成立。存在性得證。唯一性 假設(shè)有兩對(duì)整數(shù) 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、余數(shù)。由定理1可知，對(duì)于給定的整數(shù) b,可以按照被b除的余數(shù)將所有的整數(shù)分成b類。在同一類中的數(shù)被 b 除的余數(shù)相同。 這就使得許多關(guān)于全體整數(shù)的問題可以歸化為對(duì)有限個(gè)整 數(shù)類的研究。以后在本書中，除特別聲明外，在談到帶余數(shù)除法時(shí)總是假定b 是正整數(shù)。例1 設(shè)a, b, x, y是整數(shù)，k和m是正整數(shù)，并且a =a1mr1， o r1 < m，b =b1mr2， o r2 < m，則 ax by 和 ab 被 m 除的余數(shù)分別與r1xr2y和門r2被m除的余數(shù)相同。特別地，ak與 r1被 m 除的余數(shù)相同。 解由ax by = (a1m r1)x (b1m r2)y = (a1x

16、b1y)m r1x r2y 可知，若rix r2y被m除的余數(shù)是r，即r1x r2y = qm r, o r < m,則ax by = (a1x b1y q)m r, o r < m,即 ax by 被 m 除的余數(shù)也是 r。 同樣方法可以證明其余結(jié)論。例2設(shè)ai, a2, , an為不全為零的整數(shù)，以yo表示集合A = y；y = a1x1anxn, xi Z, 1 i n 中的最小正數(shù)，則對(duì)于任何 y A，yo y;特別地，yo a， 1 i n。解設(shè) yo = a1X1anxn，對(duì)任意的 y = a1X1anxn A，由定理 1，存在 q, ro Z，使得y = qyoro，

17、 oro < yo 。因此ro = yqyo= a1(x1qx1 )an(xnqxn ) A。如果roo ，那么，因?yàn)閛 <ro < yo，所以ro是A中比yo 還小的正數(shù)，這與 yo 的定義矛盾。所以ro=o，即 yoy。顯然aiA( 1in)，所以yo整除每個(gè)ai (1 i n)。例 3 任意給出的五個(gè)整數(shù)中，必有三個(gè)數(shù)之和被 3 整除。 解 設(shè)這五個(gè)數(shù)是 ai，i = 1, 2, 3, 4, 5，記ai = 3qi分別考慮以下兩種情形：(i )若在 ri, r2,ri，0 ri < 3， i = 1, 2, 3, 4, 5。, r5 中數(shù) 0 ，a11，a22 都

18、出現(xiàn)，不妨設(shè) a3 = 3(q1 q2 q3)r1 = 0，r2 = 1，r3 = 2，此時(shí)3這樣至少有三個(gè)r i 要取相同的值，不妨設(shè) r1 = r2 = r3 = r(r= 0， 1 或 2)，此時(shí)a1a2a3= 3(q1 q2q3)3r可以被 3 整除。例 4 設(shè) a0, a1, an Z，f(x) = an nxa1xa0，已知f(0)與-明：若方程 f(x) = 0 有整數(shù)解，則3f( 1) =a0a1a2( 1)n an 。解對(duì)任何整數(shù)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的倍數(shù)，所以f(x)0；(i ) 若 r = 1，即 x = 3q1， qZ，則f(x) = f(3q 1) =an(3q1)na1(3q1)a0= 3Q2 ana1a0 =3Q2f(1)，, r5 中數(shù) 0，2至少有一個(gè)不出現(xiàn)，1，其中 Q2f(1) 都不是 3 的倍數(shù)，證f(0)，可以被 3 整除；(ii)若在 ri, r2,Z。由于f(1)不是3的倍數(shù)，所以f(x) 0。因此若f(x) = 0有整數(shù)解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證明：對(duì)于任意的整數(shù)n，f(n) = 3n5 5n3 7n被15整除。解對(duì)于任意的正整數(shù) n，記0 r < 15 。n = 15q r，1 ， q Z ，于是 a0n2 = 15Q1 r1其中ri與r2分別是r2與r4被15除的余數(shù)。以 R 表示 3n4 5n2 7 被 i5 除的余數(shù)， 被15除的余數(shù)就是rR被15除的余數(shù)，記為當(dāng)r = 0時(shí)，顯然R = 0，即對(duì)于n4 = 15Q2 r2，r = 1, 2, 3, 14 的情形，則 R

21、 就是 3r2R。15 3n5 5n3 7n。通過計(jì)算列出下表：5r1 7被 15除的余數(shù)，而且 f(n)由例 1，r =1, 142, 133, 124, 115, 106, 97, 8r1 =14911064r2 =11611061R =0010012100R=0000000這證明了結(jié)論。例6設(shè)n是奇數(shù)，則16 n4 4n2 11。解我們有n4 4n211 = (n21)( n25)16。由第一節(jié)例題9，有8 n2 1,由此及2 n2 5得到16 (n2 1)(n2 5)。例7證明：若a被9除的余數(shù)是3， 4， 5或6，則方程x3 y3 = a沒有整數(shù)解。 解對(duì)任意的整數(shù)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除的余數(shù)分別與 門3和23被9除的余數(shù)相同，即R1 = 0，1 或 8，R2 = 0，1 或 8。(4)因此x3 y3 = 9(Q1 Q2) R1 R2。又由式(4)可知，R1 R2被9除的余數(shù)只可能是0，1, 2,7或8,所以，x3 y3不可能等于a。習(xí)題二1. 證明：12 n4 2n3 11n2 10n，n Z。2. 設(shè) 3 a2 b2，證明：3 a 且 3 b。3. 設(shè)n，k是正整數(shù)，證明：nk與nk + 4的個(gè)位數(shù)字

23、相同。4. 證明：對(duì)于任何整數(shù) n，m，等式n2 (n 1)2 = m2 2不可能成立。5. 設(shè)a是自然數(shù)，問a4 3a2 9是素?cái)?shù)還是合數(shù)？6. 證明：對(duì)于任意給定的 n個(gè)整數(shù)，必可以從中找出若干個(gè)作和，使得這個(gè)和能被n整除。答案第三節(jié)最大公約數(shù)定義1 整數(shù)a1, a2, , ak的公共約數(shù)稱為 a1, a2, , ak的公約數(shù)。不全為零的整數(shù)a1, a2,ak的公約數(shù)中最大的一個(gè)叫做a1, a2, , ak的最大公約數(shù)(或最大公因數(shù))，記為(a1, a2,ak)。由于每個(gè)非零整數(shù)的約數(shù)的個(gè)數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù)。如果(a1, a2, , ak) = 1，則稱a1,

24、 a2, , ak是互素的(或互質(zhì)的)；如果(ai, a j) = 1，1 i, j k，i j， 則稱a1, a2, , ak是兩兩互素的(或兩兩互質(zhì)的)。顯然，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是素?cái)?shù)，a是整數(shù)，則(p, a) = 1或

25、p a;(V ) 若 a = bq r，則(a, b) = (b, r)。證明(i )(iv )留作習(xí)題。(v )由第一節(jié)定理1可知，如果d a, d b，則有dr = a bq,反之，若d b, dr, 則d a = bq r。因此a與b的全體公約數(shù)的集合就是b與r的全體公約數(shù)的集合，這兩個(gè)集合中的最大正數(shù)當(dāng)然相等，即(a, b) = (b, r)。證畢。由定理1可知，在討論(ai, a2, , an)時(shí)，不妨假設(shè)ai, a2, , an是正整數(shù)，以后我們就維 持這一假設(shè)。定理2設(shè)ai, a2, ak Z，記kA = y; y =aiXi ，Xi z， i k 。i 1如果yo是集合A中最小

26、的正數(shù)，則 yo = (ai, a2, , ak)。證明 設(shè)d是ai, a2, , ak的一個(gè)公約數(shù)，則 d yo，所以d yo。另一方面，由第二節(jié)例 2知，yo也是ai, a2, , ak的公約數(shù)。因此yo是ai, a2, , ak的公約數(shù)中的最大者，即yo = ( ai,a2, ak)。證畢。推論I 設(shè)d是ai, a2, , ak的一個(gè)公約數(shù)，則 d (ai, a2, , ak)。這個(gè)推論對(duì)最大公約數(shù)的性質(zhì)做了更深的刻劃：最大公約數(shù)不但是公約數(shù)中的最大的, 而且是所有公約數(shù)的倍數(shù)。推論 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的充要條件是存在整數(shù)xi, X2, , xk,使得aixi a2x2akXk = i。(i)證明 必要性 由定理2得到。充分性 若式成立，如果(ai,a2, ak)= d > i,那么由dai(i ik)推出daixia2X2akxk= i，這是不可能的。所以有 (ai, a2, , ak) = i。證畢。定理4 對(duì)于任意的整數(shù) a, b, c,下面的結(jié)論成立：(i ) 由b ac及(a, b) = 1可以推出b c;(ii)由 b c, a c 及(a, b) = 1

28、 可以推出 ab c。證明(i )若(a, b) = 1，由定理2,存在整數(shù)x與y,使得ax by = 1。因此acx bcy = c。(2)由上式及b ac得到b c。結(jié)論(i )得證；(i) 若(a, b) = 1,則存在整數(shù)x, y使得式 成立。由b c與a c得到ab ac, ab bc, 再由式 得到ab c。結(jié)論(i )得證。證畢。推論1若p是素?cái)?shù)，則下述結(jié)論成立：(i ) p ab p a 或 p b;(i) p a2pa。證明留作習(xí)題。推論 2 若(a, b) = 1，則(a, bc) = (a, c)。證明 設(shè)d是a與bc的一個(gè)公約數(shù)，則 d a, d bc,由式(2)得到，

29、d|c,即d是a與c的公約數(shù)。另一方面，若d是a與c的公約數(shù)，則它也是 a與be的公約數(shù)。因此,的公約數(shù)的集合，就是a與be的公約數(shù)的集合，所以(a, be) = (a, e)。證畢。推論 3 若(a, bi) = 1， 1 i n,則(a, bib2 bn) = 1。 證明留作習(xí)題。依次定理5對(duì)于任意的n個(gè)整數(shù)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的一個(gè)公約數(shù)。則即1, an) = dn，另一方面，對(duì)于 a1, a2, , an的任何公約數(shù)d，由定理2的推論及d2, , dn的定義, 得出da1，da2dd2,dd2，da3dd3,d dn 1， d an d dn，因此dn是a1, a2, , an的公約數(shù)中的最大者，即dn = (a1, a2, , an)。證畢。例1證明：

31、若n是正整數(shù)，則 空 4是既約分?jǐn)?shù)。 14n 3解由定理1得到(21 n 4, 14n 3) = (7 n 1, 14n 3) = (7 n 1, 1)=1。注：一般地，若(x, y) = 1，那么，對(duì)于任意的整數(shù)a，b，有(x, y) = (x ay, y) = (x ay, y b(x ay) = (x ay, (ab 1)y bx)，因此， 1_翌是既約分?jǐn)?shù)。(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)不能成立。注：這個(gè)例題的一般形式是：設(shè)p是素?cái)?shù)，a，b是整數(shù)，則pk | (an b)k pk 1e，其中 c 是不被 p 整除的任意整數(shù)， k 是任意的大于 1 的整數(shù)。例 3 設(shè) a， b 是整數(shù)，且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 設(shè) a 和 b 是正整數(shù), 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，此時(shí)2kb 1 =(2b1)(2(k 1)b 2(k 2)b1) = (2b 1)Q，其中 Q 是整數(shù)。所以2a1 =

34、 2kb + r1= 2r(2kb1 1)1= 2r(2b1)Q 1)1 = (2b1)Q(2r1)，其中 Q 是整數(shù)。因此2b 12a 12b1 2r 1，a = 1,即 b = 2,這是不可能的,所以式 (6)不成立。(ii)若a = b,且式成立，則由式(6)得到在(i )中已經(jīng)證明這是不可能的，所以式不能成立。(6)綜上證得 2b 1 |2a 1。習(xí)題三1. 證明定理1中的結(jié)論(i ) (iv )。2. 證明定理 2的推論 1, 推論 2 和推論 3。3. 證明定理 4 的推論 1 和推論 3。4. 設(shè)x,y Z, 17 2x 3y,證明：17 9x 5y。5. 設(shè)a,b, c N ,

35、 c無平方因子，a2 b2c,證明：a b。132n 16. 設(shè) n 是正整數(shù)，求 C12n,C32n, ,C22nn 1的最大公約數(shù)。第四節(jié)最小公倍數(shù)定義1 整數(shù)ai, a2,中的最小的一個(gè)叫做定理,ak的公共倍數(shù)稱為 ai, a2, , ak的公倍數(shù)。ai, a2, , ak的正公倍數(shù) ai, a2, , ak的最小公倍數(shù)，記為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|。留作習(xí)題。由

36、定理1中的結(jié)論(iii)可知，在討論ai, a2, , ak的最小公倍數(shù)時(shí)，不妨假定它們都是正 整數(shù)。在本節(jié)中總是維持這一假定。最小公倍數(shù)和最大公約數(shù)之間有一個(gè)很重要的關(guān)系，即下面的定理。定理2對(duì)任意的正整數(shù)a, b,有ab a, b=(a,b)證明 設(shè)m是a和b的一個(gè)公倍數(shù)，那么存在整數(shù)ki, k2，使得m = aki, m = bk2，因此(1)aki = bk2。亠2。(a,b)由于(聶，盤=1，所以由第三節(jié)定理4得到盞1ki，即ki盞/，其中t是某個(gè)整數(shù)。將上式代入式 (1)得到abm = t。(a, b)另一方面，對(duì)于任意的整數(shù)t,由式(2)所確定的m顯然是a與b的公倍數(shù)，因此a與b

37、的公倍數(shù)必是式 中的形式，其中t是整數(shù)。當(dāng)t=1時(shí)，得到最小公倍數(shù)aba, b=(a,b)證畢。推論1兩個(gè)整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除。 證明由式(2)可得證。證畢。而且是另外的公倍數(shù)的約這個(gè)推論說明：兩個(gè)整數(shù)的最小公倍數(shù)不但是最小的正倍數(shù)， 數(shù)。推論2 設(shè)m, a, b是正整數(shù)，則ma, mb = ma, b。證明由定理2及第三節(jié)定理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對(duì)于任意的則=mn,n個(gè)整數(shù)ai, a2, an,記mn是ai, a2, an的一個(gè)公倍數(shù)。另一方面，對(duì)于 ai, a2, an的任何公倍數(shù) m，由定理2的推論及m2, mn的定義，得m2 m， m3 m， mn m。mn是ai, a2, an最小的正的公倍數(shù)。證畢。推論 若m是整數(shù)ai, a2, an的

39、公倍數(shù)，則ai, a2, an m。留作習(xí)題。證明定理4整數(shù)ai, a2, an兩兩互素，即（ai, aj） = i，i i, j n，i j的充要條件是ai, a2, , an = aia2 an。 證明 必要性因?yàn)?ai, a2) = i，由定理2得到a a?ai, a2 = aia2。(ai,a2)由(ai, a3)= (a2, a3)= i及第三節(jié)定理 4推論3得到(aia2, a3)= i，由此及定理3得到ai, a2, a3 = ai, a2, a3 = ai a2, a3 = aia2a3 。如此繼續(xù)下去，就得到式（3）。充分性 用歸納法證明。當(dāng) n = 2時(shí)，式 成為ai, a

40、2 = aia2。由定理2aa2aia2 = ai, a2 =(ai, a2) = i，(ai, a2 )即當(dāng)n = 2時(shí)，充分性成立。假設(shè)充分性當(dāng)n= k時(shí)成立，即ai, a2, ak = aia2對(duì)于整數(shù)ai, a2, ak, ak + i，使用定理ak(ai, aj) = i， i i, j k， i j。3中的記號(hào)，由定理 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；由式及歸納假設(shè)推出(ai, aj) = 1，1 i, j k，i j。(8)綜合式(7)與式(8)，可知當(dāng)n =k 1時(shí)，充分性成立。由歸納法證明了充分性。證畢。mk=aia2 ak ,(mk, ak 1 )定理4有許多應(yīng)用。例如，如果mi, m2, mk是兩兩互素的整數(shù)，那么，要證明m =i， 1 ik，都有

42、mi Q。這一點(diǎn)在實(shí)際計(jì)算m f(n)，n Z ”是否成立，可以用第二節(jié)例5若分別m1m2 mk整除某個(gè)整數(shù) Q，只需證明對(duì)于每個(gè) 中是很有用的。對(duì)于函數(shù)f(x)，要驗(yàn)證命題“中的方法，驗(yàn)證"m f(r)，r = 0, 1, m驗(yàn)證“ mi f(門)，門=0, 1, mi 1， 1除法。后者的運(yùn)算次數(shù)顯然少于前者。例1 設(shè)a， b， c是正整數(shù)，證明：解由定理3和定理2有1”是否成立。這需要做 m次除法。但是,k”是否成立，則總共需要做 m1 m2a, b, c(ab, be, ca) = abc。a,bc a, b, c = a, b, c=(a,b, c)由第三節(jié)定理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)聯(lián)合式(9)與式(10)得到所需結(jié)論。對(duì)于任意的整數(shù)a1, a2,a1, a2,因?yàn)閍1, a2, , an是 a1,an及整數(shù)k， 1,an = a1,ak, ak + 1,k n,證明：,ak,ak+ 1, an,an的公倍數(shù)，所以由定理2推論，推出再由定理3推論知另一方面，對(duì)于任意的所以由定理3推論可知a1,ak + 1,ai( 1aiia1,a1, a2, 聯(lián)合上式與式(11)得證。例3 設(shè)

44、a， b， c是正整數(shù)，證明:,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, 由此得證。習(xí)題四1. 證明定理1。2. 證明定理3的推論。3. 設(shè) a, b 是正整數(shù)，證明：(a b)a, b = ab, a b。4. 求正整數(shù) a， b，使得 a b = 12

46、0， (a, b) = 24， a, b = 144。5. 設(shè)a，b， c是正整數(shù)，證明：2 2a,b, c(a,b,c)。a, bb,cc, a (a,b)(b, c)(c, a)6. 設(shè)k是正奇數(shù)，證明：1 29 1k 2k9k。第五節(jié)輾轉(zhuǎn)相除法本節(jié)要介紹一個(gè)計(jì)算最大公約數(shù)的算法一一輾轉(zhuǎn)相除法，又稱 中的一個(gè)重要方法，在其他數(shù)學(xué)分支中也有廣泛的應(yīng)用。定義1下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法。設(shè)a和b是整數(shù)，b 0,依次做帶余數(shù)除法：a = bq1 r1，0 < r1 < |b|,b = aq2 2，0 <2 < r1，Euclid算法。它是數(shù)論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)中只包含有限個(gè)等式。下面，我們要對(duì)式(1)所包含的等式的個(gè)數(shù)，即要做的帶余數(shù)除法的次數(shù)進(jìn)行估計(jì)。弓I理1用下面的方式定義 Fib on acci數(shù)列 Fn:F1 = F2 = 1， Fn = Fn 1Fn 2， n 3，那么對(duì)于任意的整數(shù)n 3,有n 2Fn >其中1,52證明容易驗(yàn)證當(dāng)n = 3時(shí)，由1。2可知式(2)成立。假

48、設(shè)式(2)對(duì)于所有的整數(shù)k n (n 3)成立，即Fk > k 2，k n，F(xiàn)n + 1 = Fn Fn 1 >3(1)=即當(dāng)k = n 1時(shí)式也成立。由歸納法知式 對(duì)一切n 3成立。證畢。定理1 (Lame)設(shè)a, b N， a > b，使用在式(1)中的記號(hào)，則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、理結(jié)論。證畢。定理2使用式(1)中的記號(hào),記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，此時(shí)由式(1)得到aQ2bP2 :=aq2b(q2q11)=(a bq1)q2b = r1q2 b = r2,即式成立。假設(shè)對(duì)于k < m(1m n)式成立,由此假設(shè)及式(1)得到證明當(dāng)k = 1時(shí)，式成立。當(dāng)k = 2時(shí)，有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，即式