先看費(fèi)馬小定理：
費(fèi)馬小定理是
數(shù)論中的一個(gè)重要定理,其內(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
逆元：
設(shè)m為正整數(shù)，a為正整數(shù)，如果存在a' 使得：
a X a' = 1（mod m）
a'叫做a的逆元。密碼學(xué)中用到了這個(gè)結(jié)論。RSA.
證明:x^(MOD-1) = 1 (mod MOD)
x*x^(MOD-2) = 1 (mod MOD) x^(MOD-2)為其逆元
其中MOD 為素?cái)?shù) ， x要小于MOD,如果x>=MOD,可以先對(duì)x取MOD,這不會(huì)影響結(jié)果。
另一種想法：
其實(shí)用莫線性方程解a'亦可。 擴(kuò)展歐幾里德...