同餘（十）——歐幾裡得輾轉相除法
往期文章
導讀
歐幾裡得算法又稱輾轉相除法。可以用來求兩個整數的最大公約數，兩個多項式的最大公因式。在之前的文章《》已經使用了這個算法。本期我們單獨來研究它。
回顧
從二年級學習帶餘數除法後，我們知道
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;
□
最新文章
-
太師修行問答48：人生隻是演戲瑜伽也能修禅，能達到幾禅
7分鐘前 -
![[書法]閑暇草書彙03](https://m.74hao.com/zb_users/upload/2024/10/202410161729086639361289.png)
[書法]閑暇草書彙03
24分鐘前 -
3D技巧：兩碼和差選号法
46分鐘前 -
“落日無情最有情，遍催萬樹暮蟬鳴”楊萬裡詩五首，風格清新自然
1小時前 -
《玄理賦》五行生克的太過不及 等
1小時前 -
《老山1984-1989，中越老山之戰實錄》連載之二：118團8連收敲掉54
2小時前 -
攝影：故鄉的秋色（2）
2小時前 -
論入宅歸火擇吉（續）第二，坐向要吉 坐向要吉，主要是指所選日課
2小時前
有話要說...