基礎問題集
数学A 整数問題「フェルマーの小定理」の問題8 解説
数学Aの整数問題「フェルマーの小定理」にある問題8の基礎問題と解説ページです。問題と保存済み解説を公開し、ログイン後はAI質問と学習履歴も利用できます。
MathGrAIl の基礎問題集にある公開問題ページです。ログイン前でも問題と保存済み解説を確認でき、ログイン後はAI質問と学習履歴の保存を利用できます。
- 基礎問題の問題画像と保存済み解説を公開
- ログイン後にAI質問で復習
- ログイン後に学習履歴を保存
解説
方針・初手
まず二項係数 $_p C_r$ が $p$ で割り切れることを示し、それを二項展開に利用する。
(2) は $(n+1)^p$ を二項展開すれば、両端以外の項に $_p C_r$ が現れる。(3) は (2) を使って数学的帰納法で示す。(4) は (3) の結果を合同式で読み替える。
解法1
**(1)**
$r=1,2,\dots,p-1$ とする。
$$ {}_p C_r=\frac{p!}{r!(p-r)!}
$$
である。ここで $1\leqq r\leqq p-1$ より、$r!$ にも $(p-r)!$ にも素数 $p$ は因数として含まれない。
一方、$p!$ には因数 $p$ がちょうど $1$ 個含まれる。したがって、分母 $r!(p-r)!$ ではこの因数 $p$ は消えない。
よって $_p C_r$ は $p$ の倍数である。
**(2)**
二項定理より、
$$ (n+1)^p=\sum_{r=0}^{p} {}_p C_r n^{p-r}
$$
である。両端の項を取り出すと、
$$ (n+1)^p=n^p+{}_p C_1n^{p-1}+{}_p C_2n^{p-2}+\cdots+{}*p C*{p-1}n+1
$$
となる。
したがって、
$$ (n+1)^p-(n^p+1) ={}_p C_1n^{p-1}+{}_p C_2n^{p-2}+\cdots+{}*p C*{p-1}n
$$
である。
(1) より、$r=1,2,\dots,p-1$ に対して $_p C_r$ はすべて $p$ の倍数である。よって右辺の各項は $p$ の倍数である。
したがって、
$$ (n+1)^p-(n^p+1)
$$
は $p$ の倍数である。
**(3)**
$n$ に関する数学的帰納法で示す。
$n=1$ のとき、
$$ 1^p-1=0
$$
であり、これは $p$ の倍数である。
次に、ある自然数 $n$ について
$$ n^p-n
$$
が $p$ の倍数であると仮定する。
このとき、
$$ \begin{aligned} (n+1)^p-(n+1) &={(n+1)^p-(n^p+1)}+(n^p-n) \end{aligned}
$$
である。
(2) より、$(n+1)^p-(n^p+1)$ は $p$ の倍数である。また、帰納法の仮定より、$n^p-n$ も $p$ の倍数である。
したがって、
$$ (n+1)^p-(n+1)
$$
も $p$ の倍数である。
よって数学的帰納法により、すべての自然数 $n$ について
$$ n^p-n
$$
は $p$ の倍数である。
**(4)**
(3) より、
$$ n^p-n\equiv 0 \pmod p
$$
である。すなわち、
$$ n(n^{p-1}-1)\equiv 0 \pmod p
$$
である。
ここで、$n$ が $p$ の倍数である場合とそうでない場合に分ける。
**(i)**
$n$ が $p$ の倍数であるとき
$n\equiv 0\pmod p$ であるから、
$$ n^{p-1}\equiv 0 \pmod p
$$
である。
したがって、$n^{p-1}$ を $p$ で割った余りは $0$ である。
**(ii)**
$n$ が $p$ の倍数でないとき
$p$ は素数であり、$n$ は $p$ の倍数でないから、$n$ と $p$ は互いに素である。
$$ n(n^{p-1}-1)\equiv 0 \pmod p
$$
において、$p$ は $n$ を割らないので、$p$ は $n^{p-1}-1$ を割る。
したがって、
$$ n^{p-1}\equiv 1 \pmod p
$$
である。
よって、$n^{p-1}$ を $p$ で割った余りは $1$ である。
解説
この問題は、二項定理からフェルマーの小定理を導く標準的な流れである。
中心になるのは、素数 $p$ に対して中間の二項係数 $_p C_1,{}_p C_2,\dots,{}*p C*{p-1}$ がすべて $p$ の倍数になる点である。これにより、二項展開したときに両端以外の項がすべて $p$ の倍数として処理できる。
(3) は (2) を使った数学的帰納法で処理するのが自然である。(4) では、$n$ が $p$ の倍数かどうかで余りが変わるため、場合分けを省略してはいけない。
答え
**(1)**
$r=1,2,\dots,p-1$ に対して、$_p C_r$ は $p$ の倍数である。
**(2)**
$(n+1)^p-(n^p+1)$ は $p$ の倍数である。
**(3)**
$n^p-n$ は $p$ の倍数である。
**(4)**
$$ n^{p-1}\text{ を }p\text{ で割った余り} =
\begin{cases} 0 & (p\mid n)\\ 1 & (p\nmid n) \end{cases}
$$