アルゴリズム論特論(塩田)第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 から矛盾が生じません。