輾轉相除法的證明

輾轉相除法的證明

設兩數為a、b(b＜a)，求它們最大公約數的步驟如下：用b除a，得a＝bq＋r（0≤r＜b）（q是這個除法的商）。若r=0,則b是a和b的最大公約數。若r≠0,則繼續考慮。

首先，應該明白的一點是任何 a 和 b 的公約數都是 r 的公約數。要想證明這一點，就要考慮把 r 寫成 r=a-bq。現在，如果 a 和 b 有一個公約數 d，而且設 a=sd , b=td, 那么 r = sd-tdq = (s-tq)d。因為這個式子中，所有的數（包括 s-tq )都為整數，所以 r 可以被 d 整除。

對于所有的 d 的值，這都是正確的；所以 a 和 b 的最大公約數也是 b 和 r 的最大公約數。因此我們可以繼續對 b 和 r 進行上述取余的運算。這個過程在有限的重復后，可以最終得到 r=0 的結果，我們也就得到了 a 和 b 的最大公約數。