整数\(n\)が整数\(m > 1\)と互いに素であるならば、 \[ n^{\varphi(m)}\equiv1\pmod m \] が成り立つ。
\(m\)と互いに素である\(m\)未満の正整数全体の集合を\[X = \{ x_1,x_2,\ldots,x_{\varphi(m)}\}\]とする。また集合\(X_n\)を、 \[ X_n = \{xn \bmod m \,|\,x \in X \} \] とおくと、\(X_n = X\)が成り立つ（注1）。よって\(X_n\)の要素をすべて乗じた結果と、\(X\)の要素をすべて乗じた結果は等しい。 \[ x_1\cdot x_2\cdots x_{\varphi(m)} = (x_1n \bmod m)\cdot(x_2n \bmod m)\cdots (x_{\varphi(m)}n \bmod m) \] これから、 \[x_1\cdot x_2\cdots x_{\varphi(m)}\equiv x_1n\cdot x_2n\cdots x_{\varphi(m)}n \pmod m\] が成り立つ。式を整理して、 \[n^{\varphi(m)}\prod_{x \in X}x \equiv \prod_{x \in X}x \pmod m\] \(\prod\limits_{x \in X}x\)は\(m\)と互いに素なので、 \[n^{\varphi(m)} \equiv 1 \pmod m\] が示された。（証明終わり）
https://story.hyuki.net/20170703002408/
※メモ \(m > 1\)と入れたのは\(m = 1\)のときの取り扱いを（フェルマーの小定理との関係で）整理したいから。あとで考える。
