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