フェルマーの小定理の２通りの証明とは？【京大入試を含む問題３選も解説】

こんにちは、ウチダです。

さて、「フェルマーの小定理」とは以下が成り立つことを指します。

1. $p$ を素数とし、$n$ を $p$ と互いに素な自然数とする。
   このとき、$$n^{p-1}≡1 \pmod{p}$$
2. もしくは、$$n^p≡n \pmod{p}$$

※①を「第 $1$ 形式」、②を「第 $2$ 形式」と呼びます。

「そもそも合同式（mod）ってなに？」という方は、こちらの記事から読み進めることをオススメします。

よって本記事では、フェルマーの小定理の証明 $2$ 通りから、フェルマーの小定理の応用問題 $3$ 選（京大入試問題を含む）まで

• 東北大学理学部数学科卒業
• 実用数学技能検定１級保持
• 高校教員→塾の教室長の経験あり

の僕がわかりやすく解説します。

フェルマーの小定理の２通りの証明とは？【「数学的帰納法」「互いに素」を使います】

まずは、フェルマーの小定理の証明における概要をお伝えしておきます。

• 数学的帰納法を用いる証明
  • 二項定理を使って展開して $p$ の倍数である部分を無視し、そこから帰納的に予想して導く。
• 互いに素を用いた鮮やかな証明
  • 互いに素であるときに成り立つ条件を使い、簡潔かつ鮮やかに導く。

※「 ～ 証明」の部分がリンクになっており、クリックすると証明へジャンプします。

それでは早速解説していきます。

数学的帰納法を用いる証明

【証明】

$(a+b)^p$ について考える。

この数は、二項定理を用いて、

と展開できる。

※以降途切れている数式は横にスクロールできます。(スマホでご覧の方対象。)

ここで、$①$ の式の真ん中部分

$${}_p{C}_{1} \ a^{p-1} \ b+{}_p{C}_{2} \ a^{p-2} \ b^2+…+{}_p{C}_{p-1} \ a \ b^{p-1}$$

のすべての項は、共通因数 $p$ でくくり出すことができるので、$p$ の倍数となる。（※２）

よって、$(a+b)^p≡a^p+b^p \pmod{p}$ が導けた。

この式から、

が言える。

よって、以下帰納的に

であることが予想（※１）できる。

この予想した式に $a_1=a_2=…=a_n=1$ を代入すれば、

となるから、$n^p≡n \pmod{p}$ が導ける。

(証明終了)

フェルマーの小定理の第 $2$ 形式を導くことができました。

これについては合同式の除法に成り立つ性質を理解する必要があります。

詳しくは「合同式（mod）を応用して京大入試問題を解こう【不定方程式の問題も解説】」の記事をご参考ください。

※１．予想が成り立つことを証明しよう

さて、今のところ証明は不完全です。

なぜなら、予想した式が本当に正しいのか証明していないからです。

ではこの予想を、数学的帰納法を用いて証明していきましょう。

【予想※１の証明】

を数学的帰納法（ $n≧2$ ）を使って示していこう。

ⅰ） $n=2$ のとき

$(a_1+a_2)^p≡{a_1}^p+{a_2}^p$ は成り立つことを確認していたのでOK。

ⅱ） $n=k$（ $k≧2$ ）のとき、成り立つと仮定する。

このとき、$n=k+1$ に対して、

よって、$n=k+1$ のときも成り立つ。

したがってⅰ）ⅱ）と数学的帰納法より、$②$ の予想は正しい。

(証明終了)

ちなみに、$n=1$ の場合を除きましたが、$1^p≡1 \pmod{p}$ は自明なのでやらなくて大丈夫です。

証明で用いた予備知識の詳しい解説はこちらから

【数Ｂ】数学的帰納法とは～（準備中）

※２．二項係数 pCk が p の倍数であることの証明

もうひとつ、証明中に用いた

$p$ が素数のとき、${}_p{C}_{k}$ は $p$ の倍数である（ $1≦k≦p-1$ ）

これを示していきましょう！

【※２の証明】

両辺に $k$ をかけて、$k \ {}_p{C}_{k}=p \ {}_{p-1}{C}_{k-1}$

もちろん、${}_{p-1}{C}_{k-1}$ は整数なので、右辺は $p$ × 整数、 $p$ の倍数。

また、$1≦k≦p-1$ より $k$ は $p$ の倍数ではない。

したがって、${}_p{C}_{k}$ は $p$ の倍数である。

(証明終了)

二項係数 ${}_p{C}_{k}$ の押さえておきたい性質 $3$ つは、こちらの記事を参考にしてください。

互いに素を用いた鮮やかな証明

さて、次の証明では以下の補題を用います。

この補題を認めることで、フェルマーの小定理を簡潔に導くことができます。

それでは、補題の証明はあとまわしにして、フェルマーの小定理から示していきます。

【小定理の証明】

$n$，$2n$，$3n$，…，$(p-2)n$，$(p-1)n$ の積を $p$ で割った余りについて考えると、

つまり、$(p-1)!×n^{p-1}≡(p-1)! \pmod{p}$ が成り立つ。

ここで、$(p-1)!$ と $p$ は互いに素なので、両辺を $(p-1)!$ で割ることができる。

したがって、$$n^{p-1}≡1 \pmod{p}$$が成り立つ。

(証明終了)

「余りがすべて異なることから、積を $(p-1)!$ で表せる」という発想が、この証明の面白いところですね。

補題の証明

