また次の表現も知られています。

上の形式から下の形式は，\(n\,\)が\(\,p\,\)と互いに素なとき，\(\,n\,\)を\(\,n^{p-1}\equiv 1\pmod{p}\,\)の両辺にかけることで得られます。

\(n\,\)が\(\,p\,\)と互いに素でないときも\(\,n^p,n \equiv 0 \pmod{p}\,\)なので，上の形式から下の形式が導けることが分かります。

逆に下の形式を認めると，\(\,n\,\)と\(\,p\,\)が互いに素のとき，\(\,n^p\equiv n\pmod{p}\,\)の両辺を\(\,n\,\)で割ることができるので，上の形式\(\,n^{p-1}\equiv 1 \pmod{p}\,\)が得られます。

フェルマーの小定理はRSA暗号や素数判定法などへの応用が知られています。

高校数学でもフェルマーの小定理を背景にした問題が多く，下のように特に京大の整数問題に使われている印象です。

このことについては“フェルマーの小定理と京大”で取り上げているので，ぜひ読んでみてください。

フェルマーの小定理の証明を4通り紹介します。

以後，合同式で\(\,(\operatorname{\mathrm{mod}}p)\,\)のときは，\(\,(\operatorname{\mathrm{mod}}p)\,\)を省略することにします。

前提として，フェルマーの小定理は整数\(\,n\,\)が自然数である場合にのみ示せば十分であることに注意しましょう。

なぜなら\(\,n=0\,\)のときは明らかで，もし\(\,n\gt 0\,\)のとき成り立つとすると，負の整数\(\,-n\,\,(n\gt 0)\,\)について，

\(p\not=2\,\)のとき，素数\(\,p\,\)は奇数なので，\(\,(-n)^p\equiv -n^p\equiv -n\,\)となるからです。

また\(\,p=2\,\)のとき，そもそも\(\,-1\equiv 1\,\)なので，\(\,n^2 \equiv n \Rightarrow (-n)^2\equiv (-n)\,\)だからです。

二項定理による証明

まず次の補題を確認します。

こちらの証明は簡単で，

\[{}_p\mathrm{C}_{k}=\dfrac{p\cdot (p-1)!}{(p-k)\cdot (p-1-k)!k!}=\dfrac{p}{p-k}{}_{p-1}\mathrm{C}_{k}\]

で，整理すると\(\,(p-k){}_p\mathrm{C}_{k}=p\,{}_{p-1}\mathrm{C}_{k}\,\)となります。

\(p\,\)は素数なので，\(\,p-k,{}_p\mathrm{C}_{k}\,\)のどちらかを割ります。

そして\(\,1\leq p-k\leq p-1\,\)で，\(\,p-k\,\)を割り切ることはないので，\(\,{}_p\mathrm{C}_{k}\,\)は\(\,p\,\)で割り切れるということです。

それでは補題を用いて，フェルマーの小定理を行っていきます。

数列\(\,\{a_n\}\,\)を\(\,a_n=n^p\,\)と定めます。

このとき二項定理と先ほど示した補題から

\[\begin{align*}&\,a_{n+1}\\=&\,(a+1)^p\\ =&\,a^p+{}_p\mathrm{C}_1a^{p-1}+\cdots+{}_p\mathrm{C}_{p-1}a+1 \\ \equiv &\, a^p+1 \\ =&\,a_n+1, \end{align*}\]

すなわち，合同式上の漸化式\(\,a_{n+1}=a_n+1\,\)が成り立ちます。

等差数列型の漸化式なので，簡単に解けて\(\,a_n\equiv n\,\)となります。

もちろんこれは\(\,n^p\equiv n\,\)のことであり，証明は完了しました。\(\quad\square\)

基本的な証明

まず\(\,n,2n,\ldots,(p-1)n\,\)の素数\(\,p\,\)による余りを考えます。

\(1,\ldots,p-1\,\)は\(\,p\,\)で割り切れないので，\(n\,\)が\(\,p\,\)で割り切れないとすると，これらの余りは\(\,0\,\)となりません。

つまり\(\,n,2n,\ldots,(p-1)n\,\)の余りは，\(\,1,\ldots,p-1\,\)のどれかとなります。

ここで\(\,n,2n,\ldots,(p-1)n\,\)のうち，余りが一致するものが存在する，

すなわち\(\,in\equiv jn\,\,(1\leq i,j\leq p-1)\,\)と仮定すると，\(\,n\,\)と\(\,p\,\)は互いに素なので，\(\,i\equiv j\,\)となります。

\(1\leq i,j\leq p-1\,\)より，これは\(\,i=j\,\)を意味します。

よって\(\,p-1\,\)個の数\(\,n,2n,\ldots,(p-1)n\,\)の余りはお互いに異なることが分かります。

余りとしてあり得るものも\(\,1,\ldots,p-1\,\)の\(\,p-1\,\)個の数なので，

