同余
tóng yú
如果两个整数除以 n 的余数相同,它们就模 n 同余,记作 a ≡ b (mod n)。
Formula
a \equiv b \pmod{n} \text{ iff } n \mid (a - b)
Definition
如果两个数除以 $n$ 时余数相同，那么它们模 $n$ 同余；符号 $\equiv$ 表示"同余"，$\pmod{n}$ 说明模数是多少。严格地说，若 $n \mid (a - b)$，则 $a \equiv b \pmod{n}$；同余是一种等价关系（自反、对称、传递），并且在加法和乘法下保持不变，所以 $a \equiv b$ 且 $c \equiv d \pmod{n}$ 蕴含 $a+c \equiv b+d$ 且 $ac \equiv bd \pmod{n}$。模 $n$ 同余把 $\mathbb{Z}$ 划分成 $n$ 个剩余类，构成商环 $\mathbb{Z}/n\mathbb{Z}$；中国剩余定理为一组模两两互素的同余方程组，在模 $n_1 \times \ldots \times n_k$ 下给出唯一解，欧拉定理指出当 $\gcd(a,n) = 1$ 时，$a^{\phi(n)} \equiv 1 \pmod{n}$。
Example
$17 \equiv 2 \pmod{5}$，因为两者除以 $5$ 的余数都是 $2$，而且确实 $17 - 2 = 15$ 能被 $5$ 整除。求解 $3x \equiv 6 \pmod{9}$：用 $\gcd(3,9)=3$（它整除 $6$）去除，得到 $x \equiv 2 \pmod{3}$，解为 $2, 5, 8, \ldots$；线性同余方程 $ax \equiv b \pmod{n}$ 有解当且仅当 $\gcd(a,n) \mid b$。费马小定理让你能高效计算 $2^{100} \bmod 7$：由于 $2^6 \equiv 1 \pmod 7$，$2^{100} = (2^6)^{16} \times 2^4 \equiv 16 \equiv 2 \pmod{7}$，用到了通过重复平方的模幂运算。
Key Insight
同余把数分成若干"家族"：所有模 12 同余的数在"钟表上显示相同的时间"，而当线性同余方程确有解时，模 $n$ 下恰有 $\gcd(a,n)$ 个解。模素数幂的模运算给出了 p-进整数 $\mathbb{Z}_p$，这是 $\mathbb{Z}$ 的一种完备化方式，类似于 $\mathbb{R}$ 作为 $\mathbb{Q}$ 的完备化，p-进分析在数论中是与实分析平行的一门丰富理论。