组合数学/同余

关于同余的基本事实可以在任何一本数论书中找到。我们这里只回顾一下。有关详细信息，请参阅任何关于数论的标准教材。

对于任何整数 $n\geq 2$，我们说两个整数 a 和 b 在模 n 下同余或 $a\equiv b{\pmod {n}}$，如果 n 整除差值 a-b。

例如，5 和 11 在模 3 下同余

11≡5(mod 3) 因为 11 − 5 等于 6，而 6 可以被 3 整除。或者，同样地，这两个数字在被 3 除时有相同的余数

11 = 3×3 + 2

5 = 1×3 + 2

如果 a1 ≡ b1 (mod n) 且 a2 ≡ b2 (mod n)，那么 a1 + a2 ≡ b1 + b2 (mod n) 且 a1a2 ≡ b1b2 (mod n)。这将同余 (mod n) 转化为所有整数环上的等价关系。整数 a 的等价类，记为 ${\overline {a}}_{n}$，是集合 $\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}$。这个集合，由所有模 n 同余于 a 的整数组成，称为 a 模 n 的同余类或剩余类。另一种表示这个同余类的记法，需要在上下文中知道模，是 $\displaystyle [a]$。

模 n 的同余类集合记为 $\mathbb {Z} /n\mathbb {Z}$（或者，换句话说，$\mathbb {Z} /n$ 或 $\mathbb {Z} _{n}$）并由以下定义

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.$

$\mathbb {Z} /n\mathbb {Z}$ 有 n 个元素，可以写成

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.$

我们可以根据以下规则定义 $\mathbb {Z} /n\mathbb {Z}$ 上的加法、减法和乘法。

• ${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {a+b}}_{n}$
• ${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {a-b}}_{n}$
• ${\overline {a}}_{n}{\overline {b}}_{n}={\overline {ab}}_{n}.$

使用之前给出的性质可以验证这是一个正确的定义。

这样，$\mathbb {Z} /n\mathbb {Z}$ 成为一个交换环。事实上， $\mathbb {Z} /n\mathbb {Z}$ 是一个域（它是交换环的一种特殊类型），当且仅当 n 是素数。

费马小定理（不要与费马大定理混淆）指出，如果p是素数，那么对于任何整数a，$a^{p}-a$ 可以被p整除。这可以表示如下

$a^{p}\equiv a{\pmod {p}}\,\!$

正整数n的欧拉函数 $\varphi (n)$ 定义为小于等于n且与n互质的正整数的数量。例如，$\varphi (9)=6$，因为六个数字1、2、4、5、7和8与9互质。

欧拉定理（也称为费马-欧拉定理或欧拉托里安定理）指出，如果n是正整数，a与n互质，那么

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

其中 φ(n) 是欧拉函数，"... ≡ ... (mod n)" 表示模 n 同余。

该定理是费马小定理的推广。