一般化されたフェルマーの定理

  • 投稿日:
  • by
  • カテゴリ:

MathJax初導入ということで,離散対数問題を modmod 演算だけでなく,
演算を一般化して考えてみましょう.

まずは,集合と演算子の組 (G,)
群になす条件について復習しましょう.
TEX の数式が使えるからうれしい.

なぜ, G なのか?

群を英語で言うとGroupで,
頭文字をとって G としているからです.

  • 全ての x,yG に対して, xyG
    つまり,演算結果も集合 G の中に入っているということです.
  • 全ての x,yG に対して, (xy)z=x(yz)
    いわゆる,結合法則ですね.

ここまで満たせば半群になりますが,
群をなすというためにはさらに二つの条件が必要です.

  • 全ての xG に対して xe=ex=x となるような
    eG がただ一つ存在する.
    つまり,単位元が存在するということで,演算を施しても自分自身であるということですね.
  • 全ての xG に対して xy=yx=e となるような
    yG がただ一つ存在する.
    つまり,逆元が存在するということで,この yy=x1 と書きます.
    足し算だったら, y=x と書いたほうがわかりやすいでしょう.

集合 G の要素数 |G|
(G,)位数といいます.

位数が有限の群を有限群といいます.

このとき,次の定理が知られています.
これはフェルマーの定理を一般化したものです.

定理  有限群 (G,) において,任意の aG に対して aaa|G|=e である.

この定理の意味は,どんな aG の要素数の回数だけ演算すれば,
必ず単位元 e に戻ってくるということです.

では,例を見てみましょう.
5で割った余りの世界(つまり集合 Z5 )で考えてみましょう.

(Z5,+) の単位元は0ですね(小学生でもわかるはずです).
5回同じ数で足し算して,その答えを5で割って,余りを計算してみましょう.
0+0+0+0+0=00(mod5) 1+1+1+1+1=50(mod5) 2+2+2+2+2=100(mod5) 3+3+3+3+3=150(mod5) 4+4+4+4+4=200(mod5)

ちゃんと0になったので,フェルマーの定理が正しいことが確かめられました.
めでたしめでたし.