初等數(shù)論整除理論

1、第一章整除理論整除性理論是初等數(shù)論的基礎(chǔ)。本章要介紹 帶余數(shù)除法，輾轉(zhuǎn)相除法，最大公約數(shù)， 最小公 倍數(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ù))，并且使用記號b a;如 果不存在整數(shù)c使彳導(dǎo)a = bc成立，則稱a不被b整除，記為b | a。顯然每個非零整數(shù) a都有約數(shù) 1, a, 稱這四個數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱 為非平凡約數(shù)。被2整除的整數(shù)稱為偶數(shù)，不被2整除的整 數(shù)稱為奇數(shù)。定理1 下面的結(jié)論成立：(i ) a b ab;(ii) ab,

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

3、。不妨設(shè)di是 其中最小的。若di不是素數(shù)，則存在ei > 1, e2 > 1,使得d1 = e1e2,因此，e1和e2也是a的正的 非平凡約數(shù)。這與 d1的最小性矛盾。所以 d1是 素數(shù)。證畢。推論任何大于1的合數(shù)a必有一個不超過0a的素約數(shù)。證明 使用定理2中的記號，有a = d1d2, 其中d1 > 1是最小的素約數(shù)，所以 d12a。證畢。例1 設(shè)r是正奇數(shù)，證明：對任意的正整 數(shù)n,有n 2 11r 2rn。解對于任意的正整數(shù)a, b以及正奇數(shù)k,有akbk = (a b)(ak 1 ak 2bak 3b2bk 1) = (ab)q,其中q是整數(shù)。記s = 1r 2

4、r n r,則2s = 2(2rn r)(3r (n1)r)(n r2r) = 2(n 2)Q,其中Q是整數(shù)。若n 2 s,由上式知n 2 2,因為n 2 > 2,這是不可能的，所以 n 2 | s。例2 設(shè)A = d1, d2, dk 是門的所有約數(shù)的集合，則也是n的所有約數(shù)的集合。解 由以下三點理由可以證得結(jié)論：(i ) A和B的元素個數(shù)相同；(ii ) 若di A, IP di n,則2-| n,反之亦 di然；n n(in)右 didj,貝U 。di dj例3 以d(n)表示n的正約數(shù)的個數(shù)，例如:d(1) = 1, d(2) = 2, d(3) = 2, d(4) = 3,。問

5、：d(1)d(2)d(1997)是否為偶數(shù)解 對于n的每個約數(shù)d,都有n = d因此，n的正約數(shù)d與q是成對地出現(xiàn)的。 只有 當(dāng)d =_n ,即n = d2時，d和n才是同一個數(shù)。故當(dāng)且僅當(dāng)n是完全平方數(shù)時，d(n)是奇數(shù)。因為 442 < 1997 < 452,所以在 d(1), d(2), d(1997)中恰有44個奇數(shù),故d(1)d(2)d(1997)是偶數(shù)。例4 設(shè)凸2n邊形M的頂點是Ai, A2,l A2n,點O在M的內(nèi)部，用1, 2, 2n將M的2n條邊分別編號，又將OAi, OA2, OA2n也同樣進行編號，若把這些編號作為相應(yīng)的線段的長 度，證明：無論怎么編號，都不

6、能使得三角形 OA1A2, OA2A3, OA2nAi 的周長都相等。解假設(shè)這些三角形的周長都相等，記為So 則2ns = 3(122n) = 3n(2n1),即2s = 3(2n1),因此2 3(2n1),這是不可能的，這個矛盾說明這些三角形的周長不可能全都相等。例5 設(shè)整數(shù)k 1,證明：(i)若 2k n < 2k 1,1 a n, a2k,則 2k | a；(ii)若 3k2n 1 < 3k + 1, 1 b n,2b 13k,則 3k 12b1。解(i )若2k|a,則存在整數(shù)q,使得a= q2k。顯然q只可能是0或1。此時a= 0或2k ,這都是不可能的，所以 2k |

7、a；(ii)若3k|2b-1，則存在整數(shù)q,使得2b-1 = q3k,顯然q只可能是0, 1,或2。此時2b-1= 0, 3k,或2 3k ,這都是不可能的，所以3k12b 1。例6 寫出不超過100的所有的素數(shù)。解 將不超過100的正整數(shù)排列如下:-48 -9 101118 19 202128 29 30310ao. 10A XA.38 39 41041A Q A C cn48 49 505158 59 6061cn ztn 7A68 69 707178 79 808188 89 9023T1213M222324323334424344525354QQOPQ.A626364727374828

