組合數學/同餘

關於同餘的基本事實可以在任何一本數論書中找到。我們這裡只回顧一下。有關詳細資訊，請參閱任何關於數論的標準教材。

對於任何整數 $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 同餘。

該定理是費馬小定理的推廣。