同余

同余把"两个整数之差被模整除"化为一种代数关系，是解数论问题的主要工具。

定义

设 $m$ 为正整数。若 $m\mid (a-b)$，则称 $a$ 与 $b$ 模 $m$ 同余，记作

$$a \equiv b \pmod m$$

否则称 $a$ 与 $b$ 模 $m$ 不同余，记作 $a \not\equiv b \pmod m$。

性质

模 $m$ 同余是整数集上的等价关系：自反（$a\equiv a\pmod m$）、对称、传递。

同余保持通常的算术运算：若 $a\equiv b,\ c\equiv d \pmod m$，则

• $a\pm c \equiv b\pm d \pmod m$
• $ac \equiv bd \pmod m$
• $a^k \equiv b^k \pmod m$（$k$ 为正整数）

约去公因子：$ac \equiv bc \pmod m \iff a \equiv b \pmod{\dfrac{m}{\gcd(c,m)}}$。特别地，当 $\gcd(c,m) = 1$ 时可直接约去 $c$。

剩余类与剩余系

模 $m$ 的同余类 $[a] = \{a + km : k\in\mathbb{Z}\}$ 称为剩余类。从每个剩余类中取一个代表元，得模 $m$ 的完全剩余系，如 $\{0,1,\dots,m-1\}$。由与 $m$ 互素的剩余类组成的代表元组称为简化剩余系，其元素个数为 $\varphi(m)$（见欧拉函数）。

示例

• $17 \equiv 2 \pmod 5$，且 $17 \equiv -3 \pmod 5$（同一剩余类）
• $7\cdot 13 = 91 \equiv 1 \pmod 6$，因为 $7\equiv 1$ 且 $13\equiv 1 \pmod 6$
• 解 $6x \equiv 12 \pmod{15}$：约去公因子 $3$ 得 $2x \equiv 4 \pmod 5$，即 $x \equiv 2 \pmod 5$