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

アルゴリズム論特論（塩田）第7回 (2)　既約剰余類

$\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.6　

$\gcd(b,n) = 1$ を満たす

$b$ の属する剰余類を「法

$n$ の既約剰余類 ( きやくじょうよるい ) 」と呼ぶ。それらすべての集合を

$\znzc{n}$ と表し、ゼット・オーバー

$n$ ゼット・クロスと読む。

　教科書によっては

$(\znz{n})^{\ast}$ と書いていることもありますが、同じものです。

Ex.7　

$\znzc{2}=\{\,\ol{1}\,\}$ ,

$\quad\znzc{3}=\{\,\ol{1},\ol{2}\,\}$ ,

$\quad\znzc{4}=\{\,\ol{1},\ol{3}\,\}$ .

やってみよう　

$n=5,6,7,10$ に対しても

$\znzc{n}$ の要素を書き出してみましょう。

$\znzc{5}=\{\,\ol{1},\ol{2},\ol{3},\ol{4}\,\}$ ,
　

$\znzc{6}=\{\,\ol{1},\ol{5}\,\}$ ,
　

$\znzc{7}=\{\,\ol{1},\ol{2},\ol{3},\ol{4},\ol{5},\ol{6}\,\}$ ,
　

$\znzc{10}=\{\,\ol{1},\ol{3},\ol{7},\ol{9}\,\}$

Prop.8　素数

$p$ が法ならば、

$\znzc{p}=\{\,\ol{1},\ol{2},\cdots,\ol{(p-1)}\,\}$

既約剰余類の乗法構造

　ここから

$\ol{\phantom{e}}$ を付けずに剰余類を書くことがありますが、例えば

$a = \ol{2}$ というように書いてあると思ってください。

Th.9

$a \in \znzc{n}$ $\Leftrightarrow$ $\inv{a}$ が存在する
$a$ , $b \in \znzc{n}$ ならば $ab \in \znzc{n}$
$a \in \znzc{n}$ ならば、 $a$ 倍写像 : $x \mapsto ax$ は　 $\znz{n}$ から $\znz{n}$ 自身への全単射（一対一写像）であり、また $\znzc{n}$ から $\znzc{n}$ 自身への全単射でもある。

証明　(1) は第6回の Th.6。

$a$ , $b \in \znzc{n}$ ならば (1) より $\inv{a}$ , $\inv{b}$ が存在するので、 $\inv{a} \times \inv{b}$ は $ab$ の逆数となり $ab \in \znzc{n}$ .
$\inv{a}$ が存在すると $ax=ay \quad \Rightarrow \quad x = 1 \times x = \left(\inv{a}\right) \times a \times x = \left(\inv{a}\right) \times a \times y = 1 \times y = y$ ゆえ $a$ 倍写像は単射であり、有限集合自身への単射ゆえ全射にもなる。(証明終)

※　代数学用語で

と言います。