群、環、体とかの言葉の整理 - ちりもつもればミルキーウェイ

はじめに

これは RSA完全理解 Advent Calendar の9日目の記事です。

前回までで拡張ユークリッド互除法でベズーの等式の解を探索できることがわかったので、それで剰余環の逆元がだせることを知るために言葉の整理をしよう！という回です。

(というか説明で剰余環とかの語彙を使わざる得ないんだからもうちょっと早めにやればよかった)

それではやっていきましょう

おもに言葉の説明になるのでざっくりサマリをさきにおいておく

空ではない集合 $\mathbb{G}$ があったとき以下の性質を満たす演算 $\circ$ が割り当てられるとき群(group)という。このときの演算の操作は任意に設定してよい

結合法則: すべての元 $a, b, c \in \mathbb{G}$ に対して $(a\circ b)\circ c = a\circ (b\circ c)$ が成り立つ
単位元が存在する: すべての元 $a \in \mathbb{G}$ に対して $a\circ e = e\circ a = a$ となるような元 $e \in \mathbb{G}$ が存在する。このような元 $e$ を単位元とよぶ。ようは演算した結果自分自身に戻るような元 $e$ が存在するということ
逆元が存在する: すべての元 $a \in \mathbb{G}$ に対して $b \in \mathbb{G}$ が存在して $a\circ b = b\circ a = e$ となる元が存在する。そのような元を逆元といい $a^{-1}$ とあらわす。すべての元に演算すると単位元に戻るような元 $a^{-1}$ が存在するということ

例を出してみると、一般的に整数集合 $\mathbb{Z}$ は通常の加算の二項演算について群である。確認していくと

さらに演算について交換法則も成り立つ場合、可換群とよぶ

加法の演算についての群を加法群、乗法の演算についての群を乗法群といったりもする

空ではない集合 $\mathbb{A}$ があったとき、加法 $+$ と乗法 $\cdot$ をもち以下の条件を満たす集合を環(ring)とよぶ

$\mathbb{A}$ は加法 $+$ について可換群である
結合法則: すべての元 $a, b, c \in \mathbb{A}$ に対して $(a\cdot b)\cdot c = a\cdot (b\cdot c)$ がなりたつ
分配法則: すべての元 $a, b, c \in \mathbb{A}$ に対して $a\cdot (b + c) = a\cdot b + b\cdot c, (a + b)\cdot c = a\cdot c + b\cdot c$ が成り立つ

このとき加法の単位元のことを零元といい $0$ であらわします

具体例をかんがえてみると整数集合 $\mathbb{Z}$ に対して $n$ で割ったときの剰余の集合 $\mathbb{Z}/n\mathbb{Z}$ は環であり、特に剰余環とよびます。いままでつかっていた何気ないワードが回収されたな！

は加法について可換群です
- 任意の $x \in \mathbb{Z}/n\mathbb{Z}$ について $x + 0 = x$ なので単位元は $0$
- ちょうど加算してちょうど法 $n$ の値になれば割り切れて単位元 $0$ となるため、任意の $x \in \mathbb{Z}/n\mathbb{Z}$ に対する逆元は $n-x$ となる
- $\mathbb{Z}$ の通常の加法 $+$ は結合法則がなりたっている。単にその結果を $n$ で割った余りを考えれば結合法則は成り立つ
- $\mathbb{Z}$ の通常の加法 $+$ は交換法則がなりたっている。単にその結果を $n$ で割った余りを考えれば交換法則は成り立つ
$\mathbb{Z}$ の通常の乗法 $\cdot$ は結合法則がなりたっている。単にその結果を $n$ で割った余りを考えれば結合法則は成り立つ
$\mathbb{Z}$ の通常の乗法 $\cdot$ は分配法則がなりたっている。単にその結果を $n$ で割った余りを考えれば分配法則は成り立つ

また、乗法演算についての交換法則も成り立つ場合、可換環とよびます。 $\mathbb{Z}/n\mathbb{Z}$ は可換環でもあり

ことからそれがわかります。

体(field) $\mathbb{F}$ は零元を除いた元について、可換でありなおかつ乗法に対しての逆元が存在する特殊な環のことです。体は可換環の性質に加えてさらに以下の条件を満たします

ようは $0$ を除いた可換環が、さらに乗法に対して逆元をもってれば体であると言えます。

具体例をみてみましょう
一般に $p$ を素数とする剰余環 $\mathbb{Z}/p\mathbb{Z}$ は体です。

$\mathbb{Z}/p\mathbb{Z}$ は可換環 $\mathbb{Z}/n\mathbb{Z}$ のより特殊な形と言えるので、可換環の性質はすべて満たしています。
乗算の逆元の存在
- 剰余環の乗算の単位元はさきほど紹介したように $1$ なので $a \in \mathbb{Z}/p\mathbb{Z} \backslash \lbrace 0 \rbrace$ としたとき $a\cdot a^{-1} \equiv 1\pmod p$ となるような逆元 $a^{-1}$ が存在すればよいです。
- $a\cdot a^{-1} \equiv 1\pmod p$ は $a \equiv a\pmod p$ に $a^{-1}$ を乗算しているので $a$ にて除算するようにも考えられます
- 合同式の両辺を除算できる条件は除数と法 $p$ が互いに素なことであり、 $p$ が素数な場合は任意の $a \in \mathbb{Z}/p\mathbb{Z} \backslash \lbrace 0 \rbrace$ と互いに素であることが保証できます。なのでこの式は任意の元 $a$ について除算可能です
- よって $\mathbb{Z}/p\mathbb{Z} \backslash \lbrace 0 \rbrace$ は乗算について逆元を持ちます

また、特に有限な元からなる体のことを有限体といい、その要素数を $p$ として $\mathbb{F}_p$ と書きます