費馬小定理，費馬定理

費馬小定理，費馬定理

在p是素數的情況下，對任意整數x都有x^p≡x（mod p），這個定理稱為飛馬小定理。其中如果x無法被p整除，我們有x^p-1≡1（mod p）。

把這個式子變形後得到a^-1≡a^p-2（mod p），因此我們可以通過快速冪來求出乘法逆元。

快速冪見http://www.cnblogs.com/wls001/p/5157107.html

乘法逆元擴展歐幾裡得求法見http://www.cnblogs.com/wls001/p/5157162.html