フェルマーの小定理の証明は完了したので、次に補題を示します。

【補題の証明】

$p$ で割った余りがすべて異なるわけではない、

つまり $p$ で割った余りが等しいものが存在すると仮定する。

すると、$in≡jn \pmod{p}$ を満たすある自然数 $i$，$j$ が存在する。（ $i≠j$ ）

ここで、$n$ と $p$ は互いに素であるので、両辺を $n$ で割っても合同式は成り立つ。

よって、$i≡j \pmod{p}　…③$ となる。

今回、$i$ と $j$ は「 $1$ 以上 $p-1$ 以下」の自然数であるため、$③$ を満たすには $i=j$ が成り立つしかないが、$i≠j$ であるため矛盾する。

したがって背理法より、$p$ で割った余りはすべて異なる。

(証明終了)

関連記事はこちらから

スポンサーリンク

フェルマーの小定理を用いる問題３選

次は、フェルマーの小定理を問題でどう用いるか見ていきましょう。

具体的には

• 余りに関する複雑な問題【 $2$ 問】
• 1995年京大入試問題

の $3$ 問を解説していきます。

余りに関する複雑な問題【２問】

合同式の基本的な性質しか知らないと、複雑になればなるほど解くのが難しくなってきます。

よって、フェルマーの小定理を使って鮮やかに解いていきましょう。

【解答】

(1)　フェルマーの小定理第 $1$ 形式 $n^{p-1}≡1 \pmod{p}$ において、$p=13$ とすると、$$n^{12}≡1 \pmod{13}$$

これを用いて、

※ $25$ も $3$ も $p=13$ と互いに素であるため、フェルマーの小定理が使える。

したがって、求める余りは $2$ である。

(2)　フェルマーの小定理第 $2$ 形式 $n^{p}≡n \pmod{p}$ において、$p=11$ とすると、$$n^{11}≡n \pmod{11}$$

これを用いて、

$$a^{22}=(a^2)^{11}≡a^2 \pmod{11}$$

今回 $a^{22}≡4 \pmod{11}$ なので、$a^2≡4 \pmod{11}$

つまり、$a^2-4=(a+2)(a-2)≡0 \pmod{11}$ が導ける。

この式は、「 $a+2$ または $a-2$ が $11$ の倍数」だということを意味する。

したがって、$10$ 以下の自然数 $a$ でこの条件を満たすものは

$$a=2 \ , \ 9$$

(解答終了)

一つ注意点としてお伝えしておきますが、$n$ と $p$ が互いに素であることをよく確認してから、フェルマーの小定理を使うようにしましょうね＾＾

1995年京大入試問題

さあ、ラストは $1995$年度の京大入試問題です。

(2)のオリジナリティがいかにも京大っぽいですね～。

それでは解答に移ります。

【解答】

(1)　$p=7$ は素数であるから、7の倍数以外のすべての自然数 $n$ と互いに素である。

ここで、フェルマーの小定理第 $2$ 形式 $n^{p}≡n \pmod{p}$ において、$p=7$ を代入すると、$$n^7≡n \pmod{7}$$

を導けた。

この式は $f(n^7)=f(n)$ そのものを意味している。

また $n=7k$( $k$ は自然数)のとき、$f(n^7)=7・(7^6k^7)$ , $f(n)=7k$ より $7$ で割ったあまりは0である、

したがって $f(n^7)=f(n)$

(2)　たとえば $g(n)$ に $n=7$ を代入すると、(1)より

と式変形できるので、$n=1 \ , \ 2 \ , \ 3 \ , \ 4 \ , \ 5 \ , \ 6$ の $6$ パターンのみ調べればよいことに気づく。

ⅰ）$n=1$ のとき

ⅱ）$n=2$ のとき

$n=3$ あたりから計算が大変になってくるため、合同式の性質

• $f(7^m)=0$
• $f(6^m)=f((-1)^m)$
• $f(5^m)=f((-2)^m)$
• $f(4^m)=f((-3)^m)$

をしっかり活用し、工夫して計算していこう。

ⅲ）$n=3$ のとき

ⅳ）$n=4$ のとき

ⅴ）$n=5$ のとき

ⅵ）$n=6$ のとき

…僕の好きな自然数は $n=6$ なので、$g(6)=18$，つまり $18$ 点ください！

(解答終了)

(1)(2)から一般的に $g(n)$ を求めると、

$$g(n)=\left\{\begin{array}{ll}0 \ ( \ n≠6+7k \ )\\18 \ ( \ n=6+7k \ )\end{array}\right.$$

なので、

• $n=6$，$13$，$20$，…を選べば $18$ 点GET。
• それ以外を選べば $0$ 点。

という、非常に恐ろしいかつユニークな問題でした。。

フェルマーの小定理の応用例「RSA暗号」の記事はこちらから

本記事のポイントをまとめます。

1. 証明方法は $2$ 通り。「数学的帰納法」もしくは「互いに素」を利用して導こう！
2. フェルマーの小定理を用いることで、計算がかなりラクになります。
3. 京大さんは本当にいい問題を作ります。

京大さんの入試問題も素晴らしいですが、もっと素晴らしい応用例が「RSA暗号」と呼ばれる、現代のネット社会を支える暗号です。

もし興味のある方は、「RSA暗号の仕組みとは？【作り方や解き方・安全性までわかりやすく解説します】」の記事で解説してますので、こちらもあわせてご覧ください♪

「整数の性質」全 25 記事をまとめました。こちらから次の記事をCHECK!!

終わりです。