乘法逆元：
乘法逆元的提出是基于模运算的性质。模运算对于加减乘的分配率成立。但是对于除法的分配率并不成立。即
(a+b)%p = (a%p+b%p)%p
(a-b)%p = (a%p-b%p)%p
(a*b)%p = (a%p*b%p)%p
(a/b)%p = (a%p/b%p)%p 不成立
于是就引入了乘法逆元的的概念：
- 若在 mod p 意义下，对于一个整数 a，有 $a*x\equiv1$(mod p), 那么 x 与 a 互为对方的乘法逆元。
- a 存在 mod p 的乘法逆元的充要条件是：a 与 p 互质，否则 a mod p 就等于 0 了。
- (a/b)% p 等价于（a*b 的逆元）% p
- 求解逆元的方式：费马小定理，扩展欧几里得，线性递推。
使用费马小求解乘法逆元
由上述充要条件（a 与 p 互质）可得，a 必定不是 p 的倍数，因此 $a^{p-1} \equiv 1$(mod p)。由此可推出：$a*a^{p-2} \equiv 1$(mod p)。因此 $a^{p-2}$ 是 a 的逆元。
费马小定理：
定理：假如一个 a 是一个整数，p 是一个质数，那么则有如下定理：
如果 a 是 p 的倍数，则有 $a^p \equiv a$(mod p) 即： $a^p \% p = a\% p$
因为 $a=x*p$ 所以 $a^p \% p = (xp)^{p}\% p = x$
同理得 $a\% p = (xp)\% p = x $
- 如果 a 不是 p 的倍数，则 $a^{p-1} \equiv 1$(mod p) 即： $a^p \% p = a\% p$
links
扩展欧几里得和线性递推极其令人头大，我也是看的一知半解。所以附上我看的觉得比较清晰的几篇文章。
666