基本事項解説 大学受験 数学

【保存版】高校数学 フェルマーの小定理 証明

目次

  1. 主張
  2. 証明
  3. 入試問題
  4. あとがき

主張

フェルマーの小定理:\(n\)を正の整数、\(p\)を素数とするとき、\(\mathrm {mod} p\)のもとで以下の関係式が成立する。
\(n^p \equiv n (\mathrm {mod} p)\)

特に、\(n\)と\(p\)が互いに素のとき、この両辺を\(n\)で割ることにより以下の関係式が成立する。
\(n^{p-1} \equiv 1 (\mathrm {mod} p)\)

以下では汎用性の高い証明方法を2つ説明し、関連した自作問題(分野:整数)も紹介しておきます。

では、ぜひ最後までご覧になってください。

証明

方針

\(n\)を正の整数とする」という文言がありますが、これは暗に、「すべての正の整数\(n\)について証明せよ」と言っています。ですので、まず思い付く解法としては数学的帰納法でしょう。また、この手法以外でも証明2に提示されているような整数の有名な定理を用いた証明もあります。この定理は証明の流れも合わせて知っておくと、他の入試問題にも適用することができ、便利でしょう。余裕のある方は証明2も読んでみてください。

証明1の途中で2項係数に関する有名な性質:\(p\)が素数、\(1 \leq k \leq p-1\)のとき、\({}_n \mathrm{C} _k\)は\(p\)の倍数である
ことを使います。この性質は大学入試でも頻出です。記述式答案では自力で証明できるように練習しておきましょう。(記述量はそんなに多くなくて楽ですよ。)

証明1(数学的帰納法を用いた証明)

証明するべきことは、\(f(n)=n^p - n\)が\(p\)の倍数であることと同値である。(∵\(\mathrm {mod}\)の性質)
(ⅰ)\(n=1\)のとき
\(f(1)=1^p -1 =0 \equiv 0 (\mathrm{mod}p)\)より主張は正しい。

(ⅱ)ある正の整数\(n\)で題意の主張が成立するとき
2項定理によって\({(n+1)}^p\)を展開することにより、

\begin{align}
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\)で主張は正しい。(証明おわり)

証明2(整数の有名な定理を用いた証明)

補題

整数の有名な定理:\(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)\)を得る。(証明おわり)

入試問題

では、フェルマーの小定理を使った入試問題を実際に解いていきましょう。

(問題)
(1)\(n\)を正の整数、\(p\)を素数とする. このとき,\(n^p \equiv n (\mathrm {mod} p)\)が成立することを証明せよ.
(2)\(n\)を正の整数、\(p\)を素数とし、\(k\)は\(1 \leq k \leq p-1\)を満たす整数とする. このとき,\(n^p = p^n + k\)を満たす\((n,p,k)\)の組を全て求めよ.
(創作問題)

方針・解説は以下の記事を参照してください。

あとがき

最後まで閲覧していただきありがとうございました。

今後も定期的に更新していきますので、ブックマークやツイッターアカウントのフォローのほうぜひしてみてください!

当サイトについての質問・問い合わせなどは当サイトのフォーラムへコメントまたは自分の個人用のツイッターアカウントにDMをくだされば幸いです。(アカウントは@skrdy0121です。)

最終更新:2020 9/18(Fri.)

  • この記事を書いた人
  • 最新記事

Yuya Sakurada

洛北(中高一貫)→京都大学理学部2回生|元駿台特待, EX生|予備校勤務 |個別指導講師(英数物)|高3時, 京大模試英語で全国15位以内を1年間で7回達成|ポケモン全国3位(2013), 全国Top8(2017), 全国Top4(2018)|大学受験英語・数学や大学の学問紹介の記事を中心に書いています。

-基本事項解説, 大学受験, 数学
-, ,

Copyright © 2020-2021 Sacramy