2017年07月03日(月)

命題

整数\(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\] が示された。(証明終わり)

注1

https://story.hyuki.net/20170703002408/

※メモ \(m > 1\)と入れたのは\(m = 1\)のときの取り扱いを(フェルマーの小定理との関係で)整理したいから。あとで考える。


 このお話をTwitterでシェアする  このお話についてnoteで書く

結城浩(ゆうき・ひろし) @hyuki

『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Home Twitter 結城メルマガ note