首先說壹下逆元的定義。
存在壹個數a使得a x對y進行取余運算，得到的值是壹，則成為a是x的逆元。在數學中記做
a * x = 1(mod p)
例如x = 4，y = 11，3 x = 1(mod y)，3 4=12,12 mod 11 = 1,3就是x的逆元。
對於求逆元這壹操作在計算機領域主要用於非對稱加密，如我們常見的RSA加密算法等。
那應該求得這個逆元呢，我們知道，再求兩個數的最大公約數的時候可以用歐幾裏得算法。
在歐幾裏得算法中，通過輾轉相除，當余數為0的時候最後的除數就是兩個數的最大公約數。
而在其擴展算法中，我們已知兩個數的最大公約數，我們已知 a x = 1(mod p),
展開就是 a x mod p = 1，首先我們先求 p = x1 * a + p1，然後p = a，a = p1，叠代下去
知道pi = 1（i表示出了i次）為之，然後就可以得出 1 = p - xi * a，此時的a和p已經不是我們初始的a和p了，我們需要往前推，推到 1= y p + x*a 為止，此時得出的x就是a的逆元，當然如果逆元x為負數，或者比p大，要對其就行取余操作。
舉個例子 11 = 1(mod 20)求11的逆元
20 = 1 * 11 + 9 //註釋：此時x1 = 1， a = 11，p = 20，p1 = 9，執行p = a，a = p1
11 = 1 * 9 + 2 //註釋：x2 = 1，a = 9，p2 = 2。
9 = 2 * 4 + 1 //註釋：p3 = 1，
1 = 9-2 * 4。
從上述式子中可以得知 9 = 20-11
1 = 20-11-2 * 4
同時 2 = 11 -9
1 = 20 -11 -4 * (11-9)
已知 9 = 20 - 11
1 = 20 -11 -4 * (11-(20-11))
1 = 20 -11 -4 * (11-20+11)
合並同類項得
1 = 5 * 20 - 9 * 11
1 = y * 20 + x * 11
x為a的逆元 x = -9
x對p取余，x = 11
驗證 11 * 11 = 121，121 mod 20 = 6 --- 1
到此 計算結束