『壹』 歐幾里得輾轉相除法
輾轉相除法， 又名歐幾里德演算法（Euclidean algorithm），是求最大公約數的一種方法。它的具體做法是：用較大數除以較小數，再用出現的余數（第一餘數）去除除數，再用出現的余數（第二餘數）去除第一餘數，如此反復，直到最後余數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。 另一種求兩數的最大公約數的方法是更相減損法。輾轉相除法是用來計算兩個整數的最大公約數。假設兩個整數為a和b，他們的公約數可以表示為gcd(a,b)。如果gcd(a,b) = c,則必然a = mc和b = nc。a除以b得商和余數，余數r可以表示為r = a - bk，k這里是系數。因為c為 a和b的最大公約數，所以c也一定是r的最大公約數，因為r = mc - nck = (m-nk)c。
因此gcd(a,b) = gcd(b,r)，相當於把較大的一個整數用一個較小的余數替換了，這樣不斷地迭代，直到余數為0，則找到最大公約數。
舉例兩個整數為1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此時余數為零，則21為兩個數的最大公約數。
貝祖公式表明對於任意兩個整數a和b，都可以找到一對可為負的整數x和y，可以使等式xa + yb = m，其中m為a和b的最大公約數，合理性稍加思考可得。如果m為1說明a和b互素。所以在互素的情況下，xa + yb = 1。這個等式對於求乘法逆元有很大的幫助。
那麼如何通過貝祖公式及擴展歐幾里得演算法來求乘法逆元呢？舉一個例子來描述什麼是乘法逆元。如果ab mod m = 1，或者可以表示為ab ≡ 1 mod m，這里b就是a關於模數m的乘法逆元。計算乘法逆元的方法就是擴展歐幾里得演算法，以下通過一個例子來幫助理解：
假設我們要求3 關於模26的乘法逆元(隱含了3和26的最大公約數為1，即互素)。當a = 3，b = 26，則根據貝祖公式，存在整數x和y，3x + 26y = 1。
思路就是等號兩邊同時mod 26，等式則變成(3x + 26y) mod 26 = 1 mod 26，根據模運算的性質(a + b) mod m = (a mod m + b mod m) mod m。
所以展開等式(3x mod 26 + 26y mod 26) mod 26 = 1 mod 26。化簡最終得到(3x mod 26) mod 26 = 1 mod 26。我們發現3x mod 26 = 1正好符合了乘法逆元的定義，所以歐幾里得演算法就是解x的關鍵。
下面將通過輾轉相除法來求x：
第一步：26 = 3 * 8 + 2
第二步：3 = 2 * 1 + 1
統一將余數換到等號左邊：
2 = 26 - 3 * 8
1 = 3 - 2 * 1
將第一行的2替換到第二行，保證等式左邊永遠為1，等式右邊變成僅由3x + 26y組成。
1 = 3 - (26 - 3 * 8) * 1 = 3 * 9 + (-1) * 26
可得x = 9
最後9就是3關於模26的乘法逆元。它可以應用於仿射加密。
附：仿射加密的公式e(x) = ax + b mod m， 其中a與m互素， b為移動距離。
仿射解密公式d(x) = a-1(x - b) mod m
『貳』 Rust語言編程實例100題-016
題目： 給定兩個正整數m=128和n=60，求其最大公約數和最小公倍數。
程序分析：
（1）最小公倍數=輸入的兩個數之積除於它們的最大公約數，關鍵是求出最大公約數；
（2）求最大公約數用輾轉相除法（又名歐幾里德演算法）
1）證明：設c是a和b的最大公約數，記為c=gcd(a,b),a>=b,
令r=a mod b
設a=kc，b=jc，則k，j互素，否則c不是最大公約數
據上，r=a-mb=kc-mjc=(k-mj)c
可知r也是c的倍數，且k-mj與j互素，否則與前述k，j互素矛盾,
由此可知，b與r的最大公約數也是c，即gcd(a,b)=gcd(b,a mod b)，得證。
2）演算法描述：
第一步：a ÷ b，令r為所得余數（0≤r 第二步：互換：置 a←b，b←r，並返回第一步。
輸出格式： 第一行輸出最大公約數，第二行輸出最小公倍數。
知識點 ：循環
程序執行結果：