歐幾裡得輾轉相除法證明及推論

一、輾轉相除法定義

輾轉相除法：以大數除以小數，如果能整除，那麼小數就是所求的最大公約數（Greatest CommonDivisor：gcd）。否則就用餘數來除剛才的除數；再用這新除法的餘數去除剛才的餘數。依此類推，直到一個除法能夠整除，這時作為除數的數就是所求的最大公約數。即：gcd（x,y）表示x與y的最大公約數，有gcd(x,y)=gcd（y,x%y），如此便可把原問題轉化為求兩個更小數的公約數，直到其中一個數為0，剩下的另外一個數就是兩者的最大公約數。

• 例如：求 4453 和 5767 的最大公約數時，可作如下除法．

  5767÷4453＝1 餘 1314

  4453÷1314＝3 餘 511

  1314÷511 ＝2 餘 292

  511 ÷292 ＝1 餘 219

  292 ÷219 ＝1 餘 73

  219÷73＝3 于是得知，5767 和 4453 的最大公約數是 73。輾轉相除法适用比較廣，比短除法要好得多，它能保證求出任意兩個數的最大公約數。

二、歐幾裡得輾轉相除法證明

輾轉相除法就是給出了一個關系： g c d （ a , b ） = g c d ( b , r ) gcd（a,b）=gcd(b,r) gcd（a,b）=gcd(b,r)，其中a、b、r滿足a=bq+r。

設u同時整除a和b，則有

a = s u , b = t u a=su,b=tu a=su,b=tu

則 r = a − b q = s u − t u q = ( s − t q ) u r=a-bq=su-tuq=(s-tq)u r=a−bq=su−tuq=(s−tq)u，得到u也整除r。反過來，每一個整除b和r的整數 v v v，則有

b = s ′ v ， r = t ′ v . b=s'v，r=t'v . b=s′v，r=t′v.

則 a = b q + r = s ′ v q + t ′ v = ( s ′ q + t ′ ) v a=bq+r=s'vq+t'v=(s'q+t')v a=bq+r=s′vq+t′v=(s′q+t′)v，得到 v v v也整除a。

綜上：a和b的每一個公因子也是b和r的一個因子，反之亦然。是以a和b的全體公因子集合就與b和r的全體公因子集合相同。是以gcd（a,b）=gcd(b,r)。

三、推論

推論一：如果 d = g c d ( a , b ) d=gcd(a,b) d=gcd(a,b)，則能找到正的或負的整數 k k k和 l l l，使得 d = k a + l b . d=ka+lb. d=ka+lb.

我們在使用輾轉相除法時，由于 g c d ( a , 0 ) = a gcd(a,0)=a gcd(a,0)=a,我們可以假設 b ≠ 0 b \neq 0 b​=0。這樣我們能寫出如下

a = b q 1 + r 1 ( 0 < r 1 < b ) a=bq_1+r_1 (0<r_1<b) a=bq1​+r1​(0<r1​<b)公式一

b = r 1 q 2 + r 2 ( 0 < r 2 < r 1 ) b=r_1q_2+r_2(0<r_2<r_1) b=r1​q2​+r2​(0<r2​<r1​)

r 1 = r 2 q 3 + r 3 ( 0 < r 3 < r 2 ) r_1=r_2q_3+r_3(0<r_3<r_2) r1​=r2​q3​+r3​(0<r3​<r2​)

r 2 = r 3 q 4 + r 4 ( 0 < r 4 < r 3 ) r_2=r_3q_4+r_4(0<r_4<r_3) r2​=r3​q4​+r4​(0<r4​<r3​)

…

隻要餘數 r 1 , r 2 , r 3 , r 4 . . . . . r_1,r_2,r_3,r_4..... r1​,r2​,r3​,r4​.....不是0就繼續寫下去。從右邊的不等式，可以看出餘數形成了一個嚴格遞減序列： b > r 1 > r 2 > r 3 > . . . . > 0 b>r_1>r_2>r_3>....>0 b>r1​>r2​>r3​>....>0。是以最多b步，0這個餘數必然出現。

r n − 2 = r n − 1 q n + r n r_{n-2}=r_{n-1}q_n+r_n rn−2​=rn−1​qn​+rn​

r n − 1 = r n q n + 1 + 0 r_{n-1}=r_nq_{n+1}+0 rn−1​=rn​qn+1​+0

此時，我們就得到 r n = g c d ( a , b ) r_n=gcd(a,b) rn​=gcd(a,b);

在公式一中，我們可以推出 r 1 = a − q 1 b r_1=a-q_1b r1​=a−q1​b,是以 r 1 r_1 r1​可以寫成 k 1 a + l 1 b k_1a+l_1b k1​a+l1​b的形式。是以

r 2 = b − q 2 r 1 = b − q 2 ( k 1 a + l 1 b ) = ( − q 2 k 1 ) a + ( 1 − q 2 l 1 ) b = k 2 a + l 2 b r_2=b-q_2r_1=b-q_2(k_1a+l_1b)=(-q_2k_1)a+(1-q_2l_1)b=k_2a+l_2b r2​=b−q2​r1​=b−q2​(k1​a+l1​b)=(−q2​k1​)a+(1−q2​l1​)b=k2​a+l2​b，顯然，通過這一串餘數 r 3 , r 4 . . . . . r_3,r_4..... r3​,r4​.....的結果，推導出 r n = g c d ( a , b ) = k a + l b r_n=gcd(a,b)=ka+lb rn​=gcd(a,b)=ka+lb。

推論二：如果一個素數p整除乘積ab，則p必整除a或b。

因為p整除ab，是以 a b = p r ab=pr ab=pr。

因素數p僅有因子p和1，是以如果p不整除a，則gcd（a，p）=1，根據上面的推論一我們能找到整數 k k k和 l l l，使得 1 = k a + l p 1=ka+lp 1=ka+lp.在等式兩邊同時乘以b，我們得到： b = k a b + l p b = k p r + l p b = p ( k r + l b ) b=kab+lpb=kpr+lpb=p(kr+lb) b=kab+lpb=kpr+lpb=p(kr+lb)，到此顯然p整除b。

同理，當p不整除b時，可以證得p整除a。

綜上，命題“如果一個素數p整除乘積ab，則p必整除a或b”得證。

注意：不妨舉幾個例子印證推論二。

• 13是2652的一個因子，以及2652=6*442，就可以得出13是442的因子。
• 6是240的一個因子，而240=15*16，但6既不是15也不是16的因子。why？這表明p是素數這個前提是不可或缺的。