形式陈述

给定正整数 $n$$n$，若 $n\mid(a-b)$$n\mid (a-b)$，称整数 $a,b$$a,b$ 模 $n$$n$ 同余，记

$$ a\equiv b\pmod n. $$$$a\equiv b(\mathrm{mod}n).$$

这是 $\mathbb Z$$\mathbb{Z}$ 上的等价关系，其等价类构成商环 $\mathbb Z/n\mathbb Z$$\mathbb{Z}/n\mathbb{Z}$。同余与加法、减法、乘法相容：若 $a\equiv b$$a\equiv b$、$c\equiv d\pmod n$$c\equiv d(\mathrm{mod}n)$，则

$$ a\pm c\equiv b\pm d, \qquad ac\equiv bd\pmod n. $$$$a\pm c\equiv b\pm d,ac\equiv bd(\mathrm{mod}n).$$

消去因子需条件：由 $ac\equiv bc\pmod n$$ac\equiv bc(\mathrm{mod}n)$ 只能推出

$$ a\equiv b\pmod{n/\gcd(c,n)}; $$$$a\equiv b(\mathrm{mod}n/gcd(c,n));$$

若 $\gcd(c,n)=1$$gcd(c,n)=1$，才可模 $n$$n$ 消去 $c$$c$。

直觉

模同余把相差 $n$$n$ 的整数视为同一状态，把无限整数轴卷成 $n$$n$ 个剩余类；环运算因差仍为 $n$$n$ 的倍数而良定义。

例子与边界

$17\equiv2\pmod5$$17\equiv 2(\mathrm{mod}5)$。模 $6$$6$ 有 $2\cdot1\equiv2\cdot4\pmod6$$2\cdot 1\equiv 2\cdot 4(\mathrm{mod}6)$，却 $1\not\equiv4\pmod6$$1\not\equiv 4(\mathrm{mod}6)$，展示不可任意除以 $2$$2$。模数按标准约定取正；模 $1$$1$ 时所有整数同余。记号 $a\bmod n$$amodn$ 有时指余数值，有时指剩余类，二者需区分。负数也可归到 $0,\dots,n-1$$0,\dots ,n-1$ 的标准代表，但代表选择不影响类。由 $a^2\equiv b^2$$a^2\equiv b^2$ 不能一般推出 $a\equiv\pm b$$a\equiv \pm b$，合数模下尤其会有更多平方根。

推论与应用

同余是有限环、模逆、CRT、密码学和周期性算法的基础。

参考资料

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer, 1990，Ch. 2, congruences and residue classes。
• Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991，Ch. 2, congruences and cancellation。