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

更新日時 2021/03/07
フェルマーの小定理

pp が素数で,aapp の倍数でない正の整数のとき ap11(modp)a^{p-1}\equiv 1\pmod{p}

目次
  • フェルマーの小定理の意味と例

  • フェルマーの小定理の証明

  • フェルマーの小定理の応用例

  • フェルマーの小定理を使う問題

フェルマーの小定理の意味と例

ab(modp)a\equiv b\pmod{p} とは「aabbpp で割った余りが等しい」という意味です。 →合同式の意味とよく使う6つの性質

フェルマーの小定理の例

p=5p=5a=1,2,3,4a=1,2,3,4 の場合を見てみます。ap1a^{p-1} を計算すると,

  • 14=11^4=1
  • 24=162^4=16
  • 34=813^4=81
  • 44=2564^4=256

なので,a4a^455 で割った余りは 11 です。つまり,a41(mod5)a^4\equiv 1\pmod 5 となりフェルマーの小定理が成立しています。

フェルマーの小定理の証明

2通りの証明を紹介します。 以下,このページでは全てmodp\bmod{p} なのでmodp\bmod{p} を省略します。

数学的帰納法による証明

方針

aa に関する数学的帰納法を用いて証明します。「aapp が互いに素なときは合同式の両辺を aa で割ることができる」を使います。

証明

任意の正の整数 aa に対して apaa^p\equiv a であることを示す (そうすれば,ppaa が互いに素なとき両辺を 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

(→補足)

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

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

補足:途中の式変形で pp が素数で 1kp11\leq k\leq {p-1} のとき pCk{}_p\mathrm{C}_{k}pp の倍数という性質を用いました。 これは有名な性質です。 詳細は二項係数の有名公式一覧と2つの証明方針

なお,上記で示した以下の主張をフェルマーの小定理として覚えてもよいでしょう:
素数 pp と全ての正の整数 aa に対して apaa^p\equiv a が成立する。

整数の有名な性質を利用した美しい証明

方針

有名な定理「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 を得る。

フェルマーの小定理の応用例

フェルマーの小定理を応用すると,以下の定理を証明できます。

定理

2255 以外の任意の素数 pp について,pp の倍数となるような 「すべてのケタが1である整数(11111\cdots 1)」 が存在する。

詳細は →レプユニット数

フェルマーの小定理は他にも

フェルマーの小定理を使う問題

フェルマーの小定理は,数学オリンピックの整数分野で頻出の定理です。以下は2005年国際数学オリンピックメキシコ大会の第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:素数にまつわる覚えておくべき性質まとめ