オイラーの定理(整数論)

勉強を夜中までやってたら、今日は疲れが取れないまま1日が終わってしまいました・・・。
生活習慣は大切ですね。


今日の勉強で何とかオイラーの定理の導出を理解したので書いてみることにします。


まず、前提知識の準備をします。

ある正の整数nが与えられたとき、整数をnで割ったときの余りの値によって整数全体img3_20101105224030.pngをn個に分類する。
そうすると一般に余りがrとなる集合は
img1_20101105224054.png
となる。この集合img2_20101105224117.pngを剰余類という。剰余類の集合img4_20101105224155.pngを剰余類環という。

この剰余類環の元のうち、nと互いに素な元を既約剰余類という。
また、既約剰余類の元の個数をimg5_20101105224236.pngで表し、このimg5_20101105224236.pngオイラーの関数という。
img5_20101105224236.png個の既約剰余類の集合img6_20101105224323.pngを既約剰余類群という。

pが素数とすると、1〜p-1にpを因子とするものはないから、img7_20101105224347.pngとなる。
よってnがimg7_20101105224347.png素因数分解されるとすると、nのオイラーの関数img5_20101105224236.png
img9_20101105224636.png
となる。


ここまでで、前提知識の準備は終わり。

オイラーの定理を導出します。

二つの異なる既約剰余類img10_20101105224706.pngに任意の既約剰余類img11_20101105224724.pngを乗算した結果は異なる。これは合同式の性質から明らかである。
したがって、既約剰余類群の元全てに既約剰余類を掛けたものはすべて異なり、img6_20101105224323.pngの元であるので、これらの集合は元の既約剰余類群img6_20101105224323.pngに等しくなる。よって、
img11_20101105224724.png
である。この元の全ての積をとると
img13_20101105224837.png
ここで、両辺にimg1_20101106001820.pngの逆元を掛けると
img2_20101106001824.png
となる。これをオイラーの定理という。



ふう、数学記号が多くて画像作成に手間取ってしまいました。

既約剰余類"群"なんて書いてるけどホントに群なの?とかそういう質問は無しの方向で。
一応、証明したんですが記事はオイラーの定理についてなのでその辺は略しました。

wikipediaいわく、カーマイケルの定理というさらに一般化された定理があるようですが、聞いたこともないですし、暗号論で使うのがオイラーの定理のようなので、今回はここまで。

広告を非表示にする