1. 高校数学の美しい物語
  2. フェルマーの小定理の証明と例題

フェルマーの小定理の証明と例題

更新日時 2021/03/07
フェルマーの小定理
  • pp が素数,aa が任意の自然数のとき
    apa(modp)a^p\equiv a\pmod{p}

  • 特に pp が素数で,aapp と互いに素な自然数のとき
    ap11(modp)a^{p-1}\equiv 1\pmod{p}

ab(modn)a\equiv b\pmod{n} とは aabbnn で割った余りが等しいという意味の記号です。合同式と言います。 →合同式の意味とよく使う6つの性質

以下このページでは全てmodp\bmod{p} なのでmodp\bmod{p} を省略します。

フェルマーの小定理は,数学オリンピックの整数論分野で頻出の定理です。定理の前提条件も重要なので,「pp が素数,aapp と互いに素な整数のとき」というのはしっかり覚えておきましょう。

このページではフェルマーの小定理の2通りの証明と,その応用例として国際数学オリンピック2005年(メキシコ大会)の過去問を扱います。

目次
  • 1:数学的帰納法による証明

  • 2:整数の有名な性質を利用したエレガントな証明

  • 数オリの問題に挑戦

1:数学的帰納法による証明

方針

aa に関する数学的帰納法を用いて apa(modp)a^p\equiv a \pmod{p} を証明します。aapp が互いに素なときは合同式の両辺を aa で割ることができることを使います。

証明

a=1a=1 のとき,明らかに apaa^p\equiv a

また,二項定理を用いることで,

(m+1)p=mp+1+k=1p1pCkmkmp+1(m+1)^p=m^p+1+\displaystyle\sum_{k=1}^{p-1}{}_p\mathrm{C}_{k}m^k\equiv m^p+1

(ただし,pp が素数で 1kp11\leq k\leq {p-1} のとき pCk=p(p1)(pk+1)k!{}_p\mathrm{C}_{k}=p\dfrac{(p-1)\cdots(p-k+1)}{k!}pp の倍数であることを用いた。)

よって,mpmm^p \equiv m なら,(m+1)pm+1(m+1)^p\equiv m+1

以上から数学的帰納法より,全ての aa に対して apaa^p\equiv a

よって,ppaa が互いに素なとき両辺を aa で割ってフェルマーの小定理を得る。

2:整数の有名な性質を利用したエレガントな証明

方針

整数の有名な定理「aapp が互いに素なとき,a,2a,3a,(p1)aa,2a,3a,\cdots (p-1)app で割った余りはすべて異なる」を用います。この定理を知らない人は,一次不定方程式ax+by=cの整数解の中央当たりに2行ほどで証明しているので参考にしてください。

証明

方針で述べたことと,a,2a,3a,(p1)aa,2a,3a,\cdots(p-1)a は全て pp の倍数でないので,

a,2a,3a(p1)aa,2a,3a\cdots (p-1)app で割った余りを並べると 11 から p1p-1 までが全て1回ずつ登場する。よって,

a2a3a(p1)a(p1)!a\cdot 2a\cdot 3a\cdot\cdots\cdot (p-1)a\equiv (p-1)!

ここで,(p1)!(p-1)!pp と互いに素なので両辺を (p1)!(p-1)! で割って,

ap11a^{p-1}\equiv 1 を得る。

数オリの問題に挑戦

国際数学オリンピックメキシコ大会の第4問です。

問題

「数列 an=2n+3n+6n1a_n=2^n+3^n+6^n-1 の全ての項と互いに素」な自然数を全て求めよ。

方針

素数 p,qp,qana_n と互いに素なら pqpqana_n と互いに素になります。逆も然り。つまり素数の場合だけ考えればよいのです(第一関門)。

問題の流れから「数列の全ての項と互いに素」という強い条件を満たす数は少ないと予想できます。よって,「ある例外を除いて素数 pp は数列 an{a_n} のどこかの項の約数になっている」ことを証明すればよいわけです(第二関門)。

ana^npp で割った余りを評価するときにはフェルマーの小定理が活躍します。そこで,ap0a_p\equiv 0 を示そうと思いますが,うまくいきません。右辺が 00 になるように色々試すと ap2a_{p-2} でうまくいくことが分かります(第三関門)。

解答

p4p\geq 4 のとき,

ap2=2p2+3p2+6p210(modp)a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv 0 \pmod{p} を示す。

pp66 は互いに素なので,両辺を 66 倍した以下の式を示せば良い:

32p1+23p1+6p1603\cdot 2^{p-1}+2\cdot 3^{p-1}+6^{p-1}-6\equiv 0

ところが,これはフェルマーの小定理より成立する。

よって,候補は 1,2,31,2,3 のみ。 22a1=10a_1=10 の約数で,33a2=48a_2=48 の約数なので不適。答えは 11 のみ。

数学オリンピック対策をしっかりしていれば第二関門までは行きたいところです。

フェルマーの最終定理と区別するために「小」定理という名前がついてしまったかわいそうな定理です。

Tag:不定方程式の解き方まとめ

Tag:国際数学オリンピックの過去問

Tag:素数にまつわる覚えておくべき性質まとめ数学オリンピック対策の公式まとめ

人気記事
  1. 高校数学の美しい物語
  2. フェルマーの小定理の証明と例題