オイラーの定理
準備
$ {\rm\mathcal Cop}(n)
$ \varphi(n)=\#{\rm\mathcal Cop}(n)
定理
$ a\in{\rm\mathcal Cop}(n)とする。
$ a^{\varphi(n)}\overset n\equiv 1
ちなみに
$ a^{-1}\overset n\equiv a^{\varphi(n)-1}
だが、オイラー関数を求める計算量が$ \Omicron(\sqrt n)なので速い計算はできない 証明
$ {\rm\mathcal Cop}(n)=\{x_1,\cdots,x_{\varphi(n)}\}とする。
$ {\rm\mathcal Cop}(n)の各要素を$ a倍した集合$ a{\rm\mathcal Cop}(n)を定める。
$ a{\rm\mathcal Cop}(n)=\{ax_1,\cdots,ax_{\varphi(n)}\}
$ a{\rm\mathcal Cop}(n)は$ {\rm\mathcal Cop}(n)の要素の順番を入れ替えたものである。
$ x_i,aは$ nと互いに素であるため、$ ax_iもまた$ nと互いに素である。
また、$ x_1,\cdots,x_{\varphi(n)}は相異なるため、$ ax_1,\cdots,ax_{\varphi(n)}もまた相異なる。
よって$ a{\rm\mathcal Cop}(n)は$ {\rm\mathcal Cop}(n)の要素の順番を入れ替えたものである。
従って、$ \prod_{i=1}^{\varphi(n)}(ax_i)\overset n\equiv\prod_{i=1}^{\varphi(n)}x_i
$ a^{\varphi(n)}\prod_{i=1}^{\varphi(n)}x_i\overset n\equiv\prod_{i=1}^{\varphi(n)}x_i
$ \therefore a^{\varphi(n)}\overset n\equiv1