目次
主張
フェルマーの小定理：\(n\)を正の整数、\(p\)を素数とするとき、\(\mathrm {mod} p\)のもとで以下の関係式が成立する。
\(n^p \equiv n (\mathrm {mod} p)\)
特に、\(n\)と\(p\)が互いに素のとき、この両辺を\(n\)で割ることにより以下の関係式が成立する。
\(n^{p-1} \equiv 1 (\mathrm {mod} p)\)
以下では汎用性の高い証明方法を２つ説明し、関連した自作問題（分野：整数）も紹介しておきます。
では、ぜひ最後までご覧になってください。
証明
方針
「\(n\)を正の整数とする」という文言がありますが、これは暗に、「すべての正の整数\(n\)について証明せよ」と言っています。ですので、まず思い付く解法としては数学的帰納法でしょう。また、この手法以外でも証明２に提示されているような整数の有名な定理を用いた証明もあります。この定理は証明の流れも合わせて知っておくと、他の入試問題にも適用することができ、便利でしょう。余裕のある方は証明２も読んでみてください。
証明１の途中で２項係数に関する有名な性質：\(p\)が素数、\(1 \leq k \leq p-1\)のとき、\({}_n \mathrm{C} _k\)は\(p\)の倍数である
ことを使います。この性質は大学入試でも頻出です。記述式答案では自力で証明できるように練習しておきましょう。（記述量はそんなに多くなくて楽ですよ。）
証明１（数学的帰納法を用いた証明）
証明するべきことは、\(f(n)=n^p - n\)が\(p\)の倍数であることと同値である。（∵\(\mathrm {mod}\)の性質）
（ⅰ）\(n=1\)のとき
\(f(1)=1^p -1 =0 \equiv 0 (\mathrm{mod}p)\)より主張は正しい。
（ⅱ）ある正の整数\(n\)で題意の主張が成立するとき
２項定理によって\({(n+1)}^p\)を展開することにより、
f(n+1) &={(n+1)}^p - (n+1) \\
&=\sum_{k=0}^{p} {}_p \mathrm{C} _k n^k -(n+1) \\
&=\sum_{k=1}^{p-1} {}_p \mathrm{C} _k n^k +1+n^p-(n+1) \\
&=\sum_{k=1}^{p-1} {}_p \mathrm{C} _k n^k +(n^p-n) \\
\end{align}
ここで、帰納法の仮定によって、\(n^p-n \equiv 0 (\mathrm{mod}p)\)が成立しているので、Σの部分が\(p\)の倍数であることを示すことが目標となる。
さて、\(1 \leq k \leq p-1\)のとき、
\({}_n \mathrm{C} _k =\frac{p!}{k!(p-k)!}\)
となるが、
①\({}_n \mathrm{C} _k \)はその定義から整数であること
②\(p\)が素数であること
③\(1 \leq k \leq p-1\)、\(1 \leq p-k \leq p-1\)であること
これと、\(p\)が素数のとき、\(1,2,…,p-1\)が\(p\)と互いに素であることを合わせて考えれば、上式の分子の素数\(p\)は分母によって約分されずに残る。
∴\(1 \leq k \leq p-1\)のとき、\({}_n \mathrm{C} _k\)は\(p\)の倍数である。
ゆえに\(f(n+1)\)も\(p\)の倍数となり、\(n+1\)のときも主張は正しい。
∴（ⅰ）（ⅱ）より、全ての正の整数\(n\)で主張は正しい。（証明おわり）
証明２（整数の有名な定理を用いた証明）
補題
整数の有名な定理：\(n\)と\(p\)が互いに素のとき\(p-1\)個の整数\(n,2n,…,(p-1)n\)を\(p\)で割ったあまりは全て異なる。
（証明）
背理法で証明する。\(p-1\)個の数の中にあまりが等しい組が存在するとし、これらを\(in,jn\)（\(1 \leq i < j \leq p-1\)、\(i,j\)は整数）とすると、\(in \equiv jn (\mathrm{mod}p)\)が成立し、\((j-i)n \equiv 0 (\mathrm{mod}p)\)となるが、
\(p\)が素数であることと、\(n\)と\(p\)が互いに素であること、\(1 \leq j-i \leq p-2 \)であることより、左辺は\(p\)の倍数に成り得ず矛盾する。
∴背理法により、\(p-1\)個の数のあまりは全て異なる。（証明おわり）
さて、\(p\)で割ったあまりは0以上\(p-1\)以下の\(p\)種類あるが、\(p-1\)個の数\(n,2n,…,(p-1)n\)の中に\(p\)で割り切れるものは存在しないため、\(n,2n,…,(p-1)n\)を\(p\)で割ったあまりには、1から\(p-1\)までがそれぞれちょうど一回ずつ登場することになる。
したがって、\(n \cdot 2n \cdot … (p-1)n \equiv (p-1)! (\mathrm{mod} p)\)が成立する。
さらに、\(p\)は素数だから、\(p\)と\((p-1)!\)は互いに素であるから、この両辺を\((p-1)!\)で割ることができ、この結果により、\(n^{p-1} \equiv 1 (\mathrm{mod}p)\)を得る。（証明おわり）
入試問題
では、フェルマーの小定理を使った入試問題を実際に解いていきましょう。
（問題）
（１）\(n\)を正の整数、\(p\)を素数とする. このとき,\(n^p \equiv n (\mathrm {mod} p)\)が成立することを証明せよ.
（２）\(n\)を正の整数、\(p\)を素数とし、\(k\)は\(1 \leq k \leq p-1\)を満たす整数とする. このとき,\(n^p = p^n + k\)を満たす\((n,p,k)\)の組を全て求めよ.
（創作問題）
方針・解説は以下の記事を参照してください。
あとがき
最後まで閲覧していただきありがとうございました。
今後も定期的に更新していきますので、ブックマークやツイッターアカウントのフォローのほうぜひしてみてください！
当サイトについての質問・問い合わせなどは当サイトのフォーラムへコメントまたは自分の個人用のツイッターアカウントにDMをくだされば幸いです。（アカウントは@skrdy0121です。）
最終更新：2020 9/18(Fri.)
