COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

フェルマーの小定理

フェルマーの小定理

定理≪フェルマーの小定理≫

(1)
$p$ が素数であるならば, すべての整数 $a$ に対して $a^p-a$ は $p$ の倍数である.
(2)
$p$ が素数であるならば, $p$ の倍数でない各整数 $a$ に対して $a^{p-1}-1$ は $p$ の倍数である.

証明

 $a$ が $p$ と互いに素であるとき, $a^p-a = a(a^{p-1}-1)$ が $p$ の倍数であることと $a^{p-1}-1$ が $p$ の倍数であることは同値であるから, (1) と (2) は同値である.
 (1) の証明については, こちらを参照.

問題

融合問題

問題≪フェルマーの小定理≫

 $p$ を素数とし, $k$ を $p-1$ 以下の正の整数とする. 次のことを示せ.
(1)
$k\,{}_p\mathrm C_k = p\,{}_{p-1}\mathrm C_{k-1}$ が成り立つ.
(2)
${}_p\mathrm C_k$ は $p$ の倍数である.
(3)
各整数 $a$ に対して, $a^p-a$ は $p$ の倍数である.
[奈良女子大*]

解答例

(1)
二項係数の定義により, \begin{align*} k\,{}_p\mathrm C_k &= k\cdot\frac{p!}{k!(p-k)!} \\ &= k\cdot\frac{p}{k}\cdot\frac{(p-1)!}{(k-1)!\{ (p-1)-(k-1)\} !} \\ &= p\,{}_{p-1}\mathrm C_{k-1} \end{align*} が成り立つ.
(2)
(1) から, $k\,{}_p\mathrm C_k$ は $p$ の倍数である.
$p$ は素数であり, $1 \leqq k \leqq p-1$ であるから, $p,$ $k$ は互いに素である.
よって, ${}_p\mathrm C_k$ は $p$ の倍数である.
(3)
(I)
$a \geqq 0$ のとき. $a$ に関する数学的帰納法で示す.
(i)
$a = 0$ のとき. $0^p-0 = 0$ から, $a^p-a$ は $p$ の倍数である.
(ii)
与えられた非負整数 $a$ に対して $a^p-a$ が $p$ の倍数であるとする. このとき, (2) から \begin{align*} &(a+1)^p-(a+1) \\ &= \left( a^p+\sum\limits_{k = 1}^{p-1}{}_p\mathrm C_ka^{p-k}+1\right) -(a+1) \\ &= (a^p-a)+\sum\limits_{k = 1}^{p-1}{}_p\mathrm C_ka^{p-k} \end{align*} は $p$ の倍数となる.
(i), (ii) から, $a \geqq 0$ のとき $a^p-a$ は $p$ の倍数である.
(II)
$a < 0,$ $p \geqq 3$ のとき. $p$ は奇数であるから $(-a)^p-(-a) = -(a^p-a)$ であり, これは (i) から $p$ の倍数である. よって, $a^p-a$ も $p$ の倍数である.
(III)
$a < 0,$ $p = 2$ のとき. $a^2-a = a(a-1)$ は偶数であるから, $a^p-a$ は $p$ の倍数である.
(I)~(III) から, 各整数 $a$ に対して $a^p-a$ は $p$ の倍数である.

別解

(1)
$p$ 人から $k$ 人を選び, その $k$ 人からリーダー $1$ 人を選ぶ方法は, 全部で ${}_p\mathrm C_k\cdot k$ 通りある. 同様にするには, $p$ 人からリーダー $1$ 人 L を選んでおき, L を除く $p-1$ 人から残りの $k-1$ 人を選ぶこともできるから, これは $p{}_{p-1}\mathrm C_{k-1}$ に等しい. よって, $k\,{}_p\mathrm C_k = p\,{}_{p-1}\mathrm C_{k-1}$ が成り立つ.

背景

 (3) で示した命題は,「フェルマーの小定理」(Fermat's little theorem)と呼ばれ, 整数論の諸定理の証明に使われている.
 また, この定理の対偶から, ある整数 $a$ に対して $a^n-a$ が $n$ の倍数とならないような $1$ より大きい整数 $n$ は合成数であることが言える. これは, 素数の候補の絞り込みに利用されている.