輾轉(zhuǎn)相除法是用來計算兩個整數(shù)的最大公約數(shù)筐咧。假設兩個整數(shù)為a和b越妈，他們的公約數(shù)可以表示為gcd(a,b)檩赢。如果gcd(a,b) = c,則必然a = mc和b = nc闪盔。a除以b得商和余數(shù)，余數(shù)r可以表示為r = a - bk障斋，k這里是系數(shù)纵潦。因為c為 a和b的最大公約數(shù)，所以c也一定是r的最大公約數(shù)垃环，因為r = mc - nck = (m-nk)c邀层。
因此gcd(a,b) = gcd(b,r)，相當于把較大的一個整數(shù)用一個較小的余數(shù)替換了晴裹，這樣不斷地迭代被济，直到余數(shù)為0，則找到最大公約數(shù)涧团。
舉例兩個整數(shù)為1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此時余數(shù)為零只磷，則21為兩個數(shù)的最大公約數(shù)经磅。
貝祖公式表明對于任意兩個整數(shù)a和b，都可以找到一對可為負的整數(shù)x和y钮追，可以使等式xa + yb = m预厌，其中m為a和b的最大公約數(shù)，合理性稍加思考可得元媚。如果m為1說明a和b互素轧叽。所以在互素的情況下，xa + yb = 1刊棕。這個等式對于求乘法逆元有很大的幫助炭晒。
那么如何通過貝祖公式及擴展歐幾里得算法來求乘法逆元呢？舉一個例子來描述什么是乘法逆元甥角。如果ab mod m = 1网严，或者可以表示為ab ≡ 1 mod m，這里b就是a關(guān)于模數(shù)m的乘法逆元嗤无。計算乘法逆元的方法就是擴展歐幾里得算法震束，以下通過一個例子來幫助理解：
假設我們要求3 關(guān)于模26的乘法逆元(隱含了3和26的最大公約數(shù)為1，即互素)当犯。當a = 3垢村，b = 26，則根據(jù)貝祖公式嚎卫，存在整數(shù)x和y嘉栓，3x + 26y = 1。
思路就是等號兩邊同時mod 26驰凛，等式則變成(3x + 26y) mod 26 = 1 mod 26胸懈，根據(jù)模運算的性質(zhì)(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涌献。我們發(fā)現(xiàn)3x mod 26 = 1正好符合了乘法逆元的定義胚宦，所以歐幾里得算法就是解x的關(guān)鍵。
下面將通過輾轉(zhuǎn)相除法來求x：
第一步：26 = 3 * 8 + 2
第二步：3 = 2 * 1 + 1
統(tǒng)一將余數(shù)換到等號左邊：
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關(guān)于模26的乘法逆元卜壕。它可以應用于仿射加密您旁。
附：仿射加密的公式e(x) = ax + b mod m， 其中a與m互素轴捎， b為移動距離鹤盒。
仿射解密公式d(x) = a-1(x - b) mod m
