入試数学演習 大学受験 数学

【入試数学演習No.2】整数 フェルマーの小定理

目次

  1. 問題
  2. 方針
  3. 解答
  4. あとがき

問題

(問題)
(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)\)の組を全て求めよ.
(創作問題)

方針

(1)「フェルマーの小定理」そのものです。フェルマーの小定理について詳しく知りたい方は以下の記事を参照してください。

(2)整数問題の基本方針は以下の3つです。

整数問題の基本方針3つ

約数倍数に注目する(因数分解を伴うことが多い)

あまりに注目する(\(\mathrm{mod}2,3,4,5,7\)あたりを考えたり、素数が絡んだりすることが多い)

③とりうる範囲に注目する(分数型の不定方程式や関数の発散スピード

※整数問題のより詳しい解き方に関する記事は後々、「高校数学解法集」として寄稿いたしますので、少々お待ちください。

→本問では

まず文字がやたら多いので①の因数分解可能性を考えてみましょう。\(p\)が素数であることや\(k\)の範囲を利用したいので、\(p^n,k=\)(積の形)に変形することを目指すことになるのですが、前者だと\(p^n =n^p -k\)となって、後者だと\(k=n^p - p^n\)となって(前者はもちろんのこと)因数分解ができない形になっています。(\(n,p\)の偶奇性を考えれば後者も可能性はありますが、②の考え方も必要になってきて現実的ではありません。)

次に②を考えてみますが、両辺の\(\mathrm{mod}p\)を考えてみると、\(n^p \equiv k (\mathrm{mod}p)\)となります。さらに(1)の事実から、\(n^p \equiv n (\mathrm {mod} p)\)が成立するため、\(n \equiv k (\mathrm {mod} p)\)が成立することが分かりました。(1)の誘導から情報を得ることができましたね。

最後に③を考えてみますが、\(k\)に他の文字よりも明確な範囲が定められていることに注目してみましょう。\(k=n^p - p^n\)が\(1 \leq k \leq p-1\)の範囲にあるわけですが、\(n,p\)の2文字が同時に広い範囲を動いてしまいますので、とりあえず片方の文字を固定してしまいましょう。\(p\)が動くと\(k\)の定義域も変化してしまうので、2文字のうちで固定しようとするならば、\(p\)のほうがようでしょう。すると、\(1 \leq n^p - p^n \leq p-1\)が成立するわけですが、\(f(n)=n^p - p^n\)とおくと、これは(多項式関数)-(指数関数)の形をしています。\(n\)を大きくしていくと、指数関数のほうが多項式関数よりも圧倒的に速いスピードで増加していきますので、\(f(n)\)は十分大きな\(n\)では負になってしまい、\(1 \leq f(n) \leq p-1\)となりえないだろう、と予想がつきます。(このように、整数問題ではまず文字の範囲に大体の見当をつけ、必要条件として範囲を絞った後、残りの細かいところを丁寧に詰めいくことはよくあります。)
ですので、\(f(n)\)の増減を調べていけばいいことになります。\(f(n)\)は正の整数のみで定義されている離散関数なので、以下の3つの手法から選択して解答を進めていくことになります。

離散関数の扱い方

以下、正の整数\(n\)についての離散関数を\(a_n\)とする。

\(a_{n+1}-a_n\)の符号を調べる

\(\frac{a_{n+1}}{a_n}-1\)の符号を調べる(ただし、常に\(a_n > 0\)のとき)

→差を取るか比を取るかは\(a_n\)の形に応じて適宜使い分けましょう。(2項係数や階乗が登場するときはこの手法しかありません。)

③\(a_n\)を正の数全体で定義される連続関数に拡張して\(a_n\)を\(n\)で微分する

→数Ⅲ既習の方は困ったら、微分できそうな関数ならば③の手法を取ればよいでしょう。(いわゆる「ゴリ押し」戦法です。)

→本問では

①、②の手法はとても使えそうにありませんので、\(f(n)=n^p - p^n\)を直接微分することになります。
あるいは、エレガントに解くのであれば、\(f(n)\)は十分大きな\(n\)では負になってしまうことに注目し、いったん\(1 \leq f(n) \leq p-1\)を\(f(n) > 0\)として必要条件を考えてみると、\(n^p - p^n > 0\)となります。
この形の不等式を見たことがある方も多いのでしょう。(例えば「\(\pi^eとe^\pi\)の大小を比較せよ」という旨の問題です)
変数が両辺に散らばっているのことに加え、指数部分に変数があるので、両辺が正であることを確認してから自然対数を取るのがよいでしょう。
自然対数を取った後、変数を片方の辺に寄せてやると、
\(\frac{\log{}n}{n} > \frac{\log{}p}{p}\)
となるので、関数\(\frac{log{}x}{x}\)の増減を考察することに帰着します。(具体的な数値から抽象的な関数を想起することがポイント)

また本題からは逸れますが、このグラフは入試でも頻出ですので、必ず抑えておきましょう。このグラフに関連した\(\frac{log{}x}{x}\)の極限については、「有名極限」シリーズで述べていこうと思います。

解答

(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)両辺の\(\mathrm{mod}p\)を考えると、\(n^p \equiv k (\mathrm{mod}p)\)となり、さらに(1)の事実から、\(n^p \equiv n (\mathrm {mod} p)\)が成立するため、\(n \equiv k (\mathrm {mod} p) \tag1\)が成立する。
ここで、\(k > 0\)が必要条件であるから、\(n^p - p^n > 0\)となり、この両辺は正であるから自然対数をとって整理すると、
\(\frac{\log{}n}{n} > \frac{\log{}p}{p} \tag2\)となる。
さらに、\(f(x)=\frac{log{}x}{x}\)とおくと、\(f'(x)=\frac{1-log{}x}{x^2}\)となるが、分母は常に正だから分子の符号にのみ注目すればよい。
\(f'(x)=0\)となるのは\(x=e\)のときであり、その前後で\(f'(x)\)の符号は正から負に転じるから、\(f(x)\)は増加から減少に転じる。
\(\displaystyle \lim_{x \to +0} f(x)=-\infty\)、\(\displaystyle \lim_{x \to \infty} f(x)=0\)であるから、\(y=f(x)\)のグラフは以下のようになる。

グラフから分かるように、\(x\)が正の整数のときの\(f(x)\)の値を調べていくと、\(2 \leq e \leq 3\)であるから、
\(f(1)=0,f(2)=f(4),f(3) > f(4) > f(5) >…\tag3\)が成立する。

(ⅰ)\(p \geq 5\)のとき
(2)より、\(f(n) > f(p)\)だから、(3)により、\(n < p\)を得るが、(1)により、\(1 \leq k \leq p-1\)であることと合わせて、\(n=k\)が成立する。
これをもとの式に代入すると、\(k^p =p^k + k\)となるが、\(k \geq 2\)のときは、両辺の\(\mathrm{mod}k\)を考えると、\(p^k \equiv 0 (\mathrm{mod}k)\)となるが、\(p\)と\(k\)は互いに素である(∵\(p\)は素数かつ\(1 \leq k \leq p-1\))ことにより、これは矛盾。したがって、解はない。
また、\(k=1\)のときは、\(1=p+1\)となり\(p=0\)となるが、\(p\)が素数であることと矛盾する。したがって、この場合も買いはない。

(ⅱ)\(p=3\)のとき
\(f(3)\)よりも大きな\(f(l)\)(lは正の整数)は存在しないため、(2)より解はない。

(ⅲ)\(p=2\)のとき
\(f(2)\)よりも大きな\(f(l)\)(lは正の整数)は\(l=3\)に限られるため、(2)より\(n=3\)となる。これらをもとの式に代入すると、\(k=1\)を得る。(たしかに\(1 \leq k \leq p-1\)の範囲に収まっている。)

以上より求める解は\((n,p,k)=(3,2,1)\)のみである。 (答え)

あとがき

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

今回の入試問題解説のほう、いかがだったでしょうか。

数学では入試問題1問から学ぶべきことが多くあると思います。復習して解法をどんどんと溜めていきましょう!

解説の感想のほど、SNSでシェアあるいはDMにて気軽にお聞かせください!今後の当サイト改善に役立てます。

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

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

最終更新:2020 9/21(Mon.)

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

Yuya Sakurada

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

-入試数学演習, 大学受験, 数学
-, , ,

Copyright © 2020-2021 Sacramy