2017年07月03日(月)

命題 整数\(n\)が素数\(p\)と互いに素であるならば、 \[n^{p-1}\equiv1\pmod p\] が成り立つ。 証明 \(p\)が素数のとき、集合\(X = \{ 1,2,3,\ldots,p-1 \}\)とおく。また\(X_n = \{xn \bmod p \,|\,x \in S \}\)としたとき、\(X_n = X\)が成り立つ(※1)。よって、\(X\)の要素をすべて乗じた結果と、\(X_n\)の要素をすべて乗じた結果は等しい。 \[ 1\cdot2\cdots(p-1) = (1n \bmod p)\cdot(2n\bmod p)\cdots((p-1)n \bmod p) \] これから、 \[ 1\cdot2\cdots(p-1) \equiv 1n\cdot2n\cdots(p-1)n \pmod p \] が成り立つ。式を整理して、 \[ (p-1)!\,n^{p-1} \equiv (p-1)! \pmod p \] \((p-1)!\)\(p\)と互いに素なので、 \[n^{p-1} \equiv 1 \pmod p\] が示された。(証明終わり)

※1の証明 https://story.hyuki.net/20170703002408/


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

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

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

Home Twitter 結城メルマガ note