1.3最大公因數與最小公倍數

1、13最大公因數與最小公倍數設a、b是不全為零的兩個整數，d是一個非零整數，如果dIa且dIb，那么稱d為a、b的公因數注意到，當dIa且dIb時，則dWla丨或dWlb丨中必有一個成立（對a、b中不為零的數成立）.因此，a、b的公因數中有一個最大的，這個數稱為a、b的最大公因數，記為（a,b）.如果（a,b）=l,那么我們稱a、b互素.在討論最大公因數的性質之前，我們不加證明地引入一個在小學就接觸到的、數論中最基本、最常用的結論帶余數除法設a、b是兩個整數，aMO,則存在唯一的一對整數q和r,滿足b=aq+r,OWrVlb丨，其中q稱為b除以a所得的商，r稱為b除以a所得的余數.性質1設d=（

2、a,b）,則存在整數x、y,使得ax+by=d.這個結論就是著名的貝祖（Bezout）定理.證明我們利用帶余除法來處理，此結論的證明過程又是求a、b的最大公因數的過程,它被稱為“輾轉相除”不妨設a、b都不為零（當a、b中有一個為零時，結論是顯然的），且丨a|bI.設b=aq+r，其中OWrIaI,q、r為整數.若r=0,則輾轉相除到此為此；否llllll則用a去除以r，得等式a=rq+r,0Wrrr，因此輾ll222ll23轉相除到某一步后，所得的r=0，于是，我們得到了如下的一系列式子：k十1b=aq+r，0rIaI；111a=rq+r，0rr；12221r=rq+r，0rr；123332r

3、=rq+r，0rl.ab證明：若(a,b)=1，貝(a,a+b)=1(這由性質3可推得)，從而，由a+bIab及=(a,(a,a+b)=1,得a+bIb，但是a+bb,故a+bIb不可能成立.所以，(a,b)1.說明在輾轉相除求a、b的公因數的討論中，可知對任意整數x,都有(a,b)b+ax),這一點在利用最大公因數處理數論問題時經常被用到.例2設正整數a、b、c滿足b2=ac.證明：(a,b)2=a(a,c).證明：如果我們能夠證明：(a,b)2=(a2,b2),那么結合性質11,可知(a,b)2=C2，b2)=C2，ac)=a(a,c)命題獲證為此，記d=(a,b),設a=du,b=dv，

4、則由性質11可知u、v是兩個互素的正整數,為證C2+b2)=d2只需證明：C2,V2)=1.利用貝祖定理，知存在整數x、y,使得ux+vy=1,故=l+vCy2一2y),結合性質3可知(u2,v)=l，交換u2與v的位置，同上再做一次，即有(v2,u2)=1.所以，命題成立說明利用下一節(jié)的算術基本定理可以非常方便地證出：(a2,b2)=(a,b)2，但遺憾的是我們還沒給出該定理的證明，通常都是先建立最大公因數理論再去證算術基本定理，這里不用該定理是不希望掉入“循環(huán)論證”的漩渦，讀者在學習中應認真掌握其中的邏輯結構例3求所有的正整數a、b(aWb),使得ab=300+7a,b+5(a,b).解：

5、設a,b=x,(a,b)=y,由性質8可知ab=xy，于是，變?yōu)閤y=300+7x+5y,即(x5)(y7)=5X67.由于a,b三(a,b),故xy,進而x5y7,只有如下的兩種情形.情形一x5=67且y7=5；此時，x=72,y=12，于是，可設a=12n,b=12m,(m,n)=1,并有(12n)(12m)=ab=xy=12X72，結合aWb，只能是(m,n)=(1,6)或(2,3),對應的(a,b)=(12,72)或(24,36).情形二x5=335且y7=1；對應地，x=340,y=8,但y=(a,b)是x=a,b的因數，而8340，所以，此時無解.綜上，符合條件的(a,b)=(12

6、,72)或(24,36).例4求所有的正整數a、b,使得TOC o 1-5 h z(a,b)+9a,b+9(a,b)=7ab解：記(a,b)=d,設a=dx,b=dy，貝9(x、y)=1(由性質11知)，a,b=dxy(由性質8知)，于是代入可得1+9xy+9(x+y)=7dxy(11)17d=9+9-+-+,Ixy丿xy HYPERLINK l bookmark50 (111所以9V7dW9+9-+-+=28，故2WdW4.U1)1X1當d=2時，由得5xy9(x+y)=1,兩邊乘以5，并將左邊因式分解，得(5x9)(5y9)=86=2X43，故(5x9,5y9)=(1,86)、(86,1)

7、,(2,43)、(43,2).分別求解可知只能是(x,y)=(2,19),(19,2),對應的(a,b)=(4,38),(38,4).分別就d=3,4同上討論，得(a,b)=(4,4).所以，滿足條件的(a,b)=(4,38),(38,4),(4,4).例5Fibonacci數列定義如下：F=F=1,F=F+F,n=1,證明：對12n+2n+1n任意正整數m、n都有(F,F)=巧、.mn(m,n)證明：當m=n時，命題顯然成立.現(xiàn)在不妨設mF,npFF，而F為素數,nqn故(F,F、=(F,F)=1,所以，F(xiàn)=F=1,再由npnqpq2WpWq,可知只能是p=q=2,即n=4.所以，性質成立.例6設n為大于1的正整數.證明：存在從小到大排列后成等差數列(即從第二項起,每一項與它前面那項的差為常數的數列)的n個正整數，它們中任意兩項互素.證明:考慮下面的n個數：n!+1,2X(n!)+1,，nX(n!)+1.這n個正整數組成一個公差為n!的等差數列.我們證明其中任意兩項是互素的.事實上，若存在1Wi1.考慮d的素因子p,可知pI(jx(n!)+l)Cx(n!)+l),即pl(ji)xn!.由性質6可知pIji或pIn!,結合l