[size=150][b][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][br]＜オイラーは拡張する＞[br][/b][/size][br][b]fermat定理は素数pを法としてa[sup]p-1[/sup]≡1 (mod p)だった。[br][/b]pが素数なら[size=100][color=#0000ff][b]φ(p)=p-1なので、[br][/b][/color][b]fermat定理は素数pを法としてa[/b][b][sup]φ(p)[/sup][/b][b]≡1 (mod p)とかけるね。[br]このオイラーの定理は、この式がｐが素数でないときも成り立つというものだ。[br][br]一般のｎに対して、[br][/b][b][size=200][color=#0000ff][b]a[/b][b][sup]φ(n)[/sup][/b][b]≡1 (mod n)[/b][br][/color][/size][/b][b][br]（理由）[br][/b]pは通常、素数を表す文字だから、ｐでなくｎにしよう。[/size]mod nの剰余は{0,1,2,3,....,n-1}のｎ通りある。[br]このうち、nと互いに素な要素だけ取り出そう。ｘ＝{a[sub]1[/sub],a[sub]2[/sub],....,a[sub]m[/sub]} m=φ(n)個だね。[br][br][b]少し、実験しよう。[br][/b]mod10のときの剰余は{0,1,2,...,9}の９通りある。[br]ｎと互いに素な要素はL={1,3,7,9｝の４個。もちろん、4=φ(10)だ。[br]3L(mod 10) ={3,9,1,7}と順番が入れ替わるだけ[br]だから、Lの４個の積K=product(L)に対して3Lの４個の積product(3L)=3[sup]4[/sup]Kになる。[br]一方で、3L(mod10)の4個の積はKに等しい。[br]だから、3[sup]4[/sup]K≡K(mod 10)。[br]Kは10と互いに素なので簡約できるはず。3[sup]4[/sup]≡1(mod10)。3[sup]φ(10)[/sup]＝3[sup]4[/sup]≡１（mod10)だね。[br]ということは、[br]1[sup]4[/sup]≡１（mod10)[br]7[sup]4[/sup]≡１（mod10)[br]9[sup]4[/sup]≡１（mod10)[br]も同様にして言えるだろう。[br][br]さっきの続きにもどる。[br]mod nの剰余は{0,1,2,3,....,n-1}のｎ通りある。[br]このうち、nと互いに素な要素だけ取り出そう。L＝{a[sub]1[/sub],a[sub]2[/sub],....,a[sub]m[/sub]} （m=φ(n)個）だね。[br]このLの１つの要素aにLをかけていくと、結果はバラバラ　aL=permutate{a[sub]1[/sub],a[sub]2[/sub],....,a[sub]m[/sub]} （m=φ(n)個）[br]もし、ax≡ay(mod n)となると、a(x-y)≡0(modｎ)となり、aはnの倍数でないから、x-yがｎの倍数。[br]しかし、x,yともにｎ以下なので、x-y=0しかない。つまり、かぶることはないから順列になる。[br]だから、Lのｍ個の積Kに対してaLのｍ個の積＝a[sup]m[/sup]Kになる。[br]fermatの証明のときにp-1個の積を考えたものが、m個の積に変わるだけなので、同じ論法が使えるね。[br]Lのｍ個の積Kに対してax(mod n)のｍ個の積はKに等しい。[br]だから、a[sup]m[/sup]K≡K(mod n)。Kはnと互いに素なので簡約できるはず。[br]a[sup]m[/sup]≡1(mod n)。a[sup]φ(n)[/sup]=a[sup]m[/sup]≡1(mod n)ということだね。[br][br]つまり、[color=#0000ff][b][size=150]aをｎと互いに素な要素に限定すると、[br]Fermat定理の証明と同じ議論の構造が成り立つことがわかるね。[/size][/b][/color][br][color=#0000ff][b][size=150][br][/size][/b][/color]

fermat定理のおかげで、[br]素数ｐの倍数がa[sup]p-1[/sup]-1で簡単に作れたり、[br]a[sup]p-1[/sup]≡1(mod p)から、a[sup]p-1[/sup]は何乗しても１なので、[br]a[sup]M[/sup]の計算をするのに、Mをp-1で割った余りに置き換えることができたね。[br]オイラーの定理があると、[color=#0000ff][b][u]この[/u][/b][u][b]便利さが一般の整数に広がる[/b][/u][/color]ということだね。[br]たとえば、[br][br][color=#0000ff][b][size=150]3[sup]2050[/sup]の下２けたを知りたいとしよう。[br][/size][/b][/color]3[sup]2050[/sup]≡ｘ(mod 100)をもとめることになるね。[br]3は100と互いに素なので、オイラーの定理が使える。[br]3[sup]φ(100)[/sup]≡1（mod 100)　φ(100)=100×(1-1/2)(1-1/5)=40。3[sup]40[/sup]≡1（mod 100)[br]2050=40・51+10なので、3[sup]2050[/sup]=(3[sup]40[/sup])[sup]51[/sup]・3[sup]10[/sup]≡3[sup]10[/sup] (mod 100)[br]一方で、3[sup]5[/sup]=243≡43(mod 100)[br]まとめると、[br]3[sup]2050[/sup]≡3[sup]10[/sup] ≡43[sup]2[/sup]≡49(mod 100)[br][br]実際は、pythonで計算すると、[br]3**2050=[br]12547932543561311232186175917031413650934560890259836808378605585488292344065939468[br]11365022284164650932244868923121220062606422100022852380538230979131136144904068614[br]26256196024055729753342052227815373903777152994621759234110689890318104575226850206[br]27182773951502405028145223463508621822456076133232051697157262659843576789124636632[br]68799753615925901938180909772664259181890228350472826735573271087239814127192369934[br]77142262534810397400125449148372760105518736739713799653372917971486145577705994938[br]38737888933951308229440993150557847663510171162364875127580876761085929149995935904[br]38904404608324963657136209333918709431693260048118476465924630884619753370060347354[br]57235560329229923359524657214001341493525354061406228997617975531678094204704989359[br]99120239529320818608076589797195535937608113625517985327608148683719508295059293131[br]43082879644124621504867920299624372550718884716712141351592342578793983267555399307[br]6411547374597613617663912022565288474716104689653921200848883302[color=#ff00ff][u]49[/u][/color][br]>>> [br]このくらいならオイラーの出番はない。