先看費馬小定理：
費馬小定理是
數(shù)論中的一個重要定理,其內(nèi)容為:
假如p是質(zhì)數(shù)，且(a,p)=1，那么 a^(p-1) ≡１（mod p）
假如p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的(p-1)次方除以p的余數(shù)恒等于1
逆元：
設m為正整數(shù)，a為正整數(shù)，如果存在a' 使得：
a X a' = 1（mod m）
a'叫做a的逆元。密碼學中用到了這個結論。RSA.
證明:x^(MOD-1) = 1 (mod MOD)
x*x^(MOD-2) = 1 (mod MOD) x^(MOD-2)為其逆元
其中MOD 為素數(shù) ， x要小于MOD,如果x>=MOD,可以先對x取MOD,這不會影響結果。
另一種想法：
其實用莫線性方程解a'亦可。 擴展歐幾里德...