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

方針・初手

(1) は、素数 $p$ が ${}_{p}\mathrm{C}_{r}$ の分子に現れ、分母には現れないことを利用する。

(2) は、(1) と二項定理を使って数学的帰納法で示す。$n \mapsto n+1$ としたとき、$(n+1)^p-n^p$ の中間項がすべて $p$ の倍数になることが核心である。

(3) は、$p$ で割った余りと $q$ で割った余りをそれぞれ調べる。$p,q$ は異なる素数なので、両方で割り切れれば $pq$ で割り切れる。

解法1

まず (1) を示す。

$1 \leqq r \leqq p-1$ とする。このとき

$$ {}_{p}\mathrm{C}_{r}=\frac{p!}{r!(p-r)!} $$

である。

分子 $p!$ には素数 $p$ が因数として含まれる。一方、分母 $r!(p-r)!$ に現れる数はすべて $1,2,\ldots,p-1$ 以下であり、どれも $p$ の倍数ではない。したがって、分母には素因数 $p$ は含まれない。

${}_{p}\mathrm{C}_{r}$ は整数であるから、分子に含まれる因数 $p$ は分母によって約分されない。よって

$$ p \mid {}_{p}\mathrm{C}_{r} $$

である。

したがって

$$ {}_pC_1,{}_pC_2,\ldots,{}*pC*{p-1} $$

はいずれも $p$ の倍数である。

次に (2) を示す。

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

$$ p \mid n^p-n $$

を数学的帰納法で証明する。

$n=1$ のとき、

$$ 1^p-1=0 $$

であるから、これは $p$ の倍数である。

ある自然数 $n$ について

$$ p \mid n^p-n $$

が成り立つと仮定する。このとき、二項定理より

$$ \begin{aligned} (n+1)^p &= n^p+{}_{p}\mathrm{C}_{1}n^{p-1}+{}_{p}\mathrm{C}_{2}n^{p-2}+\cdots+{}_{p}\mathrm{C}_{p-1}n+1 \end{aligned} $$

である。

(1) より、${}_{p}\mathrm{C}_{1},{}_{p}\mathrm{C}_{2},\ldots,{}_{p}\mathrm{C}_{p-1}$ はすべて $p$ の倍数である。したがって

$$ \begin{aligned} (n+1)^p-(n+1) &= (n^p-n) + {}_{p}\mathrm{C}_{1}n^{p-1} + {}_{p}\mathrm{C}_{2}n^{p-2} +\cdots+ {}_{p}\mathrm{C}_{p-1}n \end{aligned} $$

である。

右辺の第1項 $n^p-n$ は帰納法の仮定より $p$ の倍数であり、残りの各項も (1) より $p$ の倍数である。よって

$$ p \mid (n+1)^p-(n+1) $$

である。

したがって、数学的帰納法により、すべての自然数 $n$ に対して

$$ p \mid n^p-n $$

が成り立つ。

最後に (3) を示す。

示すべきことは

$$ pq \mid n^{(p-1)(q-1)+1}-n $$

である。

$p$ で割り切れることを示す。指数を

$$ E=(p-1)(q-1)+1 $$

とおく。

(i)

$p \mid n$ のとき

このとき $n$ は $p$ の倍数であるから、$n^E$ も $p$ の倍数である。したがって

$$ n^E-n $$

も $p$ の倍数である。

(ii)

$p \nmid n$ のとき

(2) より

$$ p \mid n^p-n $$

である。ここで $p \nmid n$ なので、合同式で書けば

$$ n^p \equiv n \pmod p $$

の両辺を $n$ で割ることができ、

$$ n^{p-1}\equiv 1 \pmod p $$

を得る。

いま

$$ E=(p-1)(q-1)+1 $$

であるから、

$$ \begin{aligned} n^E &= n^{(p-1)(q-1)+1} \\ n\left(n^{p-1}\right)^{q-1} \end{aligned} $$

である。よって

$$ n^E \equiv n\cdot 1^{q-1} \equiv n \pmod p $$

となる。

したがって、いずれの場合も

$$ p \mid n^E-n $$

である。

同様にして、$q$ で割り切れることも示す。

(i)

$q \mid n$ のとき、$n^E-n$ は $q$ の倍数である。

(ii)

$q \nmid n$ のとき、(2) を素数 $q$ に対して用いると

$$ n^{q-1}\equiv 1 \pmod q $$

である。また

$$ E=(p-1)(q-1)+1 $$

より

$$ \begin{aligned} n^E &= n^{(p-1)(q-1)+1} \\ n\left(n^{q-1}\right)^{p-1} \end{aligned} $$

であるから、

$$ n^E \equiv n\cdot 1^{p-1} \equiv n \pmod q $$

となる。

よって

$$ q \mid n^E-n $$

である。

以上より、$n^E-n$ は $p$ でも $q$ でも割り切れる。$p,q$ は異なる素数であるから互いに素である。したがって

$$ pq \mid n^E-n $$

である。

すなわち

$$ pq \mid n^{(p-1)(q-1)+1}-n $$

が示された。

解説

(1) は「素数 $p$ は $1,2,\ldots,p-1$ のどれも割らない」という性質を使う典型問題である。二項係数が整数であることと組み合わせることで、分子に残る因数 $p$ がそのまま全体を割ることが分かる。

(2) はフェルマーの小定理の形であるが、ここでは (1) を使って二項定理と数学的帰納法で示すのが自然である。$(n+1)^p$ を展開したとき、中間項の係数がすべて $p$ の倍数になるため、帰納法が成立する。

(3) は、$pq$ で割り切れることを直接見るのではなく、$p$ で割り切れることと $q$ で割り切れることを別々に示すのが要点である。$p,q$ が異なる素数であるため、両方で割り切れれば積 $pq$ で割り切れる。

答え

(1)

$$ {}_pC_1,{}_pC_2,\ldots,{}*pC*{p-1} $$

はいずれも $p$ の倍数である。

(2)

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

$$ n^p-n $$

は $p$ の倍数である。

(3)

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

$$ n^{(p-1)(q-1)+1}-n $$

は $pq$ の倍数である。