GCD、EXGCD

GCD

$gcd(a,b)=gcd(b,a\mathrm{\%}b)$

证明:

$$\begin{gathered} \mathrm{设}a=bq+r=bq+a\mathrm{\%}b \\ a\mathrm{\%}b=a-bq \\ \mathrm{设}d=gcd(a,b),\mathrm{则} \\ d|a,d|b\to d|a\mathrm{\%}b \\ \mathrm{即}d=(b,a\mathrm{\%}b) \end{gathered}$$

得证

代码

int gcd(a,b) {
  if(!b)return a;
  return (b,a%b);
}

EXGCD

原理

裴蜀定理$ax+by=gcd(a,b)$

以及$gcd(a,b)=gcd(b,a\mathrm{\%}b)$

带入有$a{x}_1+b{y}_1=b{x}_2+a\mathrm{\%}b{y}_2=b{x}_2+(a-bq)y_2$

对比系数有$x_1=y_2,y_2=x_2-\frac{a}{b}{y}_2$

注意到 ax + 0y=gcd(a,0)=a 得x=1,y=0

void exgcd(a,b,int& x,int& y){
  if(!b){
    x=1,y=0;
    return;
  }
  exgcd(b,a%b,y,x); // 求解 gcd(b,a%b)的系数y,x
  // x=y_2 已经自动赋值了
  y = y - a/b *x; // x_2 - a/b y_2
}

若$gcd(a,b)=1,b\mathrm{为}\mathrm{质}\mathrm{数},\mathrm{则}x=a^{-1}(modp)$

费马小定理

$a^{p-1}=1(modp)$

即$a{a}^{p-2}=1(modp)$

得$a^{-1}=a^{p-2}$

inv[1]=1;
for(i in 1... ) {
  inv[i]=(p-p/i)*inv[p%i] % p;
}

递推办法

$inv(i)=(p-p/i)inv(p\mathrm{\%}i)\mathrm{\%}p$

$inv(1)=1$

数学推导

我们需要证明 $inv(i)=(p-p/i)\cdot inv(p\mathrm{\%}i)\mathrm{\%}p$。

设 $inv(i)$ 是 $i$ 在模 $p$ 意义下的逆元，即 $i\cdot inv(i)\equiv 1(\mathrm{mod}p)$。

根据模运算的性质，有：

$$i\cdot inv(i)\equiv 1(\mathrm{mod}p)$$

我们可以将 $i$ 表示为 $p$ 和 $p\mathrm{\%}i$ 的线性组合：

$$i=p-(p\mathrm{\%}i)\cdot \lfloor \frac{p}{i}\rfloor$$

设 $inv(p\mathrm{\%}i)$ 是 $p\mathrm{\%}i$ 在模 $p$ 意义下的逆元，即：

$$(p\mathrm{\%}i)\cdot inv(p\mathrm{\%}i)\equiv 1(\mathrm{mod}p)$$

将 $i$ 的表达式代入 $i\cdot inv(i)\equiv 1(\mathrm{mod}p)$：

$$(p-(p\mathrm{\%}i)\cdot \lfloor \frac{p}{i}\rfloor )\cdot inv(i)\equiv 1(\mathrm{mod}p)$$

展开并整理：

$$p\cdot inv(i)-(p\mathrm{\%}i)\cdot \lfloor \frac{p}{i}\rfloor \cdot inv(i)\equiv 1(\mathrm{mod}p)$$

由于 $p\cdot inv(i)\equiv 0(\mathrm{mod}p)$，因此：

$$-(p\mathrm{\%}i)\cdot \lfloor \frac{p}{i}\rfloor \cdot inv(i)\equiv 1(\mathrm{mod}p)$$

两边同时乘以 $-1$：

$$(p\mathrm{\%}i)\cdot \lfloor \frac{p}{i}\rfloor \cdot inv(i)\equiv -1(\mathrm{mod}p)$$

将 $inv(p\mathrm{\%}i)$ 代入上式：

$$(p\mathrm{\%}i)\cdot inv(p\mathrm{\%}i)\equiv 1(\mathrm{mod}p)$$

因此：

$$\lfloor \frac{p}{i}\rfloor \cdot inv(i)\equiv inv(p\mathrm{\%}i)(\mathrm{mod}p)$$

所以：

$$inv(i)\equiv (p-p/i)\cdot inv(p\mathrm{\%}i)(\mathrm{mod}p)$$

即：

$$inv(i)=(p-p/i)\cdot inv(p\mathrm{\%}i)\mathrm{\%}p$$

得证。