\(n,2n,\ldots,(p-1)n\,\)の余りはうまく並び変えれば\(\,1,\ldots,p-1\,\)になります。

故に

\[(p-1)!n^{p-1}=n\cdot 2n \cdots (p-1)n\equiv 1\cdot 2\cdots (p-1)=(p-1)!\]

となります。

もちろん\(\,(p-1)!\,\)は，\(\,p\,\)が素数なので，\(\,p\,\)と互いに素となり，両辺から割ることできて，\(\,n^{p-1}\equiv 1\,\)を得ます。\(\quad\square\)

余談ですが，この証明を工夫すれば，フェルマーの小定理を拡張した次のオイラーの定理を示すことができます。

このことは補遺：オイラーの定理で解説しています。

ネックレスの数え上げによる証明

下図のような\(\,p\,\)個のビーズが並んだネックレスについて，\(\,n\,\)色によるビーズの塗り分け方を考えます。

上の図は例えば\(\,p=3,n\geq 3\,\)のときを考えています。使われない色があっても大丈夫です。

ただしネックレスを回転させて一致する場合は同じ塗り方とみなします。

裏返しによって一致する場合は異なる塗り方とみなします。

つまり，上図で真ん中と左のネックレスは同じ\(\,1\,\)つの塗り方としてカウントし，

右のネックレスは裏返しと回転によって左や真ん中に一致しますが，異なる塗り方としてカウントします。

数学的に言えば，数珠(じゅず)順列ではなく円順列で考えるということです。

ここで少なくとも\(\,2\,\)色の以上の色が使われているような塗分け方をカウントしましょう。

回転を一旦無視すれば，塗分け方の総数は\(\,p\,\)個のビーズにそれぞれ\(\,n\,\)色の選択肢があるので，\(\,a^p\,\)通りです。

反対に\(\,1\,\)色のみが使われているような塗り方は\(\,a\,\)通りなので，

回転を無視すれば，少なくとも\(\,2\,\)色の以上の色が使われているような塗分け方は\(\,a^p-a\,\)通りとなります。

この\(\,1\,\)つの塗分け方に対し，回転により一致するものは自身を含めて\(\,p\,\)個あります^※1。

回転を考慮すると，それらは同一視されるので，求めたい数は\(\,\dfrac{a^p-a}{p}\,\)となります。

もちろんこれは整数となるので，\(\,a^p-a\,\)は\(\,p\,\)で割り切れることが示されました。\(\quad\square\)

※1 ここに\(\,p\,\)が素数であるという条件が使われています。

実際，素数でない\(\,p=4,n\geq 2\,\)なら左の塗り方に対して，回転により一致するものは右のものしかなく，計\(\,2\,\)個です。

この例を聞いて，\(\,p\,\)が素数のとき一致するものは本当に\(\,p\,\)個になるのか不安になる方がいらっしゃると思うので，かなりくどいですが補足しておきます。

ただビーズを\(\,1\,\)つ右隣りに移す操作を\(\,p-1\,\)回繰り返せば，

\(2\,\)色以上を用いた\(\,1\,\)つの塗分けから，回転させて得られる塗分け方は重複を認めると，自身を含めて\(\,p\,\)個になります。

このとき重複がないことを証明できれば，回転により一致するものの数はそのまま\(\,p\,\)個になります。

※逆に\(\,p\,\)が素数でないときは，ここで重複が生じて一致するものの数が\(\,p\,\)個から減少し，証明がそのまま通用しなくなります。

そこで重複がないことを証明しましょう。

証明のために，適当な\(\,1\,\)つのネックレスを固定して，そこからビーズを右隣りに\(\,i\,\)個移すことで得られるネックレスを\(\,N_i\,\)と表すことにします。

今\(\,N_0,N_1,\ldots,N_{p-1}\,\)の中に一致するものがないことを言えば良いです。

仮に\(\,N_i,N_j\,\,(0\leq i\lt j \leq p-1)\,\)が一致したとしましょう。

\(0\lt j-i\leq p-1\,\)で\(\,p\,\)は素数なので，\(\,j-i\,\)は\(\,p\,\)と互いに素より，\(\,(j-i)x+py=1\,\)となる整数\(\,x,y\,\)が存在します。

これを用いて，\(\,x\geq 0\,\)のとき，ネックレス\(\,N_i\,\)のビーズを\(\,(j-i)x\,\)個右に移します。

これは\(\,j-i\,\)個右に移す操作を\(\,x\,\)回繰り返したと考えられるので，

仮定よりネックレス\(\,N_i\,\)はこの操作で\(\,N_j=N_i\,\)と元に戻ります。

その後\(\,p\,\)個右に移す操作を\(\,y\,\)回繰り返します(\(\,y\,\)が負なら右ではなく左に移すと考えます)。

\(p\,\)個移す作業はただの一回転ですので，結局\(\,N_i\,\)に戻ります。

