裴蜀定理

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

证明：

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

若 $b>0$，则 $gcd(a,b)=gcd(b,amodb)$。假设存在一对整数 $x,y$ 满足 $b\ast x+(amodb)\ast y=gcd(b,amodb)$，因为 $bx+(amodb)y=bx+(a-b\lfloor a/b\rfloor )y=ay+b(x-\lfloor a/b\rfloor y)$，所以令 $x^{\prime }=y,y^{\prime }=x-\lfloor a/b\rfloor \ast y$，就得到了 $a{x}^{\prime }+b{y}^{\prime }=gcd(a,b)$。

由数学归纳法可知，裴蜀定理成立。

扩展欧几里得算法

由裴蜀定理的证明过程可得扩展欧几里得算法：

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - y * (a / b);
    return d;
}

扩展欧几里得算法可求出 $ax+by=gcd(a,b)$ 的一组特解 $(x^{\prime },y^{\prime })$。，那么由原式可知通解的形式如下：

$$\begin{gathered} x=x^{\prime }+\frac{b}{gcd(a,b)}\ast t \\ y=y^{\prime }-\frac{a}{gcd(a,b)}\ast t \end{gathered}$$

其中 $t$ 为任意整数。上式可理解为特解 $x^{\prime }$ 加上一个数，而 $y^{\prime }$ 减去一个数，得到的结果是不变的。

明确了通解的形式，那么如何求 $x$ 的最小整数解呢？其实就是让 $x^{\prime }$ 每次移动 $b/gcd(a,b)$ 单位，直到到达临界点。该操作可以使用模运算快速完成。设 $d=b/gcd(a,b)$，则 $x$ 的最小整数解为 $(x^{\prime }\mathrm{\%}d+d)\mathrm{\%}d$。

求解不定方程 $ax+by=c$

扩展欧几里得算法求解不定方程的过程如下：

1. 判断方程 $ax+by=c$ 是否有整数解。有解的充要条件是 $gcd(a,b)\mid c$。
2. 使用扩展欧几里得算法求 $ax+by=gcd(a,b)$ 的一组特解 $(x^{\prime },y^{\prime })$。
3. 在等式 $a{x}^{\prime }+b{y}^{\prime }=gcd(a,b)$ 的两边同时乘以 $\frac{c}{gcd(a,b)}$，得到 $a{x}^{\prime }\frac{c}{gcd(a,b)}+b{y}^{\prime }\frac{c}{gcd(a,b)}=c$。
4. 对照 $ax+by=c$ 得到它的一个解为：$$\begin{gathered} x_0=x^{\prime }\frac{c}{gcd(a,b)} \\ {y}_0=y^{\prime }\frac{c}{gcd(a,b)} \end{gathered}$$
5. 设 $d=gcd(a,b)$，则 $ax+by=c$ 的通解可以表示为：$$\begin{gathered} x=x_0+\frac{b}{d}\ast t \\ y=y_0-\frac{a}{d}\ast t \end{gathered}$$其中 $t$ 为任意整数。

求解线性同余方程

给定整数 $a,b,m$ 求解线性同余方程 $ax\equiv b(\mathrm{mod}m)$ 的整数解，或报告无解。

$ax\equiv b(\mathrm{mod}m)$ 等价于 $m\mid (ax-b)$，即 $ax-my=b$，又因为 $y$ 可以是任意整数，所以原方程等价于 $ax+my=b$，此时只需要求不定方程的解即可。类似地，当 $gcd(a,m)\mid b$ 时，方程 $ax+my=b$ 有整数解，且恰有 $gcd(a,m)$ 个模 $m$ 不同余的解，分别是 $x_i=x_0+i\ast (m/gcd(a,m))(0\le i\le gcd(a,m)-1)$。

求逆元

若整数 $b$ 和 $m$ 互质，则存在整数 $x$ 满足 $bx(\mathrm{mod}m)$，称 $x$ 为 $b$ 的模 $m$ 乘法逆元，记为 $b^{-1}(\mathrm{mod}m)$。也就是说在模意义下除以 $b$ 就等于乘上 $b$ 的逆元。因此，求 $b$ 的逆元，等价于求同余方程 $bx\equiv 1(\mathrm{mod}m)$ 的整数解。

int inv(int b, int m) {
    int x, y;
    exgcd(b, m, x, y);
    return (x % m + m) % m;
}