8、3845-67151617252627353637454647gggog-7555657656667757677ACiA38586879192939495969798 99 100按以下步驟進行：(i )刪去1 ,剩下的后面的第一個數(shù)是2,2是素數(shù)；(ii)刪去2后面的被2整除的數(shù)，剩下的2后面的第一個數(shù)是 3, 3是素數(shù)；(iii)再刪去3后面的被3整除的數(shù)，剩下的3后面的第一個數(shù)是 5, 5是素數(shù)；(iv)再刪去5后面的被5整除的數(shù)，剩下的5后面的第一個數(shù)是 7, 7是素數(shù)；照以上步驟可以依次得到素數(shù)2, 3, 5, 7, 11,由定理2推論可知，不超過100的合數(shù)必有 一個不超過10的素

9、約數(shù)，因此在刪去 7后面被 7整除的數(shù)以后，就得到了不超過100的全部素 數(shù)。在仞6中所使用的尋找素數(shù)的方法，稱為 Eratosthenes篩法。它可以用來求出不超過任何 固定整數(shù)的所有素數(shù)。在理論上這是可行的； 但在實際應(yīng)用中，這種列出素數(shù)的方法需要大量的 計算時間，是不可取的。例7 證明：存在無窮多個正整數(shù)a,使得n4 a (n = 1,2, 3,) 都是合數(shù)。解取a = 4k4,對于任意的n N,有n4 4k4 = (n22 k2)24n2k2 = (n2 2k22nk)(n2 2k22nk)。因為n2 2k2 2nk = (n k)2 k2 k2,所以，對于任意的k = 2, 3,以及

10、任意的n N,n4a是合數(shù)。例8 設(shè)ai, a2, an是整數(shù)，且aia2an = 0, aia2 an = n,貝U 4 n。解 如果2 | n,則n, ai, a2, an都是奇數(shù)。于是aia2an是奇數(shù)個奇數(shù)之和，不可能等于零，這與題設(shè)矛盾，所以 2 n,即在 ai, a2, an中至少有一個偶數(shù)。如果只有一個偶數(shù)，不妨設(shè)為ai,那么2 |ai (2 in)。此時有等式a2an = ai,在上式中，左端是(ni)個奇數(shù)之和，右端是偶數(shù)，這是不可能白1因此，在ai, a2, , an中至少有兩個偶數(shù)，即 4 n。例9若n是奇數(shù)，則8 n2i。解設(shè)n = 2k i,則n2 i= (2ki)2

11、i = 4k(k i)。在k和k i中有一個是偶數(shù)，所以8 n2io例9的結(jié)論雖然簡單，卻是很有用的。例如， 使用例3中的記號，我們可以提出下面的問題：問題 d(i)2d(2)2d(i997)2被 4除的余數(shù)是多少例i0 證明：方程ai2a22a32 = i999(i)無整數(shù)解。解 若ai, a2, a3都是奇數(shù)，則存在整數(shù)Ai, A2, A3,使得ai 證明定理1。 證明：若 m p mn pq,則m p mqnp。 3.證明：任意給定的連續(xù) 39個自然數(shù)， 其中至少存在一個自然數(shù)， 使得這個自然數(shù)的數(shù) 字和能被11整除。 設(shè)p是n的最小素約數(shù)，n = pni, ni > 1, = 8

12、A11, a22 = 8A21, a32 = 8A31,于是ai2a22a32 = 8(AiA2 A3)3。由于1999被8除的余數(shù)是7,所以ai, a2, a3 不可能都是奇數(shù)。由式(1), ai, a2, a3中只能有一個奇數(shù)，設(shè) ai為奇數(shù)，a2, a3為偶數(shù)，則存在整數(shù) Ai, A2, A3,使得ai2 = 8A11, a22 = 8A2r, a32 = 8A3 s,于是222aia2a3 = 8(AiA2A3)1r s,其中r和s是整數(shù)，而且只能取值 0或4。這樣 ai2a22a32被8除的余數(shù)只可能是1或5,但1999被8除的余數(shù)是7,所以這樣的ai, a2, a3也不能使式(2)

