勉強を夜中までやってたら、今日は疲れが取れないまま1日が終わってしまいました・・・。
生活習慣は大切ですね。
今日の勉強で何とかオイラーの定理の導出を理解したので書いてみることにします。
まず、前提知識の準備をします。
ある正の整数nが与えられたとき、整数をnで割ったときの余りの値によって整数全体
をn個に分類する。
そうすると一般に余りがrとなる集合は
となる。この集合
を剰余類という。剰余類の集合
を剰余類環という。
この剰余類環の元のうち、nと互いに素な元を既約剰余類という。
また、既約剰余類の元の個数を
で表し、このをオイラーの関数という。
個の既約剰余類の集合
を既約剰余類群という。
pが素数とすると、1〜p-1にpを因子とするものはないから、
となる。
よってnがと素因数分解されるとすると、nのオイラーの関数は
となる。
ここまでで、前提知識の準備は終わり。
オイラーの定理を導出します。
二つの異なる既約剰余類
に任意の既約剰余類
を乗算した結果は異なる。これは合同式の性質から明らかである。
したがって、既約剰余類群の元全てに既約剰余類を掛けたものはすべて異なり、の元であるので、これらの集合は元の既約剰余類群に等しくなる。よって、
である。この元の全ての積をとると
ここで、両辺に
の逆元を掛けると
となる。これをオイラーの定理という。
ふう、数学記号が多くて画像作成に手間取ってしまいました。
既約剰余類"群"なんて書いてるけどホントに群なの？とかそういう質問は無しの方向で。
一応、証明したんですが記事はオイラーの定理についてなのでその辺は略しました。
wikipediaいわく、カーマイケルの定理というさらに一般化された定理があるようですが、聞いたこともないですし、暗号論で使うのがオイラーの定理のようなので、今回はここまで。
