剰余類
任意の整数を 7 で割ると、余りは 0, 1, 2, 3, 4, 5, 6 のいずれかになります。
そこで、その余りの数によって整数を 7 つの集合に分けてみます。
\[\begin{align*}&C_0\,\{\:\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\:\}\\[6pt]
&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]
&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]
&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]
&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]
&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]
&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
それぞれの集合内の要素同士は法 7 のもとで合同です。このように互いに合同な整数の集合を 剰余類 (residue class) とよびます。$C$ は Class の頭文字です。
\[0,\:1,\:2,\:\cdots,\:m-1\]によって分類し、剰余が $r$ である数の集合を $C_r$ で表すと
\[C_0,\:C_1,\:C_2,\:\cdots,\:C_{m-1}\]という $m$ 個の類（剰余類）ができます。$C_r$ に属する全ての要素は
\[mt+r\:\:(t\in\mathbb{Z})\]と表すことができます。
法 7 による剰余類の例を見れば、どの整数も必ずどこかの剰余類に属し、また複数の剰余類に属することはないことは、ほぼ自明であるように思えますが、これについても一般的に証明しておきます。証明には前回説明した 同値関係 を用いるので、整数の合同における同値関係を再掲しておきます。
② 対称律 $a\equiv b\:(\mathrm{mod}\;m)$ ならば $b\equiv a\:(\mathrm{mod}\;m)$
③ 推移律 $a\equiv b,\:b=c\:(\mathrm{mod}\;m)$ ならば $a\equiv c\:(\mathrm{mod}\;m)$
① どの整数も必ずどこかの剰余類に属します。
② どの整数も複数の剰余類に属することはありません。すなわち
\[r\neq s\quad\Longrightarrow\quad C_r\cap C_s=\phi\]
ここで $\phi$ は空集合を表す記号で、上の定理は $r\neq s$ のときは $C_r$ かつ $C_s$ を満たす要素は存在しないことを述べています。
[定理 C1 の証明]
① 反射律 $a\equiv a\:(\mathrm{mod}\;m)$ より $a\in C_a$ です。
すなわち、どの整数も必ずどこかの剰余類に属します。
② $C_a$ と $C_b$ のどちらにも属する整数 $x$ が存在すると仮定すると
$b\in C_b,\:\:x\in C_b$ なので $b\equiv x\:(\mathrm{mod}\;m)$
推移律によって
\[a\equiv x,\:\:x\equiv b\:(\mathrm{mod}\;m)\]
であるならば $a\equiv b\:(\mathrm{mod}\;m)$ が成立します。つまり $C_a=C_b$ となって 2 つの類は完全に一致してしまいます。したがって、どの整数も複数の剰余類に属することはありません。
完全剰余系
先ほどの法 7 による剰余類を再掲します。
\[\begin{align*}&C_0\,\{\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\}\\[6pt]
&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]
&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]
&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]
&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]
&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]
&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
それぞれの剰余類から 1 つずつ値を取り出して、
\[\{14,\:8,\:-5,\:10,\:-2,\:19,\:27\}\]
という集合を作ってみます。当然のことながら、この集合には 7 で割ったときの余りの相異なる数が過不足なく含まれています。このような集合のことを 完全剰余系 とよびます。別にどのような値をとってきても完全剰余系であることに変わりはないのですが、たとえば
\[\{0,\:1,\:2,\:3,\:4,\:5,\:6\}\]
のように選ぶと、法 7 による完全剰余系であることが一目瞭然です。一般的な定義も載せておきます。
\[C_1,\:C_2,\:\cdots,\:C_{m-1}\]の中から 1 つずつ値（類の代表）を取り出して集めた数の組を完全剰余系とよびます。