整除

若 $a / b (b \ne 0)$ 为整数，则称 $b$ 整除 $a$ ，记作 $b \mid a$ 。若 $a / b$ 和 $c / b$ 的余数相等，则称 $a, c$ 模 $b$ 同余。

同余

关于同余，有以下命题等价：

$a$ 和 $b$ 是模 $d$ 同余的。
存在某个整数 $n$ ，使 $a = b + nd$ 。
$d$ 整除 $a - b$ 。

由此可以轻易推出以下性质：

同余的基本性质

\[a \equiv b \pmod p \text{且} c \equiv d \pmod p \Rightarrow a \pm c \equiv b \pm d \]
\[a \equiv b \pmod p \Rightarrow ak \equiv bk \pmod {pk} \]
\[k\mid p \text{且} a \equiv b \pmod p \Rightarrow a \equiv b \pmod k \]
\[\text{有逆元时两侧可同除} \]

模运算基本性质

\[(a + b) \bmod p = ((a \bmod p) + (b \bmod p)) \bmod p \]
\[ab \bmod p = (a \bmod p)(b \bmod p) \bmod p \]
\[a \bmod kb \bmod b = a \bmod b \]

欧几里得辗转相除法(gcd)

给定整数 $a, b$ ，将它们的最大公因数记作 $\gcd(a, b)$ ，欧几里得辗转相除法便是用来求 $\gcd(a, b)$ 的，因而简称 $\gcd$ 。
记 $a, b$ 的公因数集合为 $T$ ，$b , a \bmod b$ 的公因数集合为 $T'$ ，有 $T = T'$ 。证明：
设 $u \subseteq T$ ，$a = xu, b = yu$ ，$$a \bmod b = a - b \left \lfloor a / b \right \rfloor = xu - yu(\left \lfloor a / b \right \rfloor) = u[x - y(\left \lfloor a / b \right \rfloor)]$$ ，所以 $u \mid a \bmod b$ 。因而 $T \subseteq T'$ 。
同样的，记 $v \subseteq T'$ ，$b = nv, a \bmod b = mv$ ，$$a = a \bmod b + b \left \lfloor a / b \right \rfloor = mv + nv(\left \lfloor a / b \right \rfloor) = v[m + n\left \lfloor a / b \right \rfloor]$$ ，所以 $v \mid a$ 。因而 $T' \subseteq T$。

综上， $\gcd(a, b) = \gcd(b, a \bmod b)$ ，因而可以直接递归求解。时间复杂度为 $\log(n)$ 。

边界：当 $b = 0$ 时，$\gcd(a, b) = a$ 。

code:

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

扩展欧几里得(exgcd)

由欧几里得辗转相除法，我们可以运用这个算法在求最大公因数的同时求出满足 $$ax + by = \gcd(a, b)$$ 的正整数解 $x, y$ 。

对于边界条件 $b = 0$ ， $x = 1, y = 0$ 就是一组合法解（当然，此处 $y$ 可以取任意数）。那么，设 $a' = b, b' = a \bmod b$ ，且我们已经求出 $x_0, y_0$ 满足 $a'x_0 + b'y_0 = \gcd(a', b')$ ，于是：

\[\begin{aligned} \gcd(a, b) &= \gcd(a', b') \\ &= a'x_0 + b'y_0 \\ &= bx_0 + (a\bmod b)y_0 \\ &= bx_0 + (a - b \left \lfloor a / b \right \rfloor)y_0 \\ &= ay_0 + b(x_0 - \left \lfloor a / b \right \rfloor y_0) \end{aligned} \]

因此，满足 $ax + by = \gcd(a, b)$ 的 $x = y_0, y = x_0 - \left \lfloor a / b \right \rfloor y_0$ 。

code:

int exgcd(int a, int b, int &x, int &y){
    if(!b){
        x = 1, y = 0;
        return a;
    }
    int a1 = exgcd(b, a % b, x, y);
    int x1 = y, y1 = x - a / b * y;
    x = x1, y = y1;
    return a1;
}

乘法逆元

对于一个数 $a$ ，若 $ab = 1$ ，那么我们称 $a$ 的逆元为 $b$ ，记作 $a^{-1}$ 。在同余中，则是若 $ab \equiv 1$ , 则 $b$ 为 $a$ 的逆元。通常，我们通过找到 $a$ 的逆元来避免除法。给定 $a$ 和 $b$ ，我们需要求出 $x$ 满足 $ax \equiv 1 \pmod b$ 。

逆元唯一性定理：逆元若存在，则总是唯一的。
反证法。设有 $x \not \equiv y$ 使得 $ax \equiv ay \equiv 1$ ，则有 $axy \equiv ax(y) \equiv y$ ,且 $axy \equiv ay(x) \equiv x$ , 则 $x \equiv y$ ，矛盾。
逆元存在性定理：在模 $m$ 下，当且仅当 $a \bot m$ 时，$a$ 的逆元存在。后续补充证明。

事实上， $ax \equiv 1 \pmod b$ 等价于 $ax + by = \gcd(a, b)$ 。由逆元存在性定理，$a \bot b$ 时， $ax + by = 1$ 。所以 $ax = 1 - by$ ， $ax \equiv 1$ 。而若 $ax \equiv 1 \pmod b$ ，则 $ax - 1 \equiv 0 \pmod b$ ，所以令 $y = \frac{ax - 1}{b}$ , 就有 $ax + by = 1$ 。因此这两者等价。我们就可以直接使用exgcd求出 $a$ 在模 $b$ 下的乘法逆元。不过有一个需要注意的是，使用exgcd求出来的逆元可能是负数，输出 (x % b + b) % b 就好啦！

裴蜀定理

不定方程 $ax + by = c$ 有整数解 $x, y$ 的充要条件是 $\gcd(a, b) \mid c$ 。
证明：
当 $\gcd(a, b) \mid c$ 时，我们可以先用exgcd求出$ax +by = \gcd(a, b)$ 的解，然后同时乘以 $\ c / gcd(a, b)$ 即可得出解。
当 $\gcd(a, b) \not \mid c$ 时，在该方程两边同时除以 $\gcd(a, b)$ ，发现方程左边为整数，右边为分数，则必定无解。

由此，我们就可以运用裴蜀定理直接证明逆元存在性定理了。