同餘（十）——歐幾裡得輾轉相除法

往期文章

導讀

歐幾裡得算法又稱輾轉相除法。可以用來求兩個整數的最大公約數，兩個多項式的最大公因式。在之前的文章《》已經使用了這個算法。本期我們單獨來研究它。

回顧

從二年級學習帶餘數除法後，我們知道

7÷2=3……1

寫成一般的形式：

設m是非零整數，n是任意整數，則可以唯一确定整數q和r,

使得

n÷m=q……r （0≤r＜|m|）

即

n=m×q+r （0≤r＜|m|）

其中q和r分别稱為商和餘數。

引理若有等式

n=m×q+r ①

則有(n，m)=(m，r)。

證明：若p|m，p|r, 由①得，p|n。這就是說m、r的公約數都是n、m的公約數。

反過來若p|n, p|m，則p一定整除它們的組合

r=n-m×q

這就是說p是m、r的公約數。由此可見，如果n、m有一個最大公約數p，那麼p也是m、r的最大公約數。 □

應用

找1804與328的最大公約數,

1804÷328=5……164

因此

1804=5×328+164

可知

（1804, 328）=（328,164）

繼續進行上述的步驟

328=2×164+0

所以

（328,164）=（164, 0）=164

故

（1804, 328）=164.

下面給出一般化的算法。

輾轉相除法

算法 設n，m是兩個不全為0的整數，

找出最大公因數（n, m）.

分析

我們可以假設,m≠0，這樣通過連除我們能寫出，

n=q1×m+r1 （0≤r1＜|m|）

m=q2×r1+r2 （0≤r2＜|r1|）

r1=q3×r2+r3 (0≤r3＜|r2|）

… … … …

隻要餘數不為0就繼續寫下去，從右邊的不等式，我們可以看到一連串的餘數形成一個嚴格遞減數列

m>|r1|>|r2|>……≥0

因此最多m步，0這個餘數一定出現。

rs-2=qs×rs-1+rs

rs-1=qs+1×rs+0

這是我們知道

(n,m)=(m，r1)，

(m，r1)=(r1，r2)，

(r1，r2)=(r2，r3)，

……

(rs-1，rs)=(rs，0)，

(rs，0)=rs，

得到

(n,m)=rs;

□