同余

裴蜀定理

设 $a,b$ 是不全为 $0$ 的整数，则

• 对任意整数 $x,y$，成立 $\gcd (x,y)|ax+by$；
• 存在整数 $x,y$，成立 $\gcd (x,y)=ax+by$。

可推广到多个数。

逆定理：设 $a,b$ 是不全为 $0$ 的整数，若 $d>0$ 是 $a,b$ 的公因数，且存在 $x,y$ 使得 $ax+by=d$，则 $d=\gcd (a,b)$。可用来判断互质。

费马小定理

对于任意质数 $p$ 和整数 $a$，有 $a^p\equiv a\mathrm{mod}p$。证明可以通过拉格朗日定理得到。

欧拉定理

若 $\gcd (a,m)=1$，则 $a^{\phi (m)}\equiv 1\mathrm{mod}m$。

证明

设 $(x_1,\cdots ,x_{\phi (m)})$ 为整数模 $m$ 剩余系的一组代表元。则 $m\nmid (x_i-x_j)$，同理 $m\nmid a(x_i-x_j)$，所以 $(a{x}_1,\cdots ,a{x}_{\phi (m)})$ 也是整数模 $m$ 剩余系的一组代表元。

故 $a{x}_{1}a{x}_2\cdots a{x}_{\phi (m)}\equiv x_1{x}_2\cdots x_{\phi (m)}\mathrm{mod}m$。

扩展欧拉定理

$$a^b\equiv \{\begin{array}{ll}{a}^{b\mathrm{mod}\phi (m)},& \gcd (a,m)=1,\\ a^b,& \gcd (a,m)\ne 1,b<\phi (m),\\ a^{(b\mathrm{mod}\phi (m))+\phi (m)},& \gcd (a,m)\ne 1,b\ge \phi (m).\end{array}(\mathrm{mod}m)$$

Exgcd

问题：求 $ax+by=\gcd (a,b)$ 的一组可行解。

考虑递归过程：$\{\begin{array}{l}a{x}_1+b{y}_1=\gcd (a,b)\\ b{x}_2+(a\mathrm{mod}b)y_2=\gcd (b,a\mathrm{mod}b)\end{array}$，则一组解为 $\{\begin{array}{l}{x}_1=y_2\\ y_1=x_2-\lfloor \frac{a}{b}\rfloor y_2\end{array}$。

对于任意的不定方程 $ax+by=c$，根据裴蜀定理，有解的条件是 $\gcd (a,b)\mid c$。可以先用 Exgcd 求解，然后乘上倍数。

线性同余方程

问题：求解 $ax\equiv b\mathrm{mod}n$ 的所有解。

有解的条件是 $\gcd (a,n)\mid b$。

先用 Exgcd 求出 $a{x}_0+n{k}_0=\gcd (a,n)$，然后就有原方程的一组解 $a\frac{b}{\gcd (a,n)}{x}_0+n\frac{b}{\gcd (a,n)}{k}_0=b$。

任意解为 $x=\frac{b}{\gcd (a,n)}{x}_0+\frac{n}{\gcd (a,n)}k$。

最小正整数解可以用负数 $\mathrm{mod}$ 转正数的公式来算：$x=(x_0\mathrm{mod}t+t)\mathrm{mod}t$，其中 $t=\frac{n}{\gcd (a,n)}$。

中国剩余定理

用来解同余方程组 $\{\begin{array}{ll}x& \equiv a_1\mathrm{mod}{n}_1\\ x& \equiv a_2\mathrm{mod}{n}_2\\ & ⋮\\ x& \equiv a_k\mathrm{mod}{n}_k\end{array}$，其中 $n_i$ 两两互质。

过程：

1. $n:=\prod n_i$
2. 对于第 $i$ 个方程：
   1. $m_i:=\frac{n}{n_i}$
   2. 计算 $m_i^{-1}\mathrm{mod}{n}_i$
   3. $c_i:=m_i{m}_i^{-1}$，不取模
3. 模 $n$ 意义下唯一解为 $x={\sum }_i{a}_i{c}_i\mathrm{mod}n$。

可以用来解决模数不是质数的一些问题：先对模数进行质因数分解，分别关于这些质因子取模计算答案，然后用 CRT 合并。

扩展 CRT

用来解决模数不互质的情况。设两个方程是 $x\equiv a_1\mathrm{mod}{m}_1$ 和 $x\equiv a_2\mathrm{mod}{m}_2$，其中 $m_1$ 和 $m_2$ 不一定互质。转化为 $x=m_{1}p+a_1=m_{2}q+a_2$，则 $m_{1}p-m_{2}q=a_2-a_1$。

由裴蜀定理，当 $\gcd (m_1,m_2)\nmid (a_2-a_1)$ 时无解。否则通过 Exgcd 解出一组 $(p,q)$，则原方程组的解为 $x\equiv m_{1}p+a_1\mathrm{mod}\mathrm{lcm}(m_1,m_2)$。