13、成立。綜上證得所需要的結(jié)論。習(xí)題一證明：若p >3/n,則ni是素數(shù)。5.證明：存在無窮多個自然數(shù)n,使得n不能表示為a2p （a >。是整數(shù)，p為素數(shù)）的形式。第二節(jié)帶余數(shù)除法在本節(jié)中，我們要介紹帶余數(shù)除法及其簡單 應(yīng)用。定理1（帶余數(shù)除法）設(shè)a與b是兩個整數(shù)， b 0,則存在唯一的兩個整數(shù)q和r,使得a = bq r, 0 r < | b|。證明存在性 若b a, a = bq, q Z,可 取r = 0。若b | a,考慮集合A = akb; k Z ,其中Z表示所有整數(shù)的集合，以后，仍使用此記號，并以N表示所有正整數(shù)的集合。在集合A中有無限多個正整數(shù)，設(shè)最小的 正整數(shù)

14、是r = akob,則必有0 < r < | b| ,（2）否則就有r | b|。因為b | a,所以r | b|。于 是 r > | b| ,即 a k0b > | b| , a k°b | b| > 0 , 這樣，在集合A中，又有正整數(shù)a k0b |b|<r,這與r的最小性矛盾。所以式（2）必定成立。取q = ko知式（1）成立。存在性得證。唯一性假設(shè)有兩又整數(shù) q , r 與q,r都使彳#式（1）成立，即a = q b r = q b r , 0 r , r < |b| , 則（q q ）b = r r , |r rI < I b

15、| ,因此r r = 0, r = r ,再由式 得出q = q ,唯一性得證。證畢。定義1稱式（1）中的q是a被b除的商，r 是a被b除的余數(shù)。由定理1可知，對于給定的整數(shù) b,可以按 照被b除的余數(shù)將所有的整數(shù)分成b類。在同一類中的數(shù)被b除的余數(shù)相同。這就使得許多關(guān)于 全體整數(shù)的問題可以歸化為對有限個整數(shù)類的 研究。以后在本書中，除特別聲明外，在談到帶余 數(shù)除法時總> 是假定 b是正整數(shù)。例1 設(shè)a, b, x, y是整數(shù)，k和m是正 整數(shù)，并且a = a1m門,0門 < m,b = b1mr2, 0r2 < m,則ax by和ab被m除的余數(shù)分別與rxr2y和r12被m

16、除的余數(shù)相同。特別地，ak與rk被m除的余數(shù)相同。解由ax by = （am門）x（bmr2）y = （a1xb1y)mr1xr2y可知，若rixr2y被m除的余數(shù)是r,即rixr2y = qm r, 0 r < m,則ax by = (aix biyq)m r, 0 r < m,即ax by被m除的余數(shù)也是r。同樣方法可以證明其余結(jié)論。例2 設(shè)ai, a2, an為不全為零的整數(shù)，以yo表示集合A = y； y = aixianxn, xi Z, 1 i n 中的最小正數(shù)，則對于任何 y A, yo y；特別 地，yo ai, 1 i n。解設(shè) yo = aixianxn ,對任

17、意的y = aixianxn A,由定理i,存在q,ro Z,使得y = qyoro, 0ro < yo。因此ro = yqyo = ai(xiqxi )an(xnqxn ) Ao如果ro o,那么，因為o < ro < yo,所以ro 是A中比yo還小的正數(shù)，這與 yo的定義矛盾。 所以ro = o,即yo yo顯然ai A(i i n),所以yo整除每個 ai (i in)。例3 任意給出的五個整數(shù)中，必有三個數(shù)之和被3整除。解 設(shè)這五個數(shù)是ai, i = i, 2, 3, 4, 5,記 ai = 3qiri, ori < 3, i = i, 2, 3, 4, 5。

18、分別考慮以下兩種情形：(i )若在ri, r2, , r5中數(shù)o, i, 2都出現(xiàn)，不妨設(shè)ri = o,r2 = i, r3 = 2,此時ai a2a3 = 3(qiq2q3)3可以被3整除；(ii) 若在門，r2, r5中數(shù)0, 1, 2至少有一個不出現(xiàn)，這樣至少有三個ri要取相同的值，不妨設(shè) ri = r2 = r3 = r (r = 0, 1 或 2),此時aia2 a3 = 3(qi q2 q3) 3r可以被3整除。例 4 設(shè) ao, ai, , an Z,f(x) = anxn aix ao ,已知f(0)與f(i)都不是3的倍數(shù)，證 明：若方程f(x) = 0有整數(shù)解，則3 f(

19、i) = aoaia2( i)nan。解對任何整數(shù)x,都有x = 3q r, r = 0, i 或 2, q Z。(i )若 r = 0,即 x = 3q, q Z,貝U f(x) = f(3q) = an(3q)nai(3q)a。= 3Qia0 = 3Qif(0),其中Qi Z,由于f(0)不是3的倍數(shù)，所以f(x) 0；(ii)若 r = i,即 x = 3q i, q Z,貝 U f(x) = f(3q i) = an(3qi)nai(3qi) a0=3Q2anaia0 =3Q2f(i),其中Q2 Zo由于f(i)不是3的倍數(shù)，所以f(x) 0。因此若f(x) = 0有整數(shù)解x,則必是x

