乘法逆元的計算方法如下:
1、費馬小定理
由費馬小定理ap-1≡1，變形得 a*ap-2≡1(mod p)，答案已經很明顯了：若a,p互質,因為a*ap-2≡1(mod p)且a*x≡1(mod p)，則x=ap-2(mod p)，用快速冪可快速求之。
2、擴展歐幾裏得
我們都知道模就是余數，比如12%5=12-5*2=2，18%4=18-4*4=2。（/是程序運算中的除）
那麽ax≡1 (mod p)即ax-yp=1。把y寫成+的形式就是ax+py=1，為方便理解下面我們把p寫成b就是ax+by=1。就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然後就可以用擴展歐幾裏得求了。
乘法逆元的定義：若存在正整數a,b,p, 滿足ab = 1(mod p), 則稱a 是b 的乘法逆元, 或稱b 是a 的乘法逆元。