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

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

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

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

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

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

あわせて読みたい
合同式の基本的な使い方3選とは【まずは練習問題でmodに慣れよう】
合同式の基本的な使い方3選とは【まずは練習問題でmodに慣れよう】合同式(mod)の意味が分からない?本記事では、合同式(mod)の基本的な部分についてまとめました。具体的には、「modとは何か」「合同式に成り立つ性質5つ」「余りを求める問題」「一の位の数を求める問題」「倍数であることの証明問題」を解説します。

う~ん…これだけ見ても、どうしてフェルマーの小定理が成り立つのかわからないなぁ。

数学花子のアイコン画像数学花子

フェルマーの小定理は、問題でどのように使えばいいんでしょうか?

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

  • 東北大学理学部数学科卒業
  • 教員採用試験に1発合格 → 高校教諭経験アリ

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

スポンサーリンク
スポンサーリンク
目次

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

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

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

ウチダのアイコン画像ウチダ

必要な予備知識が少ないのは $2$ つ目の方法ですが、発想力を必要としないのは $1$ つ目の方法です。どちらも善し悪しがありますね。

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

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

【証明】

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

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

\begin{align}(a+b)^p=a^p+{}_p{C}_{1} \ a^{p-1} \ b+{}_p{C}_{2} \ a^{p-2} \ b^2+…+{}_p{C}_{p-1} \ a \ b^{p-1}+b^p ……①\end{align}

と展開できる。

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

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

$${}_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}$ が導けた。

この式から、

\begin{align}(a+b+c)^p&≡(a+b)^p+c^p\\&≡a^p+b^p+c^p \pmod{p}\end{align}
が言える。

よって、以下帰納的に

\begin{align}(a_1+a_2+…+a_n)^p≡{a_1}^p+{a_2}^p+…+{a_n}^p \pmod{p}\end{align}

であることが予想(※1)できる。

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

\begin{align}(1+1+…+1)^p≡1^p+1^p+…+1^p \pmod{p}\end{align}

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

(証明終了)

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

数学太郎のアイコン画像数学太郎

そういえば、第 $1$ 形式と第 $2$ 形式って、何が違うの?

ウチダのアイコン画像ウチダ

違いはありませんよ。同値な条件です。ただ、「 $n$ と $p$ が互いに素」であることには注意してください。

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

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

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

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

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

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

【予想※1の証明】

\begin{align}(a_1+a_2+…+a_n)^p≡{a_1}^p+{a_2}^p+…+{a_n}^p \pmod{p} …②\end{align}

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

ⅰ) $n=2$ のとき

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

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

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

\begin{align}(a_1+a_2+…+a_k+a_{k+1})^p&=\{(a_1+a_2+…+a_k)+a_{k+1}\}^p\\&≡(a_1+a_2+…+a_k)^p+{a_{k+1}}^p\\&≡{a_1}^p+{a_2}^p+…+{a_n}^p+{a_{k+1}}^p \pmod{p}\end{align}

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

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

(証明終了)

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

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

  • 【数Ⅱ】二項定理とは~(準備中)
  • 【数B】数学的帰納法とは~(準備中)

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

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

【互いに素のとき成り立つ補題】
$n$ と $p$ が互いに素であるとき、$n$,$2n$,$3n$,…,$(p-2)n$,$(p-1)n$ を $p$ で割った余りは、すべて異なる。

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

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

【小定理の証明】

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

\begin{align}n×2n×3n×…×(p-2)n×(p-1)n&=1×2×3×…×(p-2)×(p-1)×n^{p-1}\\&≡1×2×3×…×(p-2)×(p-1) \pmod{p}\end{align}

つまり、$(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$ で割った余りはすべて異なる。

(証明終了)

関連記事はこちらから

スポンサーリンク

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

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

具体的には

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

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

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

問題. 次の問いに答えよ。
(1) $5^{24}+3^{12}$ を $13$ で割ったときの余りを求めなさい。
(2) $a$ は $10$ 以下の自然数で、$a^{22}$ を $11$ で割った余りが $4$ であるとき、$a$ の値を求めなさい。

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

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

【解答】

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

これを用いて、

\begin{align}5^{24}+3^{12}&=25^{12}+3^{12}\\&≡1+1\\&=2 \pmod{13}\end{align}

※ $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年京大入試問題

問題. 自然数 $n$ に対して、$f(n)= \ n \ を \ 7 \ で割った余り$,
$\displaystyle g(n)=3f(\sum_{k=1}^{7}k^n)$ と定義する。
(1) すべての自然数 $n$ に対して $f(n^7)=f(n)$ を示しなさい。
(2) あなたの好きな自然数 $n$ を一つ決めて $g(n)$ を求めなさい。その $g(n)$ の値をこの設問(2)におけるあなたの得点とする。
※1995年度 京都大学後期文系入試問題

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

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

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

【解答】

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

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

を導けた。

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

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

\begin{align}g(7)&=3f(\sum_{k=1}^{7}k^7)\\&=3×f(1^7+2^7+…+6^7+7^7)\\&=3×f(1+2+…+6+7)\\&=g(1)\end{align}

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

ⅰ)$n=1$ のとき

\begin{align}g(1)&=3f(1+2+3+4+5+6+7)\\&=3f(28)\\&=0\end{align}

ⅱ)$n=2$ のとき

\begin{align}g(2)&=3f(1+4+9+16+25+36+49)\\&=3f(140)\\&=0\end{align}

$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$ のとき

\begin{align}g(3)&=3f(1+8+27+(-27)+(-8)+(-1)+7^3)\\&=3f(0)\\&=0\end{align}

ⅳ)$n=4$ のとき

\begin{align}g(4)&=3f(1+16+81+81+16+1+7^4)\\&=3f(196)\\&=0\end{align}

ⅴ)$n=5$ のとき

\begin{align}g(5)&=3f(1+2^5+3^5+(-3)^5+(-2)^5+(-1)^5+7^5)\\&=3f(0)\\&=0\end{align}

ⅵ)$n=6$ のとき

\begin{align}g(6)&=3f(1+2^6+3^6+(-3)^6+(-2)^6+(-1)^6+7^6)\\&=3f(2×(1+64+729))\\&=3f(1588)\\&=3×6\\&=18\end{align}

…僕の好きな自然数は $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暗号がなかったら、You〇ubeだけでなくあらゆるネットサービスが機能停止します!!

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

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

あわせて読みたい
整数の性質とは?【高校数学Aの解説記事総まとめ25選】
整数の性質とは?【高校数学Aの解説記事総まとめ25選】「整数の性質」の総まとめ記事です。本記事では、整数の性質の解説記事全25個をまとめています。「整数の性質をしっかりマスターしたい」「整数の性質を自分のものにしたい」という方は必見です。

終わりです。

遊ぶ数学公式LINEやってます!

遊ぶ数学管理人「ウチダショウマ」に数学を直接教わることができるオンライン家庭教師サービス”Play MATH”を開始しました。

その他にも

・ウチダショウマとお話がしたい
・勉強に関する悩みを相談したい

などでもOKですので、ぜひ気軽にご連絡ください。

↓友達追加はこちらから↓

友だち追加

スポンサーリンク

コメント

コメントする

目次
閉じる