トップ› 基礎問題› 数学A› 整数問題› フェルマーの小定理› 問題 4

数学A フェルマーの小定理問題 4 解説

方針・初手

$d_m$ は二項係数

$$ {}_mC_1,\ {}_mC_2,\ \ldots,\ {}*mC*{m-1} $$

のすべてを割り切る最大公約数である。したがって、まず $d_m$ が各二項係数を割り切ることを、二項展開の中で利用する。

特に

$$ (k+1)^m-(k+1) $$

を展開すると、途中に現れる係数がすべて ${}_mC_r$ になるので、帰納法と相性がよい。

解法1

(1)

$m$ が素数であるとする。

$1 \leq r \leq m-1$ に対して、

$$ {}_mC_r=\frac{m!}{r!(m-r)!} $$

である。

$m$ は素数であり、$r<m,\ m-r<m$ だから、$r!$ と $(m-r)!$ はいずれも $m$ を素因数にもたない。一方、分子 $m!$ は $m$ を素因数にもつ。

したがって、各 $r=1,2,\ldots,m-1$ について

$$ m \mid {}_mC_r $$

が成り立つ。

よって、$d_m$ は少なくとも $m$ の倍数である。

一方、

$$ {}_mC_1=m $$

であるから、すべての二項係数の最大公約数である $d_m$ は $m$ を割り切る。

以上より、

$$ d_m=m $$

である。

(2)

すべての自然数 $k$ に対して

$$ d_m \mid k^m-k $$

を示す。$k$ に関する数学的帰納法を用いる。

まず $k=1$ のとき、

$$ 1^m-1=0 $$

であるから、$d_m$ で割り切れる。

次に、ある自然数 $k$ について

$$ d_m \mid k^m-k $$

が成り立つと仮定する。

このとき、二項定理より

$$ \begin{aligned} (k+1)^m &= k^m+{}_mC_1k^{m-1}+{}_mC_2k^{m-2}+\cdots+{}*mC*{m-1}k+1 \end{aligned} $$

である。したがって、

$$ \begin{aligned} (k+1)^m-(k+1) &=k^m-k+{}_mC_1k^{m-1}+{}_mC_2k^{m-2}+\cdots+{}*mC*{m-1}k \end{aligned} $$

となる。

帰納法の仮定より、$k^m-k$ は $d_m$ で割り切れる。また、$d_m$ は ${}_mC_1,{}_mC_2,\ldots,{}*mC*{m-1}$ の最大公約数であるから、各二項係数 ${}_mC_r$ は $d_m$ で割り切れる。

したがって、右辺のすべての項は $d_m$ で割り切れる。よって、

$$ d_m \mid (k+1)^m-(k+1) $$

が成り立つ。

以上より、数学的帰納法によって、すべての自然数 $k$ に対して

$$ d_m \mid k^m-k $$

が示された。

(3)

$m$ が偶数であるとする。

まず、$d_m$ が奇素因数をもたないことを示す。奇素数 $p$ が $d_m$ を割り切ると仮定する。

（2）より、すべての自然数 $k$ について

$$ d_m \mid k^m-k $$

であるから、特に

$$ p \mid k^m-k $$

がすべての自然数 $k$ について成り立つ。

ここで $k=p-1$ とおくと、

$$ p \mid (p-1)^m-(p-1) $$

でなければならない。

ところが、法 $p$ で考えると、$p-1 \equiv -1$ より、$m$ が偶数であることから

$$ (p-1)^m-(p-1)\equiv (-1)^m-(-1)=1+1=2 \pmod p $$

となる。

$p$ は奇素数だから、$2 \not\equiv 0 \pmod p$ である。これは矛盾である。

したがって、$d_m$ は奇素因数をもたない。

次に、$4$ が $d_m$ を割り切らないことを示す。もし $4\mid d_m$ なら、（2）より $k=2$ として

$$ 4\mid 2^m-2 $$

でなければならない。

しかし、

$$ 2^m-2=2(2^{m-1}-1) $$

であり、$m\geq 2$ だから $2^{m-1}$ は偶数、したがって $2^{m-1}-1$ は奇数である。よって $2^m-2$ は $2$ では割り切れるが、$4$ では割り切れない。

これは $4\mid d_m$ に矛盾する。

以上より、$d_m$ は奇素因数をもたず、さらに $4$ でも割り切れない。したがって、$d_m$ に含まれる素因数は $2$ だけであり、その指数は高々 $1$ である。

よって、

$$ d_m=1 \quad \text{または} \quad d_m=2 $$

である。

解説

この問題の中心は、$d_m$ が「すべての中間二項係数を割り切る数」であることを、二項定理に結びつける点である。

（2）では、

$$ (k+1)^m-(k+1) $$

を展開すると、帰納法の仮定で扱える $k^m-k$ と、係数がすべて ${}_mC_r$ である項に分かれる。この形に変形できれば、$d_m$ の定義がそのまま使える。

（3）では、（2）の結果を利用して、$d_m$ の素因数を制限する。偶数 $m$ に対して $k=p-1$ を代入すると、奇素数 $p$ が $d_m$ を割り切る可能性を排除できる。また $k=2$ を代入することで、$4$ が $d_m$ を割り切る可能性も排除できる。したがって $d_m$ は $1$ または $2$ に限られる。