アルゴリズム論特論（塩田）第7回 (1) 剰余類
戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
剰余類
まずは定義から。
Def.1 法 $n$ の合同関係により $a$ の属する同値類を
$\bar a$
と表して、$a$ の属する「法 $n$ の 剰余類 ( じょうよるい ) 」と呼ぶ。
その実体は集合であって、
$\bar a=\{\,$ 法 $n$ で $a$ と合同な整数たち$\,\}$
である。
Rem.2 $a \equiv b \pmod n$ $\ \Leftrightarrow\ $ $\bar a = \bar b$
※ 前々回「$\equiv$ はイコール感覚で使える」というフレーズが出てきましたが、
本当にイコールにしてしまおう、という表記法です。
Ex.3 $n=7$, $a=2$ のとき、集合として
$\ol{2}=\{\,\cdots,\,-12,\,-5,\,2,\,9,\,\cdots\,\}$
であり、
$\cdots=\ol{(-12)}=\ol{(-5)}=\ol{2}=\ol{9}=\cdots$
です。
Def.4 法 $n$ の剰余類全ての集合を $\znz{n}$ と表し、
ゼット・オーバー $n$ ゼットと読む。
$\znz{n} = \{\,\ol{0},\,\ol{1},\,\cdots,\,\ol{(n-1)}\,\}$
であり、$\znz{n}$ には $n$ 個の要素がある。
剰余類の四則演算
法演算を剰余類で表現すると
Th.5 $\znz{n}$ には次のようにして加減乗除の四則演算が定義できる。
\begin{align}
\bar a + \bar b &= \ol{(a+b)} \\
\bar a - \bar b &= \ol{(a-b)} \\
\bar a \times \bar b &= \ol{(a \times b)} \\
\bar a \div \bar b &= \ol{\left(a \times \inv{b}\right)} \\
\end{align}
ただし除算においては、除数 $b$ は $\gcd(b,n) = 1$ を満たすものに限り、$\inv{b}$ は法 $n$ での $b$ の逆数を表す。
うかっと見ると意味が分かりませんが、
左辺は剰余類同士の演算で、それを右辺の式で定義しよう、という式です。
例えば $n=7$ のとき、
$\ol{2} = \ol{9}$,
$\quad\ol{3} = \ol{10}$
なので
$\ol{2} \times \ol{3} = \ol{(2 \times 3)}$
でもあるし、
$\ol{2} \times \ol{3} = \ol{9} \times \ol{10} = \ol{(9 \times 10)}$
でもあるのですが、第5回
Th.6 から
$\ol{(2 \times 3)} = \ol{(9 \times 10)}$
が保証されているので矛盾が生じない訳です（ well-defined, と言います）。
除算も同様に第6回
Th.5 から矛盾が生じません。