Eulerは拡張する
順番がかわるだけ
１．オイラーはフェルマーを同じ理屈
このワークシートはMath by Codeの一部です。
＜オイラーは拡張する＞
fermat定理は素数pを法としてap-1≡1 (mod p)だった。
pが素数ならφ(p)=p-1なので、
fermat定理は素数pを法としてaφ(p)≡1 (mod p)とかけるね。
このオイラーの定理は、この式がｐが素数でないときも成り立つというものだ。
一般のｎに対して、
aφ(n)≡1 (mod n)
（理由）
pは通常、素数を表す文字だから、ｐでなくｎにしよう。mod nの剰余は{0,1,2,3,....,n-1}のｎ通りある。
このうち、nと互いに素な要素だけ取り出そう。ｘ＝{a1,a2,....,am} m=φ(n)個だね。
少し、実験しよう。
mod10のときの剰余は{0,1,2,...,9}の９通りある。
ｎと互いに素な要素はL={1,3,7,9｝の４個。もちろん、4=φ(10)だ。
3L(mod 10) ={3,9,1,7}と順番が入れ替わるだけ
だから、Lの４個の積K=product(L)に対して3Lの４個の積product(3L)=34Kになる。
一方で、3L(mod10)の4個の積はKに等しい。
だから、34K≡K(mod 10)。
Kは10と互いに素なので簡約できるはず。34≡1(mod10)。3φ(10)＝34≡１（mod10)だね。
ということは、
14≡１（mod10)
74≡１（mod10)
94≡１（mod10)
も同様にして言えるだろう。
さっきの続きにもどる。
mod nの剰余は{0,1,2,3,....,n-1}のｎ通りある。
このうち、nと互いに素な要素だけ取り出そう。L＝{a1,a2,....,am} （m=φ(n)個）だね。
このLの１つの要素aにLをかけていくと、結果はバラバラ aL=permutate{a1,a2,....,am} （m=φ(n)個）
もし、ax≡ay(mod n)となると、a(x-y)≡0(modｎ)となり、aはnの倍数でないから、x-yがｎの倍数。
しかし、x,yともにｎ以下なので、x-y=0しかない。つまり、かぶることはないから順列になる。
だから、Lのｍ個の積Kに対してaLのｍ個の積＝amKになる。
fermatの証明のときにp-1個の積を考えたものが、m個の積に変わるだけなので、同じ論法が使えるね。
Lのｍ個の積Kに対してax(mod n)のｍ個の積はKに等しい。
だから、amK≡K(mod n)。Kはnと互いに素なので簡約できるはず。
am≡1(mod n)。aφ(n)=am≡1(mod n)ということだね。
つまり、aをｎと互いに素な要素に限定すると、
Fermat定理の証明と同じ議論の構造が成り立つことがわかるね。
オイラー定理の使い道
fermat定理のおかげで、
素数ｐの倍数がap-1-1で簡単に作れたり、
ap-1≡1(mod p)から、ap-1は何乗しても１なので、
aMの計算をするのに、Mをp-1で割った余りに置き換えることができたね。
オイラーの定理があると、この便利さが一般の整数に広がるということだね。
たとえば、
32050の下２けたを知りたいとしよう。
32050≡ｘ(mod 100)をもとめることになるね。
3は100と互いに素なので、オイラーの定理が使える。
3φ(100)≡1（mod 100) φ(100)=100×(1-1/2)(1-1/5)=40。340≡1（mod 100)
2050=40・51+10なので、32050=(340)51・310≡310 (mod 100)
一方で、35=243≡43(mod 100)
まとめると、
32050≡310 ≡432≡49(mod 100)
実際は、pythonで計算すると、
3**2050=
12547932543561311232186175917031413650934560890259836808378605585488292344065939468
11365022284164650932244868923121220062606422100022852380538230979131136144904068614
26256196024055729753342052227815373903777152994621759234110689890318104575226850206
27182773951502405028145223463508621822456076133232051697157262659843576789124636632
68799753615925901938180909772664259181890228350472826735573271087239814127192369934
77142262534810397400125449148372760105518736739713799653372917971486145577705994938
38737888933951308229440993150557847663510171162364875127580876761085929149995935904
38904404608324963657136209333918709431693260048118476465924630884619753370060347354
57235560329229923359524657214001341493525354061406228997617975531678094204704989359
99120239529320818608076589797195535937608113625517985327608148683719508295059293131
43082879644124621504867920299624372550718884716712141351592342578793983267555399307
641154737459761361766391202256528847471610468965392120084888330249
>>>
このくらいならオイラーの出番はない。