アルゴリズム論特論（塩田）2023年度

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

戻る / 次へ