MathJax初導入ということで，離散対数問題を \( \bmod \) 演算だけでなく，
演算を一般化して考えてみましょう．
まずは，集合と演算子の組 \( (\mathbb{G}, \odot) \) が
群になす条件について復習しましょう．
\( \TeX \) の数式が使えるからうれしい．
なぜ， \( \mathbb{G} \) なのか？
群を英語で言うとGroupで，
頭文字をとって \( \mathbb{G} \) としているからです．
- 全ての \( x, y \in \mathbb{G} \) に対して， \( x \odot y \in \mathbb{G} \) ．
つまり，演算結果も集合 \( \mathbb{G} \) の中に入っているということです． - 全ての \( x, y \in \mathbb{G} \) に対して， \( (x \odot y) \odot z = x \odot (y \odot z) \)．
いわゆる，結合法則ですね．
ここまで満たせば半群になりますが，
群をなすというためにはさらに二つの条件が必要です．
- 全ての \( x \in \mathbb{G} \) に対して \( x \odot e = e \odot x = x \) となるような
\( e \in \mathbb{G} \) がただ一つ存在する．
つまり，単位元が存在するということで，演算を施しても自分自身であるということですね． - 全ての \( x \in \mathbb{G} \) に対して \( x \odot y = y \odot x = e \) となるような
\( y \in \mathbb{G} \) がただ一つ存在する．
つまり，逆元が存在するということで，この \( y \) を \( y = x^{-1} \) と書きます．
足し算だったら， \( y = -x \) と書いたほうがわかりやすいでしょう．
集合 \( \mathbb{G} \) の要素数 \( |\mathbb{G}| \) を
群 \( (\mathbb{G}, \odot) \) の位数といいます．
位数が有限の群を有限群といいます．
このとき，次の定理が知られています．
これはフェルマーの定理を一般化したものです．
定理 有限群 \( (\mathbb{G}, \odot) \) において，任意の \( a \in \mathbb{G} \) に対して \[ \underbrace{a \odot a \odot \dots \odot a}_{|\mathbb{G}|} = e \] である．
この定理の意味は，どんな \( a \) を \( \mathbb{G} \) の要素数の回数だけ演算すれば，
必ず単位元 \( e \) に戻ってくるということです．
では，例を見てみましょう．
5で割った余りの世界（つまり集合 \( \mathbb{Z}_5 \) ）で考えてみましょう．
\( (\mathbb{Z}_5, +) \) の単位元は0ですね（小学生でもわかるはずです）．
5回同じ数で足し算して，その答えを5で割って，余りを計算してみましょう．
\[ 0 + 0 + 0 + 0 + 0 = 0 \equiv 0 \pmod{5} \]
\[ 1 + 1 + 1 + 1 + 1 = 5 \equiv 0 \pmod{5} \]
\[ 2 + 2 + 2 + 2 + 2 = 10 \equiv 0 \pmod{5} \]
\[ 3 + 3 + 3 + 3 + 3 = 15 \equiv 0 \pmod{5} \]
\[ 4 + 4 + 4 + 4 + 4 = 20 \equiv 0 \pmod{5} \]
ちゃんと0になったので，フェルマーの定理が正しいことが確かめられました．
めでたしめでたし．