上述代码求解逆元的时间复杂度为 $O(\log n)$。

费马小定理求逆元

当 $m$ 是质数时，将 $m$ 记作 $p$，若 $b<p$，根据费马小定理 $b^{p-1}\equiv 1(\mathrm{mod}p)$，则 $b{b}^{p-2}\equiv 1(\mathrm{mod}p)$，因此模 $p$ 意义下 $b$ 的逆元为 $b^{p-2}$。

这里就可以使用快速幂求解 $b^{p-2}$，时间复杂度为 $O(\log p)$。

int inv(int b, int p) {
    return qmi(b, p - 2, p)
}

线性递推求逆元

当需要求 $1\sim n$ 每一个数的逆元时，可以采用线性递推的方法，时间复杂度为 $O(n)$。

线性递推求解逆元的思路如下：

使用 inv[i] 表示 $i$ 的逆元，当 $i<p$ （$p$ 为质数）时，有递推式：inv[i] = (p - p / i) * inv[p % i] % p。

证明：

当 $i<p$ 时，有 $p=k\ast i+r$，其中 $k=p/i,r=p\mathrm{\%}i$，有：

$$k\ast i+r\equiv 0(\mathrm{mod}p)$$

两边同时乘上 $i$ 的逆元 $i^{-1}$，得：

$$\begin{gathered} k\ast i\ast i^{-1}+r\ast i^{-1}\equiv 0(\mathrm{mod}p) \\ k+r\ast i^{-1}\equiv 0(\mathrm{mod}p) \end{gathered}$$

移项得：

$$r\ast i^{-1}\equiv -k(\mathrm{mod}p)$$

两边同时乘上 $r$ 的逆元 $r^{-1}$，得：

$$\begin{gathered} r^{-1}\ast i^{-1}\ast r\equiv -k\ast r^{-1}(\mathrm{mod}p) \\ {i}^{-1}\equiv -k\ast r^{-1}(\mathrm{mod}p) \end{gathered}$$

代入 $k=p/i,r=p\mathrm{\%}i$，得：

$$\begin{gathered} i^{-1}\equiv -(\frac{p}{i})\ast (p\mathrm{\%}i{)}^{-1}(\mathrm{mod}p) \\ {i}^{-1}\equiv (p-\frac{p}{i})\ast (p\mathrm{\%}i{)}^{-1}(\mathrm{mod}p) \end{gathered}$$

具体代码如下：

int n, p, inv[N];

void init_inv(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
}

中国剩余定理

《孙子算经》中记载了这样一个问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？使用现代语言描述即是求满足以下条件的整数：除以 $3$ 余 $2$，除以 $5$ 余 $3$，除以 $7$ 余 $2$。

即：

$$\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}5)\\ x\equiv 2(\mathrm{mod}7)\end{array}$$

以上即是线性同余方程组。而《孙子算经》中记载的中国剩余定理就是解决形如以下形式的一次线性同余方程组的算法。

$$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{m}_1)\\ x\equiv a_2(\mathrm{mod}{m}_2)\\ ⋮\\ x\equiv a_n(\mathrm{mod}{m}_n)\end{array}$$

其中 $m_1,m_2,\cdots ,m_n$ 两两互质，则对于任意的整数 $a_1,a_2,\cdots ,a_n$，上述方程有解。

求解过程如下：

1. 计算所有模数的积 $M=m_1\ast m_2\ast \cdots \ast m_n$。
2. 对于第 $i$ 个方程：
   1. 计算 $b_i=\frac{M}{m_i}$。
   2. 计算 $b_i$ 在模 $m_i$ 意义下的逆元 $b_i^{-1}$。
   3. 计算 $c_i=b_i\ast b_i^{-1}$，注意不要取模。
3. 方程组在模 $M$ 意义下的唯一解为：$x=\sum _{i=1}^k{a}_i{c}_i(\mathrm{mod}M)$。

int CRT(int k, int a[], int r[]) {
    int M = 1, ans = 0;
    for (int i = 1; i <= k; i++) M = M * r[i];
    for (int i = 1; i <= k; i++) {
        int b = M / r[i], inv_b, y;
        exgcd(b, r[i], inv_b, y);
        ans = (ans + a[i] * b * inv_b % M) % M;
    }
    return (ans % M + M) % M;
}