以上で\(\,N_i\,\)からビーズを右に\(\,(j-i)x+py=1\,\)個ずらしても，元に戻ることが言えました。

つまり\(\,N_i=N_{i+1}\,\)が導かれました。

故に\(\,N_0=N_1=\cdots=N_{p-1}\,\)となり，すべてのネックレスが一致します。

このようにすべてのネックレスが一致する場合は，ネックレスに使われている色が\(\,1\,\)つだけのときしかあり得ません。

しかしネックレスに\(\,2\,\)色以上用いられてる場合を考えているので矛盾します。

\(x\lt 0\,\)のときは，ネックレス\(\,N_j\,\)のビーズを\(\,(j-i)(-x)\,\)個左に移せば，同様に\(\,N_i=N_j\,\)と元に戻ります。

後は\(\,x\geq 0\,\)の場合と同様にして矛盾を示せます。

以上より題意は示されました。\(\quad\square\)

群論による証明

群論の基礎知識により証明します。

\(\mathbb{Z}/p\mathbb{Z}\,\)の乗法群\(\,(\mathbb{Z}/p\mathbb{Z})^{\times}\,\)は位数\(\,p-1\,\)の巡回群です。

\(n\,\)と\(\,p\,\)は互いに素とすると，\(\,n\in(\mathbb{Z}/p\mathbb{Z})^{\times}\,\)とみなせ，先ほど述べたことより\(\,n\,\)の位数は\(\,p-1\,\)の約数です。

故に\(\,n^{p-1} \equiv 1\,\)となり，題意は示されました。\(\quad\square\)

こちらの証明方法もオイラーの定理の証明へと拡張できます。

補遺で解説しているので，良ければご覧ください。

今回の記事ではフェルマーの小定理を解説いたしました。

実は私の一番好きな定理です。

本質的に同じ証明とみなせるものもありますが，AoPs Onlineにここで紹介した以外の証明も記されています。

意欲のある方は読んでみると良いでしょう。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#サイエンティクスでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

補遺としてフェルマーの小定理を\(\,p\,\)が素数でない場合に一般化したオイラーの定理を取り上げます。

説明のために次のオイラー関数を定義します。

このオイラー関数を用いて，フェルマーの小定理を拡張したオイラーの定理が成り立ちます。

確かに素数\(\,p\,\)について，\(\,\varphi(p)=p-1\,\)なので，オイラーの定理からフェルマーの小定理が得られることが分かります。

ただし今度は，任意の整数\(\,n\,\)について，\(\,n^{\phi(m)+1}\equiv n\pmod{m}\,\)という別表式は成り立たないことに注意しましょう。

実際\(\,m=4,n=2\,\)のときを考えれば，

\[n^{\varphi(m)}=2^3\equiv 0\not\equiv 2=n\]

となります。

まずオイラーの定理を基本的な証明と同じ方針で証明しましょう。

今度は\(\,n,2n,\ldots,(p-1)n\,\)を一般化して，

\(1,\ldots, m-1\,\)の中で\(\,m\,\)と互いに素なもの\(\,x_1,\ldots,x_{\varphi(m)}\,\)をおき，

それらを\(\,n\,\)倍した\(\,x_1n,x_2n,\ldots,x_{\varphi(m)}n\,\)の\(\,m\,\)による余りを考えます。

\(n,x_i\,\)も\(\,m\,\)と互いに素なので，その余りも\(\,m\,\)と互いに素となります。

つまりその余りは\(\,x_1,\ldots,x_{\varphi(m)}\,\)のどれかとなるということです。

基本的な証明と同様にして，\(\,x_1n,x_2n,\ldots,x_{\varphi(m)}n\,\)のどの2つも余りが一致しないことが示せます。

故に\(\,x_1n,x_2n,\ldots,x_{\varphi(m)}n\,\)の余りは，うまく並び変えれば\(\,x_1,\ldots,x_{\varphi(m)}\,\)になります。

したがって

\[(x_1\cdots x_n)n^{\varphi(m)}\equiv x_1\cdots x_n\pmod{m}\]

が得られ，\(\,m\,\)と互いに素であることから\(\,x_1\cdots x_n\,\)を両辺で割ると，\(\,n^{\varphi(m)}\equiv 1\,\)が得られます。\(\quad\square\)

今度は群論による証明と同じ方針で証明します。

\[\varphi(m)=|(\mathbb{Z}/m\mathbb{Z})^{\times}|\]

に注意するだけです。

\(n\,\)と\(\,m\,\)は互いに素とすると，\(\,n\in (\mathbb{Z}/m\mathbb{Z})^\times\,\)とみなせ，\(\,n\,\)の位数は\(\,\varphi(m)\,\)の約数となります。

故に\(\,n^{\varphi(m)}\equiv 1\pmod{m}\,\)となり，題意は示されました。\(\quad\square\)

• \([1]\) “Fermat’s Little Theorem”.AoPs Online.https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem.2026-04-26参照