アルゴリズム論特論（塩田）第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}$ の要素を書き出してみましょう。
Prop.8　素数 $p$ が法ならば、
$\znzc{p}=\{\,\ol{1},\ol{2},\cdots,\ol{(p-1)}\,\}$

既約剰余類の乗法構造

　ここから $\ol{\phantom{e}}$ を付けずに剰余類を書くことがありますが、 例えば $a = \ol{2}$ というように書いてあると思ってください。
Th.9
  1. $a \in \znzc{n}$ $\Leftrightarrow$ $\inv{a}$ が存在する
  2. $a$, $b \in \znzc{n}$ ならば $ab \in \znzc{n}$
  3. $a \in \znzc{n}$ ならば、
    $a$ 倍写像 : $x \mapsto ax$
    は　$\znz{n}$ から $\znz{n}$ 自身への全単射（一対一写像）であり、 また $\znzc{n}$ から $\znzc{n}$ 自身への全単射でもある。
証明　(1) は第6回の Th.6。
  1. $a$, $b \in \znzc{n}$ ならば (1) より $\inv{a}$, $\inv{b}$ が存在するので、 $\inv{a} \times \inv{b}$ は $ab$ の逆数となり $ab \in \znzc{n}$.
  2. $\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$ 倍写像は単射であり、有限集合自身への単射ゆえ全射にもなる。(証明終)
※　代数学用語で
  • $\znz{n}$ は環を成す
  • $\znzc{n}$ は乗法群を成す
と言います。

前へ / 戻る / 次へ