20、 = 3q2 = 3q i, qZ,于是0 = f(x) = f(3q i) = an(3qi)nai(3qi) a0=3Q3a0aia2(i)nan=3Q3f( 1),其中 Q3 Z。所以 3 f( 1) = aoaia2(1)nan 。例5 證明：對于任意的整數(shù) n, f(n) = 3n55n37n被15整除。解對于任意的正整數(shù) n,記n = 15q r, 0 r < 15。由例1,n2 = 15Q1 門，n4 = 15Q2r2,其中門與r2分別是r2與r4被15除的余數(shù)。以R表示3n45n27被15除的余數(shù)，則R就是3r25門7被15除的余數(shù)，而且f(n)被15除的余數(shù)就是rR被1

21、5除的余數(shù)，記為R 。當(dāng) r = 0 時，顯然 R = 0,即 15 3n5 5n37n。對于r = 1,2, 3, 14的情形，通過計算列r = 1, 142, 133, 124, 1149160100005,11120出下表：106, 97,8門=11064r2 =11061R =0100R =0000這證明了結(jié)論。例6 設(shè)n是奇數(shù)，則16 n44n211。解我們有n4 4n211 = (n 證明：12 n42n311n210n,n Z。 2.設(shè) 3 a2b2,證明：3 a 且 3 b。1)(n25)16。由第一節(jié)例題9,有8 n21,由此及2 n25 得到 16 (n21)(n25)。例

22、7證明：若a被9除的余數(shù)是3, 4, 5 或6,則方程x3.設(shè)n,k是正整數(shù)，證明：nk與nk + 4的 個位數(shù)字相同。4.證明：對于任何整數(shù) n, m,等式n2 (n1)2 = m22不可能成立。y3 = a沒有整數(shù)解。解對任意白整數(shù)x, y,記x = 3q1門，y = 3q2r2, 0 門，r2 < 3。則存在Q1, R1, Q2, R2 Z,使得x3 = 9Q1R , y3 = 9Q2R2 ,其中R1和R2被9除的余數(shù)分別與 r13和r23被9 除的余數(shù)相同，即R1 = 0, 1 或 8, R2 = 0, 1 或 8。(4)因此x3y3 = 9(Q1Q2)R1R2。又由式(4)可知

23、，R1及被9除的余數(shù)只可能是0, 1, 2, 7或8,所以，x3 y3不可能等于a 。習(xí)題二5.設(shè)a是自然數(shù)，問a43a2 9是素數(shù)還是合數(shù)6.證明：對于任意給定的 n個整數(shù)，必可 以從中找出若干個作和，使得這個和能被n整除。答案第三節(jié)最大公約數(shù)定義1 整數(shù)ai, a2, ak的公共約數(shù)稱為ai, a2, , ak的公約數(shù)。不全為零的整數(shù) ai, a2, ak的公約數(shù)中最大的一個叫做ai, a2, ak的最大公約數(shù)(或最大公因數(shù))，記為(ai, a2, ak)。由于每個非零整數(shù)的約數(shù)的個數(shù)是有限的， 所以最大公約數(shù)是存在的，并且是正整數(shù)。如果(ai, a2, ak) = i,則稱 ai, a2

