首先说一下逆元的定义 存在一个数a使得ax对y进行取余运算，得到的值是1，则称a是x的逆元。在数学中记做：a * x = 1(mod p) 例如x = 4，y = 11，3x = 1(mod y)，3 × 4 = 12，12 mod 11 = 1 , 3就是x的逆元。
对于求逆元这一操作在计算机领域主要用于非对称加密，如我们常见的RSA加密算法等。
那应该求得这个逆元呢，我们知道，再求两个数的最大公约数的时候可以用欧几里得算法。 在欧几里得算法中，通过辗转相除，当余数为0的时候最后的除数就是两个数的最大公约数。
而在其扩展算法中，我们已知两个数的最大公约数，我们已知 ax = 1(mod p), 展开就是 ax mod p = 1，首先我们先求 p = x1 * a + p1，然后 p = a，a = p1，迭代下去直到pi = 1（i表示出了i次）为止 然后就可以得出 1 = p - xi * a，此时的a和p已经不是我们初始的a和p了，我们需要往前推，推到 1= xa + yp 为止，此时得出的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 = 4 × 2 + 1 //注释：p3 = 1
此时得到：1 = 9 - 2 × 4，开始往前推直到推出 1= xa + yp 从上述式子中可以得知 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的逆元 -9 -9对p取余为11 综上11模20的逆元为11
验证 11 × 11 = 121，121 mod 20 = 6 — 1 到此 计算结束
关于更具体的讲解可以阅读下面的文章 扩展欧几里得求逆元
