数论-逆元

[toc]

定义

若$a\times x\equiv 1\pmod b$且$a,b$互质,我们就称$x$为$a$的逆元,记作$a^{-1}$。
下面给出逆元的几种求法。

扩展欧几里得求逆元

扩展

欧几里得在这里
因为$a\times x\equiv 1\pmod b$,所以$a\times x=b\times y+1$,等价于$a\times x+b\times y=1$,这就是一个可以用欧几里得求解的线性方程了。
这里已经介绍出了如何利用原结论求出这个方程的解。
下面给代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void exgcd(int a,int b,int c,int &x,int &y)
{
int ret,tmp;
if(a==0)
{
x=0;
y=c/b;
return;
}
int tx,ty;
exgcd(b%a,a,c,tx,ty);
x=ty-(b/a)*tx;
y=tx;
return;
}

费马小定理求逆元

设$p$是一个素数,$a$是和$p$互质的整数,则有:$$a^{p-1}\equiv 1\pmod p$$
所以我们发现有:$a\times a^{p-2}\equiv 1\pmod p$,所以当$p$是素数时候,$a$的逆元就是$a^{p-2}$。
注意点:费马小定理在$p$是素数而且$a,p$互质的时候才可以使用。
变式:对任意整数$a$,有$a^p\equiv a\pmod p$,我们可以发现,对于这两个结论,我们有这样的条件:
在$a,p$互质的时候,两个结论是等价的;如果$a,p$不互质,那么只有后者成立。

证明

首先,$p-1$个整数$a,2a,3a,4a…,(p-1)a$中没有一个是$p$的倍数。(因为p是质数而且ap还互质)。
其次$a,2a,3a,4a…,(p-1)a$中没有两个模$p$同余的。
于是这些数再加上$ap$就构成了一个完系。所以$a,2a,3a,4a…,(p-1)a$在模$p$意义下是$1~p-1$的一种排列。
所以:$a\times 2a\times 3a\times …\times(p-1)a\equiv 1\times 2\times 3\times …\times (p-1)\pmod p $
化简:
$a^{p-1}\times (p-1)!\equiv (p-1)!\pmod p$
因为$p$是质数,所以$(p-1)!$和$p$互质。约分后$a^{p-1}\equiv \pmod p$
这个情况只有在$p$是素数而且$ap$互质才成立。一般地,若$p$是质数,则有:
$a^p\equiv a\pmod p$

代码

费马小定理使用的方法就很简单了,快速幂!

线性递推算法

声明:下面所有的运算都是在$\mod p$意义下进行的。
首先1的逆元是1。接下来我们表示逆元使用这个方法$a^{-1}$。
我们设$p=k\times i+r(r<i,1<i<p)。$如果把这个式子放在$\mod p$意义下,则会有$k\times i+r\equiv 0\pmod p$两边同乘以$(i^{-1}\times r^{-1})$就会有:
\begin{align}
k\times r^{-1}+i^{-1}&\equiv 0\pmod p\
i^{-1}&\equiv -k\times r^{-1}\pmod p\
i^{-1}&\equiv -[\frac pi]\times (p\mod i)^{-1}\
\end{align}
所以我们就得到了代码:

1
A[i]=-(p/i)\times A[p % i];

这个方法适用于求多个整数的逆元。

对数级算法求逆元

我们由线性算法可以得到,我们可以不停地使用上述的公式递归,显然可以证明$p\mod i<p/2$。
所以我们发现每次的问题规模都缩小了一半,所以时间复杂度$O(log_2p)$。
代码:

1
2
3
4
int ny(int i)
{
return i==1 ? 1 : (-ny(p%i)*p/i)%p;
}
文章目录
  1. 1. 定义
  2. 2. 扩展欧几里得求逆元
  3. 3. 费马小定理求逆元
    1. 3.1. 证明
    2. 3.2. 代码
  4. 4. 线性递推算法
  5. 5. 对数级算法求逆元