24、, ak是互素的(或互質(zhì)的)；如果(ai, a j) = i, i i, j k, i j,則稱ai, a2, ak是兩兩互素的(或兩兩互質(zhì)的)。顯然，ai, a2, ak兩兩互素可以推出(ai, a2,ak) = i,反之則不然，例如(2, 6, i5) = i , 1(2, 6) = 2。定理i 下面的等式成立：(i) (ai, a2, ak)= (| ai|, | a2|, | ak|);(ii) (a, i) = i, (a, 0) =| a| , (a, a) = |a| ;(iii) (a, b) = (b, a);(iv )若p是素數(shù)，a是整數(shù)，則(p, a) = i或p a;(

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

26、則yo= (ai, a2, ak)。證明 設(shè)d是ai, a2, ak的一個公約數(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的一個公約數(shù)，則 d (ai, a2, ak)。這個推論對最大公約數(shù)的性質(zhì)做了更深的 刻劃：最大公約數(shù)不但是公約數(shù)中的最大的，而且是所有公約數(shù)的倍數(shù)。推論 2 (mai, ma2, , mak) = | m|( ai, a2, ak) o推論 3 記=(ai, a2, , ak),則特別地，(一

27、一，上一)=1。(a,b) (a,b)，定理3 (ai, a2, ak) = 1的充要條件是存在整數(shù)Xi, X2, Xk,使得aixia2X2akxk = 1。(1)證明必要性 由定理2得到。充分性 若式(1)成立，如果(a1, a2, ak) = d >1,那么由 d ai (1 ik)推出 d a1X1a2X2akxk = 1,這是不可能的。所以有(a1, a2, ak) = 1。證畢。定理4 對于任意的整數(shù) a, b, c,下面的 結(jié)論成立：(i) 由b ac及(a, b) = 1可以推出b c;(ii) 由b c, a c及(a, b) = 1可以推出 ab c。證明 (i )若

28、(a, b) = 1,由定理2,存在整 數(shù)x與y,使得aX by = 1。因此acXbcy = c。(2) 由上式及b ac得到b c。結(jié)論(i )得證；(ii)若(a, b) = 1,則存在整數(shù)X, y使得式 (2)成立。由 b c 與 a c 得至U ab ac, ab bc, 再由式(2)得到ab c。結(jié)論(ii)得證。證畢。推論1若p是素數(shù)，則下述結(jié)論成立：(i )pabpa 或p b;(ii)pa2pa。證明留作習(xí)題。推論 2 若(a, b) = 1,則(a, bc) = (a, c)。證明 設(shè)d是a與bc的一個公約數(shù)，則d a, d bc,由式(2)得到，d|c,即d是a 與c的公

29、約數(shù)。另一方面，若d是a與c的公約 數(shù)，則它也是 a與bc的公約數(shù)。因此，a與c 的公約數(shù)的集合，就是a與bc的公約數(shù)的集合， 所以(a, bc) = (a, c)。證畢。推論 3 若(a, bi) = 1, 1 in,則(a,blb2 bn) = 1。證明留作習(xí)題。定理5對于任意的n個整數(shù)a1, a2, an,記(a1，a2) = d2, (d2, a3) = d3, (dn 2, an 1) = dn1, (dn 1, an) = dn,則dn = (a1, a2, an)。證明由定理2的推論，我們有dn = (dn 1, an)dn an, dn dn1,dn 1 = (dn 2, an

30、 1)dn 1 an 1,dn 1 dn 2,dn an, dn an1 , dn dn 2,dn 2 = (dn 3, an 2)dn 2 an 2,dn 2 dn 3dn an , dn an1 , dnan2, dndn3,d2 = (ai, a2)dn an, dn ani, dn a2, dn ai,即dn是ai, a2, an的一個公約數(shù)。另一方面，對于 ai, a2, , an的任何公約數(shù) d,由定理2的推論及d2, , dn的定義，依次得 出dai,da2dd2,dd2,da3dd3,d dni , d and dn,因此dn是ai, a2, an的公約數(shù)中的最大者，即dn =

31、(ai, a2, an)。證畢。例i 證明：若n是正整數(shù)，則21n 4是14n 3 既約分?jǐn)?shù)。解由定理i得到(2in 4, i4n 3) = (7n i, i4n 3) = (7n i, i) = io注：一般地，若(x, y) = i,那么，對于任意 的整數(shù)a, b,有(x, y) = (x ay, y) = (x ay, y b(x ay) = (xay, (ab i)y bx),因此，一xay一 是既約分?jǐn)?shù)。(ab i) y bx例2 證明：i2i | n22n i2, n Z。解由于 121 = 112, n2 2n 12 = (n1)211,所以，若112 (n1)211,則11 (

32、n 1)2,因此，由定理4的推論1得至ij11 n 1, 112 (n1)2。再由式(3)得到112 11 ,這是不可能的。所以式(3)不能成立。注：這個例題的一般形式是：設(shè)p是素數(shù)，a, b是整數(shù)，則pk|(an b)kpk 1c,其中c是不被p整除的任意整數(shù)，k是任意的大 于1的整數(shù)。例3 設(shè)a, b是整數(shù)，且9 a2 abb2,(4)則 3 (a, b)。解由式(4)得到9 (ab)23ab 3 (ab)23ab3 (a b)23 a b9 (ab)2。再由式(4)得到9 3ab 3 ab。因此，由定理4的推論1,得到3 a 或 3 bo若3 a,由式(5)得到3 b;若3 b,由(5)

