■フェルマー・オイラー・ウィルソン(その8)

オイラーの定理

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

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個(ここでは7)を選んで、それぞれに掛け算して、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の並び替えになっている。

このことは任意のNとNと互いに素な任意の整数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)

===================================