2014/04/24

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

分野: 整数問題  レベル: 数学オリンピック

フェルマーの小定理:
$p$ が素数,$a$ が任意の自然数のとき
$a^{p}\equiv a \:\mathrm{mod}\:p$
特に,$a$ が $p$ と互いに素な自然数のとき
$a^{p-1}\equiv 1\:\mathrm{mod}\:p$


$a\equiv b\:\mathrm{mod}\:n$ とは $a$ と $b$ を $n$ で割った余りが等しいという意味の記号です。(合同式と言います)
→合同式の意味とよく使う6つの性質
以下このページでは全て $\:\mathrm{mod}\:p$ なので $\:\mathrm{mod}\:p$ を省略します。

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

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

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

方針:$a$ に関する数学的帰納法を用いて $a^p\equiv a\:\mathrm{mod}\:p$ を証明します。 $a$ と $p$ が互いに素なときは合同式の両辺を $a$ で割ることができるのでフェルマーの小定理が導かれます。

証明

$a=1$ のとき,明らかに $a^p\equiv a$
また,二項定理を用いることで,
$(m+1)^p=m^p+1+\displaystyle\sum_{k=1}^{p-1}{}_pC_{k}m^k\equiv m^p+1$
(ただし,$p$ が素数で $1\leq k\leq {p-1}$ のとき${}_pC_{k}=p\dfrac{(p-1)\cdots(p-k+1)}{k!}$ が $p$ の倍数であることを用いた。)
よって,$m^p \equiv m$ なら,$(m+1)^p\equiv m+1$
以上から数学的帰納法より,全ての $a$ に対して $a^p\equiv a$
よって,$p$ と $a$ が互いに素なとき両辺を $a$ で割ってフェルマーの小定理を得る。

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

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

証明

方針で述べたことと,$a,2a,3a,\cdots(p-1)a$ は全て $p$ の倍数でないので,
$a,2a,3a\cdots (p-1)a$ を $p$ で割った余りを並べると $1$ から $p-1$ までが全て1回ずつ登場する。よって,
$a\cdot 2a\cdot 3a\cdot\cdots\cdot (p-1)a\equiv (p-1)!$
ここで,$(p-1)!$ は $p$ と互いに素なので両辺を$(p-1)!$ で割って,
$a^{p-1}\equiv 1$ を得る。

数オリの問題に挑戦

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

問題

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

方針:素数 $p,q$ が $a_n$ と互いに素なら $pq$ も $a_n$ と互いに素になります。逆も然り。つまり素数の場合だけ考えればよいのです。(第一関門)
問題の流れから「数列の全ての項と互いに素」という強い条件を満たす数は少ないと予想できます。よって,「ある例外を除いて素数 $p$ は数列${a_n}$ のどこかの項の約数になっている」ことを証明すればよいわけです。(第二関門)
$a^n$ を $p$ で割った余りを評価するときにはフェルマーの小定理が活躍します。そこで,$a_p\equiv 0$ を示そうと思いますが,うまくいきません。右辺が $0$ になるように色々試すと $a_{p-2}$ でうまくいくことが分かります。(第三関門)

解答

$p\geq 4$ のとき,
$a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv 0 \:\mathrm{mod}\:p$ を示す。
$p$ と $6$ は互いに素なので,両辺を $6$ 倍した以下の式を示せば良い:
$3\cdot 2^{p-1}+2\cdot 3^{p-1}+6^{p-1}-6\equiv 0$
ところが,これはフェルマーの小定理より成立する。

よって,候補は $1,2,3$ のみ。 $2$ は $a_1=10$ の約数で,$3$ は $a_2=48$ の約数なので不適。答えは $1$ のみ。


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

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

Tag: 不定方程式の解き方まとめ
Tag: 国際数学オリンピックの過去問
Tag: 素数にまつわる覚えておくべき性質まとめ
数学オリンピック対策の公式まとめ

分野: 整数問題  レベル: 数学オリンピック