扩展欧几里得算法与乘法逆元

xishanmeigao · 2022-07-14 18:47:04 · 个人记录

Part 1：前置知识

• 欧几里得算法

  \forall a,b \in \mathbb{N},\gcd(a,b)=\gcd(b,a \bmod b)

• \mathrm{Bézout} 定理

  对于任意整数 a,b，存在一对整数 x,y，满足 ax+by=\gcd(a,b)

  证明：

  在欧几里得算法的最后一步，即 b=0 时，显然有一对整数 x=1,y=0，使得 a*1+0*0=\gcd(a,0)

  若 b>0，则 \gcd(a,b)=\gcd(b,a \bmod b)

  假设存在一对正整数 x,y，满足 bx_1+(a \bmod b)y_1=\gcd(b,a \bmod b)

  则有 ax+by=bx_1+(a \bmod b)y_1

  \therefore ax+by=bx_1+(a-\left\lfloor\\a/b\right\rfloor*b)y_1 \therefore ax+by=bx_1+ay_1-(\left\lfloor\\a/b\right\rfloor*b)y_1 \therefore ax+by=ay_1+b(x_1-\left\lfloor\\a/b\right\rfloor*y_1) \therefore x=y_1,y=x_1-\left\lfloor\\a/b\right\rfloor*y_1

  对欧几里得算法的递归过程应用数学归纳法，可知 Bézout 定理 成立

  利用 \mathrm{Bézout} 定理，我们就可以使用 扩展欧几里得算法 来求出整数 x,y 的一组特解

Part 2：扩展欧几里得算法

1、求 ax+by=\gcd(a,b) 的一组特解

• 代码

#define LL long long
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;  y=0;  
        return a;
    }

    LL d=exgcd(b,a%b,x,y);
    LL tmp=x;
    x=y;  y=tmp-(a/b)*y;

    return d;
}

2.求 ax+by=\gcd(a,b) 的通解

• 已知 x_0,y_0 是一组特解，d=\gcd(a,b)（下面的 d 含义相同）

• 那么方程通解为

  x=x_0+k\dfrac{b}{d}, \qquad y=y_0-k\dfrac{a}{d}\quad(k\in \mathbb{Z})

  证明： 设 x,y 是除 x_0,y_0 之外的一组解

  则可得：\begin{cases}ax_0+by_0=d&(1)\\ax+by=d&(2)\end{cases}

  (2)-(1)$ 得：$a(x-x_0)=b(y_0-y)=\operatorname{lcm}(a,b)*k

  对 a(x-x_0)=\operatorname{lcm}(a,b)*k 进行分析：

  a(x-x_0)=\dfrac{ab}{d}*k \therefore x-x_0=\dfrac{b}{d}*k \therefore x=x_0+k\dfrac{b}{d}

  对 b(y_0-y)=\operatorname{lcm}(a,b)*k 分析，同理可得：y=y_0-k\dfrac{a}{d}

3.求 ax+by=c 的解

• 对于一般的方程 ax+by=c，它有解当且仅当 d\mid c

• 通过先前的扩欧，我们可以求出方程 ax+by=d) 的一组特解 x_0,y_0，然后令 x_0,y_0 同时乘上 c/d，就得到了 ax+by=c 的一组特解：(c/d)x_0,(c/d)y_0

• 由于 c 是 d 的倍数，所以类比求 ax+by=\gcd(a,b) 的通解的过程，我们可以将ax+by=c 的通解表示为：

  x=\dfrac{c}{d}x_0+k\dfrac{b}{d}, \qquad y=\dfrac{c}{d}y_0-k\dfrac{a}{d}\quad(k\in \Z)

Part 3：乘法逆元

1. 定义

• 若整数 a,m 互质，且 ax \equiv 1 \pmod m，那么就称 x 为 a 的模 m 乘法逆元。（记为 a^{-1}）

2.扩展欧几里得算法求逆元

• 将 ax \equiv 1 \pmod m 变形可得：ax-my=1 \ (m\in\mathbb{Z})

• 使用扩欧可轻松求出 x 的一个特解 x_0

• 若要求最小最小正整数解，则令 x=(x_0 \bmod m+m)\bmod m

• 代码

void exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;  y=0;
        return;
    }

    exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;  y=tmp-(a/b)*y;
    return;
}

int main()
{
    scanf("%d%d",&n,&m); //n为逆元表达式中的a

    int x=0,y=0;
    exgcd(n,m,x,y);
    x=(x%m+m)%m;

    printf("%d\n",x);

    return 0;
}

3.费马小定理求逆元

• 前提条件：当 m 为质数时才可使用

• 前置知识：费马小定理

  若 p 是质数，a 是正整数，且 a 不是 p 的倍数，则 a^{p-1} \equiv 1 \pmod p

• 已知\begin{cases}ax \equiv 1 \pmod m&(1) \\ a^{m-1} \equiv 1 \pmod m&(2)\end{cases}，那么由 (1)(2)可推出 ax \equiv a^{m-1} \pmod m，所以 x=a^{m-2}

• 一般情况下，我们可以使用快速幂来求出 a^{m-2}

4.线性递推求逆元

• 当题目需要我们求出一串数字 \bmod m 的逆元时，我们会采用这种方式

• 我们记 x 的逆元为 inv[x]，已知 1*1 \equiv 1 \pmod m，所以 inv[1]=1

• 设 m=k*x+r \quad (1 \leqslant r <x<m)，也就是说 k 是 m/x 的商，r 是余数。那么就有：

  k*x+r \equiv 0 \pmod m

  乘上 inv[x]*inv[r]，就有：

  k*inv[r]+inv[x] \equiv 0 \pmod m inv[x] \equiv -k*inv[r] \pmod m inv[x] \equiv -\left\lfloor\\\dfrac{m}{x}\right\rfloor *inv[m \bmod x] \pmod m

• 这样，我们就可以线性地递推出乘法逆元。但值得注意的是，一般题目中都要保证求出的逆元是正数，所以我们会在递推时往递推式中加一个 m*inv[m \bmod x]

• 代码

  inv[1]=1;
  for(int i=2; i<=n; i++)
      inv[i]=(long long)(m-m/i)*inv[m%i]%m;