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

方針・初手

前半は二項定理と素数 $p$ の性質を使って、フェルマーの小定理

$$ m^p \equiv m \pmod p $$

を導く流れである。

後半は

$$ 4n^2+4n-1=(2n+1)^2-2 $$

と変形することが核心である。$p\mid a$ なら

$$ (2n+1)^2\equiv 2 \pmod p $$

となるので、これをフェルマーの小定理と結びつける。

解法1

(1)

$0<j<p$ より、$j$ と $p$ は互いに素である。

二項係数について

$$ j{}*pC_j=p{}*{p-1}C_{j-1} $$

が成り立つ。右辺は $p$ の倍数であるから、左辺 $j{}_pC_j$ は $p$ の倍数である。

ここで $\gcd(j,p)=1$ である。したがって、積 $j{}_pC_j$ が $p$ で割り切れるためには、${}_pC_j$ が $p$ で割り切れなければならない。

よって、

$$ p\mid {}_pC_j $$

である。

(2)

二項定理より、

$$ (m+1)^p=m^p+{}_pC_1m^{p-1}+{}_pC_2m^{p-2}+\cdots+{}*pC*{p-1}m+1 $$

である。したがって、

$$ (m+1)^p-m^p-1={}_pC_1m^{p-1}+{}_pC_2m^{p-2}+\cdots+{}*pC*{p-1}m $$

となる。

(1)より、$1\leq j\leq p-1$ に対して ${}_pC_j$ はすべて $p$ で割り切れる。したがって右辺の各項は $p$ で割り切れる。

よって、

$$ p\mid {(m+1)^p-m^p-1} $$

である。

(3)

まず、すべての自然数 $m$ に対して

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

を数学的帰納法で示す。

$m=1$ のとき、

$$ 1^p-1=0 $$

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

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

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

が成り立つと仮定する。このとき、

$$ \begin{aligned} {(m+1)^p-(m+1)}-(m^p-m) &=(m+1)^p-m^p-1 \end{aligned} $$

である。

(2)より、右辺は $p$ で割り切れる。また、帰納法の仮定より $m^p-m$ も $p$ で割り切れる。したがって、

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

も $p$ で割り切れる。

よって、すべての自然数 $m$ に対して

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

が成り立つ。

さらに、$m$ が $p$ で割り切れないとする。このとき、

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

である。

すでに $p\mid (m^p-m)$ が分かっているので、

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

である。一方、仮定より $p\nmid m$ である。$p$ は素数だから、積が $p$ で割り切れて一方の因数 $m$ が $p$ で割り切れないなら、もう一方の因数が $p$ で割り切れる。

したがって、

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

である。

(4)

$a\in S$ より、

$$ a=4n^2+4n-1 $$

と表される。ここで

$$ 4n^2+4n-1=(2n+1)^2-2 $$

である。

$a$ と $2n+1$ の正の公約数を $d$ とする。このとき、

$$ d\mid a,\qquad d\mid (2n+1) $$

である。

$d\mid (2n+1)$ だから、

$$ d\mid (2n+1)^2 $$

である。また、

$$ a=(2n+1)^2-2 $$

なので、$d\mid a$ と $d\mid (2n+1)^2$ から

$$ d\mid 2 $$

が従う。

一方、$2n+1$ は奇数であるから、その約数 $d$ も奇数である。よって、$d$ は $2$ の約数であり、かつ奇数であるから

$$ d=1 $$

である。

したがって、$a$ と $2n+1$ は互いに素である。

(5)

$p$ は $3$ 以上の素数であり、$p$ が $S$ に属するある整数 $a$ を割り切るとする。

$a\in S$ より、ある自然数 $n$ を用いて

$$ a=4n^2+4n-1=(2n+1)^2-2 $$

と表される。

$p\mid a$ だから、

$$ (2n+1)^2-2\equiv 0 \pmod p $$

すなわち

$$ (2n+1)^2\equiv 2 \pmod p $$

である。

また、(4)より $a$ と $2n+1$ は互いに素である。いま $p\mid a$ であるから、もし $p\mid (2n+1)$ なら $p$ は $a$ と $2n+1$ の公約数になってしまう。これは (4) に反する。

したがって、

$$ p\nmid (2n+1) $$

である。

そこで、(3)の後半を $m=2n+1$ に適用すると、

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

は $p$ で割り切れる。すなわち、

$$ (2n+1)^{p-1}\equiv 1 \pmod p $$

である。

一方、

$$ (2n+1)^2\equiv 2 \pmod p $$

なので、両辺を $\dfrac{p-1}{2}$ 乗して、

$$ {(2n+1)^2}^{\frac{p-1}{2}}\equiv 2^{\frac{p-1}{2}}\pmod p $$

となる。左辺は

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

であるから、

$$ 2^{\frac{p-1}{2}}\equiv (2n+1)^{p-1}\equiv 1 \pmod p $$

である。

よって、

$$ p\mid \left(2^{\frac{p-1}{2}}-1\right) $$

が示された。

解説

(1)は、二項係数 ${}_pC_j$ が素数 $p$ を因数にもつことを示す基本事実である。この結果により、二項展開したときの中間項がすべて $p$ の倍数になる。

(2)はその直接利用であり、(3)はそれを帰納法に組み込むことでフェルマーの小定理を導いている。

後半の要点は、$4n^2+4n-1$ をそのまま扱わず、

$$ 4n^2+4n-1=(2n+1)^2-2 $$

と平方の形に直すことである。これにより、$p\mid a$ から

$$ (2n+1)^2\equiv 2 \pmod p $$

が得られる。

さらに (4) によって $2n+1$ が $p$ で割り切れないことを保証し、フェルマーの小定理を適用できるようにしている点が重要である。

答え

(1)

$0<j<p$ のとき、${}_pC_j$ は $p$ で割り切れる。

(2)

すべての自然数 $m$ に対して、$(m+1)^p-m^p-1$ は $p$ で割り切れる。

(3)

すべての自然数 $m$ に対して、$m^p-m$ は $p$ で割り切れる。また、$p\nmid m$ のとき、$m^{p-1}-1$ は $p$ で割り切れる。

(4)

$a=4n^2+4n-1$ と $2n+1$ は互いに素である。

(5)

$p$ が $S$ に属するある整数 $a$ を割り切るならば、

$$ 2^{\frac{p-1}{2}}-1 $$

は $p$ で割り切れる。