MENU

【乘法逆元】费马小定理,扩展欧几里得,线性递推

June 7, 2020 • ACM

乘法逆元:

乘法逆元的提出是基于模运算的性质。模运算对于加减乘的分配率成立。但是对于除法的分配率并不成立。即

(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是一个质数,那么则有如下定理:

    1. 如果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 $

    2. 如果a不是p的倍数,则$a^{p-1} \equiv 1$(mod p) 即: $a^p \%p = a\%p$

links

扩展欧几里得和线性递推极其令人头大,我也是看的一知半解。所以附上我看的觉得比较清晰的几篇文章。

什么是扩展欧几里得

扩展欧几里得

浅谈乘法逆元的三种解法

Archives QR Code
QR Code for this page
Tipping QR Code