乘法逆元：
乘法逆元的提出是基于模运算的性质。模运算对于加减乘的分配率成立。但是对于除法的分配率并不成立。即
(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