オイラーの定理

Nを2以上の自然数、ｍを1以上Ｎ以下の自然数で、Ｎと互いに素なものの個数とするとき、

a^m=1 (modN)

a^φ(N)=1 (modN)

例:　N=10→φ(10)=4

1^4=1,3^4=1,7^4=1,9^4=1 (mod10)

例:　N=33→φ(33)=20

N＝33と互いに素な任意の自然数aに対して

a^20=1 (mod33)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

N=15とします。

mは1,2,4,7,8,11,13,14の8個です。

1個（ここでは７）を選んで、それぞれに掛け算して、mod15を計算すると

7・1＝7,7・2＝14，7・4＝13,7・7＝4，7・8＝11，7・11＝2，7・13＝1,7・14＝8　　(mod15)

すなわち、1,2,4,7,8,11,13,14の並び替えになっている。

このことは任意のＮとＮと互いに素な任意の整数aについて成り立つ。

7・1＝7,7・2＝14，7・4＝13,7・7＝4，7・8＝11，7・11＝2，7・13＝1,7・14＝8　　(mod15)

の辺々掛け算すると

7^8・1・2・4・7・8・11・13・14=・1・2・4・7・8・11・13・14 　　(mod15)

1・2・4・7・8・11・13・14は15と互いに疎なので、割り算ができて

7^8=1 　　(mod15)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

Nを法とする既約剰余系：r1,r2,・・・rφ(N)を考え、（a,N)=1であるaを各rkに掛ける。

この乗算によって剰余の順序が変化するが、全体の積には影響を与えない。

N=10に対してr=1,3,7,9

a=7をかけると

ra=7,21,49,63=7,1,9,3 (mod10)

これより

a^φ(n)r1・r2・・・rφ(N)=r1・r2・・・rφ(N)　　(modN)

この剰余はNに対して素であるから

a^φ(N)=1 (modN)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