33、式也得到3 a。因此，總有3 a且3 b。由定理2的推論推出3 （a, b）。例4 設(shè)a和b是正整數(shù)，b > 2 ,則2b1 | 2aa < b,且2b1 2a 1。(6)成立，則2b 12a2b2a21)2,2a(2 b aa = 1,即b = 2,這是不可能的,所以式（6）不成立。（ii）若2= b,且式（6）成立，則由式（6）得到2a1 （2a 1）22a1 22a122a3,于是b = a = 1,這是不可能的，所以式（6）不成立。(iii)若a > b,記 a = kb r, 0r < b,此時2 kb1 =(2b其中Q是整數(shù)。2a1)(2(k 1)b2(k

34、2)b(2 b 1)Q,所以1 = 2r(2kb1)二1)1)Q其中Q2b（2r是整數(shù)。1 2a=2r(2 b 1), 因此12b1)Q1)1 2r在（i ）中已經(jīng)證明這是不可能的，所以式 成立。=(2b1,(6)不能綜上證得2b 112a1。習(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, c無平方因子，a2 b2c, 證明：a bo6 .設(shè)n是正整數(shù)，求C12n，C2n， ，c2n1的 最大公約數(shù)。第四節(jié)最小公倍數(shù)定義

35、1 整數(shù)a1, a2, , ak的公共倍數(shù)稱為 a1, a2, , ak的公倍數(shù)。a1，a2, , ak的正公倍數(shù) 中的最小的一個叫做 a1, a2, , ak的最小公倍 數(shù)，記為a1, a2, , ak。7 理1下面的等式成立：8 i ) a, 1 = |a| , a, a = | a| ;(ii) a, b = b, a;(iii) a1, a2, ak = | a”，| a2|, | ak|;(iv )若 a b,則a, b = | b|。證明留作習(xí)題。由定理1中的結(jié)論（話）可知，在討論ai, a2, ,ak的最小公倍數(shù)時，不妨假定它們都是正整 數(shù)。在本節(jié)中總是維持這一假定。最小公倍數(shù)和

36、最大公約數(shù)之間有一個很重 要的關(guān)系，即下面的定理。定理2 對任意的正整數(shù) a, b,有a, b=ab(a,b)證明設(shè)m是a和b的一個公倍數(shù)，那么存在整數(shù)ki, k2,使得m = aki, m = bk2,因此aki = bk2。(1)于是a . b , k1k2 o (a, b) (a, b)由于（島磊）=1，所以由第三節(jié)定理 |ki,即 ki -b-t , (a,b)(a,b)其中t是某個整數(shù)。將上式代入式（1）得到(2)t,由式（2）所確因此 a與b的ab m =1 。(a,b)另一方面，對于任意的整數(shù) 定的m顯然是a與b的公倍數(shù),公倍數(shù)必是式(2)中的形式，其中t是整數(shù)。當(dāng)t = 1時，

37、得到最小公倍數(shù)aba, b=(a,b)證畢。推論1兩個整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除。證明 由式(2)可得證。證畢。這個推論說明：兩個整數(shù)的最小公倍數(shù)不但 是最小的正倍數(shù)，而且是另外的公倍數(shù)的約數(shù)。推論2 設(shè)m , a, b是正整數(shù)，則ma, mb=ma, b。證明由定理2及第三節(jié)定理2的推論得到22m ab m ab mabma, mb = = ma, b。(ma, mb) m(a, b) (a, b)證畢。定理3對于任意的n個整數(shù)ai, a2, , an,ai, a2 = m2, m2, a3 = m3, mn 2, an 1=mn 1, mn 1, an = mn, 則a1,

38、 a2,an = mn。證明我們有mn = mn1, anmn 1mn ,an m n,mn1=mn 2,an 1mn 2 mn1 m n , anmn, an 1mn 1mn,mn2=mn 3,an 2mn 3 mn 2 mn, anmn, an 1mn, an 2 mn,m2 = ai, a2an mn,a2 mn, ai mn,即mn是ai, a2, an的一個公倍數(shù)。另一方面，對于 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。證明 必要性因為(ai, a2)= i,由定理2得到ai a2ai, a2 = aia2。（a1，a2）由(ai, a3)= (a2, a3)= i及第三節(jié)定理 4推論3得到(aia2, a3)= i,由此及定理3得到ai, a2, a3 = ai, a2, a3 = aia2, a3 = aia2a3 。如此繼續(xù)下去，就得到式(3)。充分性用歸納法證明。當(dāng) n = 2時，式(3)成為ai, a2

40、= aia2。由定理2a1a2，、,aia2 = ai, a2 = (ai, a2)= 1,(ai, a2)即當(dāng)n = 2時，充分性成立。假設(shè)充分性當(dāng)n = k時成立，即ai, a2, , ak = aia2 ak(ai, aj) = 1, 1 i, jk, i j。對于整數(shù)ai, a2, ak, ak + i,使用定理3中的記號，由定理3可知ai, a2, ak, ak + i = mk, ak + i。(4)其中mk = ai, a2, ak。因此，如果ai, a2, ak, ak + i = aia2 akak + i,那么，由此及式(4)得到mkak iai, a2, ak, ak +

41、 i = mk, ak + i=(mk,ak i)aia2 akak + i,即mk =aia2 ak , (mk, ak i)顯然 mk aia2 ak, (mk, ak + i)i。所以若使上式成立，必是(mk, ak + i) = i,(5)并且mk = aia2 ak 。(6)由式(6)與式(5)推出(ai, ak + i) = i, i i k；由式(6)及歸納假設(shè)推出(ai, aj) = 1,1 i, jk, i j。(8) 綜合式 與式(8),可知當(dāng)n = k 1時，充分性 成立。由歸納法證明了充分性。證畢。定理4有許多應(yīng)用。例如，如果mi, m2,mk是兩兩互素的整數(shù)，那么，要

42、證明m =mim2 mk整除某個整數(shù) Q,只需證明對于每個 i, 1 i k,都有mi Q。這一點在實際計算 中是很有用的。對于函數(shù)f(x),要驗證命題“m f(n), n Z”是否成立，可以用第二節(jié)例5中的方法，驗證"m f(r), r = 0, 1, m1”是否成立。這需要做 m次除法。但是，若分別 驗證 " mi f(ri), ri = 0, 1, , mi 1,1 ik”是否成立，則總共需要做m1m2mk次除法。后者的運算次數(shù)顯然少于前者。例1 設(shè)a,b,c是正整數(shù)，證明：a, b, c(ab, bc, ca) = abc。解由定理3和定理2有a,bca, b, c

43、 = a, b, c = /ro .,.，(a,b, c)(9)由第三節(jié)定理5和定理2的推論，(ab, bc, ca) = (ab, (bc, ca) = (ab, c(a, b)= (ab,abca,b、 (aba, b, abc)a, bab(a,b, c)a,b(10)聯(lián)合式(9)與式(10)得到所需結(jié)論。例2對于任意的整數(shù)ai, a2, an及整數(shù)k, 1 k n,證明：a1, a2，, an = a1, ak,ak + 1, an解 因為ai,a2,an是ai,ak,ak + 1,an的公倍數(shù)，所以由定理 2推論，推出ai, ak ai, a2, an,ak + i, an ai,

44、a2, an,再由定理3推論知ai, ak, ak + i, an ai, a2, an。(ii)另一方面，對于任意的ai (i i n),顯然aiai, ak, ak + i, an,所以由定理3推論可知ai, a2, an ai, ak, ak + i, an,聯(lián)合上式與式(ii)得證。例3 設(shè)a, b, c是正整數(shù)，證明：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, ab

45、c, 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, abcc, aa2c, bc2, bcac2a, c2b, 由此得證。=abc, a, b2c, a, acc, a,=abc, a2b, b2c, b2a, ac2,=abc, a2b, a2c, b2c, b2a,習(xí)題四1. 證明定理1。2. 證明定理3的推論。3. 設(shè)a, b是正整數(shù)，證明：(a b)a, b= ab, a

46、 b。4. 求正整數(shù) a, b,使得a b = 120, (a, b) =24, a, b = 144。5. 設(shè)a, b, c是正整數(shù)，證明：22a, b, c(a,b,c)a, bb,c c, a (a, b)(b,c)(c, a) °6.設(shè)k是正奇數(shù)，證明：129 1k2k9k。第五節(jié)輾轉(zhuǎn)相除法本節(jié)要介紹一個計算最大公約數(shù)的算法一一輾轉(zhuǎn)相除法，又稱Euclid算法。它是數(shù)論中的一個重要方法，在其他數(shù)學(xué)分支中也有廣泛的應(yīng)用。定義1下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn) 相除法。設(shè)a和b是整數(shù)，b 0,依次做帶余數(shù)除法：a =bqiri,0<ri<|b|，b =ri q2r2,0

47、<r2<口，rk i = rkqk + irk + i, 0 < rk + i <rk ,(i)rn 2 = rn iqnrn,0 < rn <rn-i ,rn i = rnqn + i o由于b是固定的，而且| b| > ri > r2 >,所以式(i)中只包含有限個等式。下面，我們要對式(i)所包含的等式的個數(shù)， 即要做的帶余數(shù)除法的次數(shù)進行估計。引理i 用下面的方式定義 Fibonacci數(shù)列Fn：Fi = F2 = i, Fn = Fn iFn 2, n 3,那么對于任意的整數(shù) n 3,有Fn >n 2,(2)其中證明容易驗證

48、2當(dāng)n = 3時，由1. 5F3 = 2 > 2可知式(2)成立。假設(shè)式(2)對于所有的整數(shù) k n (n 3)成立，即Fk >k 2, k n,則3(Fn + 1 = Fn1)=Fn1 >32 二n 2n 1,n 3_即當(dāng)k = n 1時式(2)也成立。由歸納法知式 (2)對一切n 3成立。證畢。定理1(Lame) 設(shè)a, b N, a > b,使用在式 (1)中的記號，則n < 5log1ob。證明在式(1)中，rn1, qn + 12, qi 1(1 i n),因此rn 1 = F2 ,rn 12rn2 = F3 ,rn 2rn 1rnF3F2 = F4 ,

49、2Fn + 1Fn =Fn + 2 ,由此及式(2)得logiobn=(1.5)n，nlogi 1n,25這就是定理結(jié)論。證畢。定理2 使用式(1)中的記號，記P0 = 1 , Pi = qi, Pk = qkPk 1 Pk 2, k 2,Qo = 0, Q1 = 1, Qk = qkQk 1 Qk 2, k 2, 則aQkbPk = ( 1)k h, k = 1,2, , n 。 證明 當(dāng)k = 1時，式(3)成立。當(dāng)k = 2時，有Q2 = q2Q1Qo = q2, P2 = q2P1Po = q2q11,此時由式得到aQ2 bP2 = aq2 b(q2q11) = (a bq1)q2 b

50、=門q2b = 2,即式成立。假設(shè)又行1 k < m (1 mn)式(3)成立，由此假設(shè)及式(1)得到aQmbPm= a(qmQm 1 Qm 2)b(q mPm 1Pm 2)=(aQm 1bPm1)qm(aQm 2bPm 2)=(1)m 2rm 1qm ( 1)m3rm 2=(1)m ( (rm 2rm iqm)=(1)m 1rm ,即式(3)當(dāng)k = m時也成立。定理由歸納法得證。 證畢。定理3使用式(1)中的記號，有rn = (a, b)o證明 由第三節(jié)定理1,從式(1)可見rn = (rn 1, rn) = (rn 2, rn 1)= (r1，=(b, r1)=(a, b)。證畢。

51、現(xiàn)在我們已經(jīng)知道，利用輾轉(zhuǎn)相除法可以求 出整數(shù)x, y,使得ax by = (a, b)。(4)為此所需要的除法次數(shù)是 O(log10b)。但是如果只 需要計算(a, b)而不需要求出使式(4)成立的整數(shù) x與y,則所需要的除法次數(shù)還可更少一些。例1 設(shè)a和b是正整數(shù)，那么只使用被 2 除的除法運算和減法運算就可以計算出(a, b)。解下面的四個基本事實給出了證明：(i )若 a b,則(a, b) = a;(ii)若 a = 2 a1, 2 |a1，b 2 bi, 2 | b1，1,則(a, b) = 2 (2a1, b1)；(ill)若2 | a, b 2 b1, 2 |b1，貝U(a,

52、b) = (a,b1)；( iv)若a b .2|a, 2|b,則(a,b) (|2-他)。在實際計算過程中，若再靈活運用最大公約數(shù)的性質(zhì)(例如第三節(jié)定理4的推論)，則可使得求最大公約數(shù)的過程更為簡單。例2 用輾轉(zhuǎn)相除法求(125, 17),以及x, y, 使得125x17y = (125, 17)。解做輾轉(zhuǎn)相除法：125 = 7 176, q1 = 7, 口 =6,17 = 2 65, q2 = 2, r2 =5,6 = 151, q3 = 1,r3 =1,5 = 5 1, q4 = 5。 由定理 4, (125,17) = r3 = 1。利用定理2計算(n = 3)Po = 1, P1 = 7, P2 = 2 71 = 15,P3 = 1 157 = 22,Qo = 0, Q1 = 1, Q2 = 2 10 = 2,Q