逆元总结

逆元 ：

　　(b/a) (mod n) = (b * x) (mod n)。 x表示a的逆元。并且 a*x ≡ 1 (mod n )  注意：只有当a与n互质的时候才存在逆元

　　求一个最小的正整数x（逆元），使a乘以x对n的取余等于1对n的取余，

费马小定理：

　　假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

　　可以记为：

　　可以求得逆元为  (当m为素数)

扩展欧几里德：

　　当gcd(a, m), ab+mx=1的任意一组整数解(b,x)，b就是a的乘法逆元

正常情况下(gcd(a, m) != 0):

　　(a/b)mod m = a mod (mb) / b;

逆元总结

原文：http://www.cnblogs.com/alihenaixiao/p/5413832.html