COMPASS

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

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

フェルマーの小定理

理論

フェルマーの小定理

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

 $p$ が素数であるならば, 各整数 $a$ に対して $a^p-a$ は $p$ の倍数である.

解説≪フェルマーテスト≫

 フェルマーの小定理の対偶は, 素数の候補の絞り込みに利用される.

カーマイケル数

定義≪カーマイケル数≫

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

命題≪カーマイケル数の特徴付け≫

 $n$ を合成数とし, 各整数 $a$ に対して $a^m-1$ が $n$ の倍数となるような正の整数 $m$ の最小値を $\lambda (n)$ で表す. このとき, 次は同値である.
(i)
$n$ はカーマイケル数である.
(ii)
$\lambda (n)$ は $n-1$ を割り切る.

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

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

証明: 原始根の存在定理, 中国式剰余の定理を使う

 (i) $\Longrightarrow$ (ii) の証明: $n$ をカーマイケル数とする. \[ (-1)^n \equiv -1 \pmod n\] と $n$ が合成数であることから, $n$ は奇数でなければならない. そこで, $n$ が相異なる奇素数 $p_1,$ $\cdots,$ $p_r$ の積 \[ n = p_1{}^{e_1}\cdots p_r{}^{e_r}\] ($e_1,$ $\cdots,$ $e_r$: 正の整数)に分解するとする. 各番号 $k \in \{ 1,\cdots,n\}$ に対して, $(\mathbb Z/p_k{}^{e_k}\mathbb Z)^\times$ は巡回群であるから, その生成元 $a_k \bmod{p_k{}^{e_k}}$ をとる. すると, 中国式剰余の定理により, 各番号 $k$ に対して \[ a \equiv a_k \pmod{p_k{}^{e_k}}\] を満たす整数 $a$ が存在する. この $a$ について, $a^{n-1} \equiv 1 \pmod n$ から, 各番号 $k$ に対して \[ a^{n-1} \equiv 1 \pmod{p_k{}^{e_k}}\] が成り立つので, \[ a_k{}^{n-1} \equiv 1 \pmod{p_k{}^{e_k}}\] が成り立つ. これと $a_k$ の位数が $\varphi (p_k{}^{e_k}) = p_k{}^{e_k-1}(p_k-1)$ であることから, $p_k{}^{e_k-1}(p_k-1)$ は $n-1$ を割り切る. ところが, $p_k$ は $n-1$ を割り切らないから, $e_k-1 = 0$ つまり $e_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$ が成り立つ.

問題

数学 A: 整数の性質

問題≪カーマイケル数の偶奇性≫

 各整数 $a$ に対して $a^n-a$ が $n$ の倍数であり, $n$ が合成数であるならば, $n$ は奇数であることを示せ.

解答例

 合成数 $n$ が条件を満たすとき, \[ (-1)^n \equiv -1 \pmod n\] が成り立つが, これは偶数の合成数に対しては成り立たないので, $n$ は奇数である.