逆元的三种求法 (费马小定理,扩展欧几里得,递推求阶乘逆元)

逆元的三种求法

费马小定理,扩展欧几里得,递推求阶乘逆元

逆元

对于一个实数 $A$ 如果存在一个 $x$ 使得 $Ax = 1$,我们就把这个 $x$ 叫做 $A$ 的逆元,记做 $x = A^{-1}$。
在一般数学中,我们所说的逆元就是倒数

但是在数论中,如果一个数字 $A$ 存在一个对 $p$ 的逆元 $x$,就可以写成 $Ax≡1\ mod\ p$ 的形式(此处 $p$ 与 $A$ 互质,若不互质,则不存在逆元)。

逆元的作用

我们知道 取余 的性质:

  1. $(a - b)\%c = (a\%c - b\%c)\%c$
  2. $(a + b)\%c = (a\%c+b\%c)\%c$
  3. $(a\times b)\%c=(a\%c\times b\%c)\%c$

对于基本的四种运算而言,加减乘都符合“分配率”,唯独除法不满足。

$(a\div b)\%c=(a\%c\div b\%c)\%c$

上面这种除法运算是错误的!

如果要实现这种运算,就要把除法转化为乘法,假设 $b^{-1}$ 是 $b$ 关于 $c$ 的逆元。
$(a\div b)\%c$ 可以转化为 $(a\times b^{-1})\%c=(a\%c\times b^{-1}\%c)\%c$。

逆元求法

费马小定理

费马小定理:假设 $p$ 是一个质数,且 $gcd(a, p) = 1$,那么 $a^{p-1}≡1\ mod\ p$。
我们也可以的得到一个费马小定理的特例:假设 $a$ 是一个整数,且 $gcd(a, p) = 1$,那么 $a^{p-1}≡1\ mod\ p$。

根据费马小定理 $a^{p-1}≡1\ mod\ p$ ,可以发现 $a^{p-2}\times a≡1\ mod\ p$ 也成立。
是不是很像上面说到的逆元的形式:$Ax≡1\ mod\ p$, $x$ 是 $A$ 关于 $p$ 的逆元。
那根据费马小定理也可得知 $a^{p-2}$ 是 $a$ 关于 $p$ 的逆元。
所以求 $a$ 的逆元,就直接用快速幂求 $a^{p-2}$ 就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
LL power(LL a, int x) {
LL ans = 1;
while(x) {
if(x&1) ans = (ans * a) %mod;
a = (a * a) %mod;
x >>= 1;
}
return ans;
}

LL inv(LL a) {
return power(a, mod - 2);
}

扩展欧几里得

扩展欧几里得:$ax +by=gcd(a,b)$ 的解一定存在。
当我们要求 $a$ 关于 $p$ 的逆元时,若逆元存在,则 $gcd(a,p)=1$。假设逆元为 $x$,即: $ax ≡ 1\ mod\ p$。
我们可以展开一下变成 $ax = 1 + pk$,由于 $k$ 可正可负。
所以我们可以得到 $ax + pk=1$,其实就是 $ax + pk= gcd(a,p)$。
所以我们用扩展欧几里得求出一个最小的 $x$ 就是 $a$ 关于 $p$ 的一个逆元啦。


我们来试着解这个欧几里得吧!
现在已经有了 $ax + by=gcd(a,b)$ 了。我们想试着求出一个特解 $x$。

根据欧几里得算法我们可以知道$gcd(a,b)=gcd(b,a\%b)$。

而且我们可以看出 $bx+(a\%b)y=gcd(b,a\%b)$
由此我们可得:(由于两边的 $x$,$y$ 值不同,我们用 $x’$ 和 $y’$ 进行区分)

我们想要把式子化简一下,可以从 $a\%b$ 入手,即 $a\%b\ =\ a-\lfloor\frac{a}{b}\rfloor \times b$。
所以我们可以化简得到:
移项:

系数相等,所以我们可以解得

根据欧几里得算法,我们一直递归下去,总会到要一个最终位置的 $a\%b=0$ 。
所以式子变成了 $ax=gcd(a,b)$。此时我们取一个特解 $x=1$,$y=0$。然后往回推,就可以得到一开始的那个 $x$。
此时解出来的 $x$ 就是 $a$ 关于 $p$ 的一个逆元。

1
2
3
4
5
6
7
8
void exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1;y = 0;
} else {
exgcd(b, a%b, y, x);
y -= (a/b) * x;
}
}

递推求阶乘逆元。

我们经常会用到阶乘的逆元,我们可以考虑用费马小定理先求出最大那个阶乘的逆元,然后再往回推,直接看代码再解释。

1
2
3
4
5
6
7
8
9
10
void init() {
fact[0] = 1;
for (int i = 1; i < maxn; i++) {
fact[i] = fact[i - 1] * i %mod;
}
inv[maxn - 1] = power(fact[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) %mod;
}
}

我们可以假设把 $n!$ 的逆元表示为 $[n!]^{-1}$。
我们要求 $(n-1)!$ 的逆元,我们可以考虑给 $(n-1)!$ 乘上一个 $n$ 把他变为 $n!$。

因此 $n[n!]^{-1}$ 是 $(n-1)!$ 关于 $p$ 的一个逆元。