有名問題・定理から学ぶ数学

Well-Known Problems and Theorems in Mathematics

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください.

フェルマーの小定理

フェルマーの小定理

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

(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) の証明については, こちらを参照.

カーマイケル数

定義≪カーマイケル数≫

 各整数 $a$ に対して $a^n-a$ が $n$ の倍数となるような合成数 $n$ をカーマイケル数と呼ぶ.

定理≪コルセルトの判定法≫

 $n$ を正の整数とするとき, 次は同値である.
(i)
$n$ はカーマイケル数である.
(ii)
$n$ は相異なる奇素数の積に分解され, $n$ の各素因数 $p$ に対して $p-1$ は $n-1$ を割り切る.

証明: 群, 環, 体の理論の知識, 特に $p$ 元体の乗法群の原始根の存在, 中国式剰余定理を使う.

 (i) $\Longrightarrow$ (ii) の証明: $n$ を $1$ より大きい整数とし, すべての整数 $a$ に対して $a^n-a$ が $n$ の倍数であるとする. このとき, $(n-1)^n-(n-1)$ は $n$ の倍数であるから, $(-1)^n+1$ は $n$ の倍数である(二項定理を利用). $n$ が偶数であるとき, $n$ は $(-1)^n+1 = 2$ の約数となるから, $n = 2$ となる. $2$ は素数であるから,カーマイケル数は奇数である.
 $n$ をカーマイケル数とする. $n$ の素因数分解における素数 $p$ の指数を $m$ とおく. $p^{(m-1)n}-p^{m-1}$ は $n$ で割り切れ, $n$ は $p^m$ で割り切れるから, \[\frac{p^{(m-1)n}-p^{m-1}}{p^m} = \frac{p^{(m-1)(n-1)}-1}{p}\] は整数である. これが成り立つのは $m = 1$ の場合に限るから, カーマイケル数は相異なる素数の積である.
 カーマイケル数 $n$ が相異なる奇素数 $p_1,$ $\cdots,$ $p_r$ の積 \[ n = p_1\cdots p_r\] に分解されるとする. 各番号 $k$ に対して, $(\mathbb Z/p_k\mathbb Z)^\times$ は巡回群であるから, その生成元 $a_k \bmod{p_k}$ をとる. すると, 中国式剰余定理により, 各番号 $k$ に対して \[ a \equiv a_k \pmod{p_k}\] を満たす整数 $a$ が存在する. この $a$ について, $a^{n-1} \equiv 1 \pmod n$ から, 各番号 $k$ に対して \[ a^{n-1} \equiv 1 \pmod{p_k}\] が成り立つので, \[ a_k{}^{n-1} \equiv 1 \pmod{p_k}\] が成り立つ. これと $a_k$ の位数が $p_k-1$ であることから, $p_k-1$ は $n-1$ を割り切る.
 (ii) $\Longrightarrow$ (i) の証明: $n$ が相異なる奇素数 $p_1,$ $\cdots,$ $p_r$ の積 \[ n = p_1\cdots p_r\] に分解されるとし, $p_1-1,$ $\cdots,$ $p_r-1$ が $n-1$ を割り切るとすると, $n$ と互いに素な各整数 $a$ と各番号 $k$ に対してフェルマーの小定理により \[ a^{n-1} = (a^{p_k-1})^{(n-1)/(p_k-1)} \equiv 1^{(n-1)/(p_k-1)} = 1 \pmod{p_k}\] が成り立つから, $a^{n-1} \equiv 1 \pmod n$ が成り立つ.

問題

融合問題

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

 $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$ の倍数である.
[奈良女子大*]

解答例

 こちらを参照.