定义#

对于两个数 $a$ 和 $b$，$a,b\in \mathbb{Z}$，则如果存在整数 $c$，$d$，使得 $bc+d=a$，且保证 $0\leq \lvert{d}\rvert \lt b$，则称 $c$ 是 $a$ 除以 $b$ 的商，$d$ 是 $a$ 除以 $b$ 的余数，也被称为 $a$ 模 $b$ 的结果，记作 $a\bmod{b}=d$．

对于两个整数 $a$ 和 $b$，如果有整数 $p$，使得 $a\bmod{p} = b\bmod{p}$，则称 $a$ 和 $b$ 对模 $p$ 同余，记作 $a\equiv b\pmod p$，像这样的式子叫做同余方程．

对于两个整数 $a$ 和 $p$，如果 $a\equiv 0\pmod p$，则 $p$ 整除 $a$，记作 $p \mid a$ ．

性质#

同余的基本性质#

对于两个整数 $a,b$，如果有 $a\equiv b\pmod p$，则可得 $p \mid a - b$

证明：

由已知可得：

$$\left\{ \begin{aligned} & k_1p+n=a \\ & k_2p+n=b\end{aligned} \right.$$

其中，

$$n,k_1,k_2\in\mathbb{Z}$$

所以：

$$\begin{aligned} a-b &=k_1p+n-k_2p-n\\ &=k_1p-k_2p\\ &=p(k_1-k_2)\\ &\Rightarrow a-b\equiv 0\pmod p \\ &\Rightarrow p \mid a-b \end{aligned}$$

加法性质#

对于整数 $a,b,c,d,p$，如果有：

$$\left\{ \begin{aligned} & a\equiv b\pmod p \\ & c\equiv d\pmod p\end{aligned} \right.$$

则有：

$$(a+c) \equiv (b+d)\pmod p$$

证明：

由已知条件可得：

$$\left\{ \begin{aligned} & k_1p+n=a \\ & k_2p+n=b \\ & k_3p+m=c \\ & k_4p+m=d\end{aligned} \right.$$

其中，

$$n,m,k_1,k_2,k_3,k_4\in\mathbb{Z}$$

所以：

$$\begin{align*} (a+c)&=k_1p+n+k_3p+m\\&=(k_1+k_3)p+m+n\\(a+c)\bmod p &= m+n\end{align*}$$

同理：

$$(b+d)\bmod p=m+n$$

所以：$(a+c) \equiv (b+d)\pmod p$

加法性质的引申性质#

对于整数 $a,b,c,d,p$，如果有：

$$\left\{ \begin{aligned} & a\equiv b\pmod p \\ & c\equiv d\pmod p\end{aligned} \right.$$

则有：

$$a-c \equiv b-d\pmod p$$ $$a\times c \equiv b\times d\pmod p$$ $$a^c \equiv b^d\pmod p$$

移项和约分#

同余方程允许移项．

对于整数 $a,b,c,p$，如果有：

$$a\equiv b+c\pmod p$$

则有：

$$a-c \equiv b\pmod p$$

证明：

$$\begin{align*} a&\equiv b+c\pmod p\\ a-c&\equiv b+c-c\pmod p\\ a-c&\equiv b\pmod p \end{align*}$$

同余方程允许约分．

对于整数 $a,b,p$，如果有：

$$a\equiv b\pmod p$$

且 $c$ 是 $a, b, p$ 的公因数，则有：

$$\frac{a}{c} \equiv \frac{b}{c}\pmod {\frac{p}{c}}$$

证明：

由已知条件可得：

$$\left\{ \begin{aligned} & k_1p+n=a \\ & k_2p+n=b \end{aligned} \right.$$

其中，

$$n,k_1,k_2\in\mathbb{Z}$$

所以：

$$\begin{aligned} \frac{a}{c}\bmod \frac{p}{c}&=\frac{k_1p+n}{c}\bmod \frac{p}{c}\\ &=(k_1\frac{p}{c}+\frac{n}{c})\bmod \frac{p}{c}\\ &=\frac{n}{c} \end{aligned}$$

同理可证，

$$\frac{b}{c}\bmod \frac{p}{c}=\frac{n}{c}$$

所以：

$$\frac{a}{c} \equiv \frac{b}{c}\pmod {\frac{p}{c}}$$

逆元#

若 $ab\equiv 1\pmod p$，且 $a,b,p \in \mathbb{Z}$ ，则称 $a$ 和 $b$ 互为模 $p$ 下的逆元，$a$ 的逆元可以记作 $a^{-1}$．

特别的，1 的逆元总是 1

除法性质#

对于整数 $a,b,c$，如果有：

$$\begin{aligned} & ac\equiv bc\pmod p\end{aligned}$$

则有：

$$a \equiv b\pmod p$$

证明：

$$\begin{aligned} ac&\equiv bc\pmod p\\ ac\cdot c^{-1}&\equiv bc\cdot c^{-1} \pmod p\\ a &\equiv b\pmod p \end{aligned}$$

剩余类和完全剩余系#

对于正整数 $p$，全部整数可以分为 $p$ 个集合，令其为 $K_0,K_1,K_2,\cdots,K_{p-1}$，其中，整数 $n$ 和其所在的集合 $K_i$ 所满足的条件为：

$$n\equiv i\pmod p$$

则称 $K_0,K_1,K_2,\cdots,K_{p-1}$ 为模 $p$ 的剩余类．

对于一个集合 $s$，如果集合中有 $p$ 个元素，且每一个元素和其他元素都不在同一个模 $p$ 的剩余类中，则称这个集合 $s$ 是模 $p$ 的完全剩余系．模 $p$ 的完全剩余系有无数个．

费马小定理#

如果 $p$ 是一个质数，而整数 $a$ 和 $p$ 互质，则有：

$$a^{p-1}\equiv 1\pmod p$$

证明：

假定模 $p$ 的完全剩余系 $s=\{0, 1, 2, \cdots, p-1\}$，不妨将 $s$ 中的每一项都乘 $a\in\mathbb{Z}$，$a\neq 0$，得到一个新的集合 $s'=\{0,a,2a,\cdots,(p-1)a\}$．

我们现在将模 $p$ 为 0 的一项删去，即 $s$ 和 $s'$ 中的 $0$．

我们可以知道，在删去 $0$ 后，$s$ 的各项之积 $T$ 为：

$$\begin{aligned} T &=1\times 2\cdots \times(p-1)\\ &=(p-1)! \end{aligned}$$

$s'$ 的各项之积 $T'$ 为：

$$\begin{aligned} T'&=a\cdot 2a\cdots ({p-1})a\\ &=a^{p-1}(p-1)! \end{aligned}$$

可推得：

$$\begin{aligned} T \bmod p&=(p-1)!\bmod p\\ T'\bmod p&=(a\bmod p)(2a\bmod p)\cdots[(p-1)a\bmod p]\bmod p\\ &=k_1k_2k_3\cdots k_{p-1}\bmod p\\ k_i\in\mathbb{Z},&0\lt k_i\lt p \end{aligned}$$

又由于 $s'$ 是模 $p$ 的完全剩余系，所以每一个 $k_i$ 都是一个 $[1,p-1]$ 之间的值（注意，$k_i$ 的值不一定是 $i$），且两两互不相同．

所以，

$$\begin{aligned} T'\bmod p&=k_1k_2k_3\cdots k_{p-1}\bmod p\\ &=1\times 2\times\cdots\times (p-1)\bmod p\\ &=(p-1)!\bmod p\\ &=T\bmod p \end{aligned}$$

由此可得，$T'\equiv T\pmod p$

所以：

$$\begin{aligned} T'&\equiv T\pmod p\\ a^{p-1}(p-1)!&\equiv (p-1)!\pmod p \end{aligned}$$

令 $(p-1)!$ 的逆元为 $n$，所以：

$$\begin{aligned} a^{p-1}(p-1)!&\equiv (p-1)!\pmod p\\ a^{p-1}(p-1)!n&\equiv (p-1)!n\pmod p\\ a^{p-1}&\equiv 1\pmod p\\ \end{aligned}$$

得证．

利用费马小定理求逆元#

$$\begin{aligned} a^{p-1}&\equiv 1\pmod p\\ a\cdot a^{p-2}&\equiv 1\pmod p\\ \end{aligned}$$

所以，$a$ 的逆元是 $a^{p-2}$．在实战中，可以使用快速幂在 $O(\log n)$ 的时间复杂度之内解决．