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

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$ が成り立つ.

問題

数学 A: 整数の性質

問題《フェルマーの小定理と RSA 暗号系の原理》

 $a,$ $b,$ $a',$ $b',$ $c,$ $n$ を整数とし, $p,$ $q$ を相異なる素数とする. $a-a'$ が $n$ で割り切れるとき, $a \equiv a'\ (\text{mod}\ n)$ と表す. 次のことを示せ.
(1)
$a \equiv a',$ $b \equiv b'\ (\text{mod}\ n)$ ならば, $ab \equiv a'b'\ (\text{mod}\ n)$ が成り立つ.
(2)
$c$ が $p$ の倍数でないとする. このとき, $ac \equiv a'c\ (\text{mod}\ p)$ ならば, $a \equiv a'\ (\text{mod}\ p)$ が成り立つ.
(3)
$a$ が $p$ の倍数でないとき, $p-1$ 以下の正の整数全体から成る集合を $G$ とおき, $k \in G$ なる各整数 $k$ に対して $ak$ を $p$ で割った余りを $r_k$ とおくと, $\{ r_k|k \in G\} = G$ が成り立つ.
(4)
$a$ が $p$ の倍数でないとき, $a^{p-1} \equiv 1\ (\text{mod}\ p)$ が成り立つ.
(5)
$n = pq$ とし, 整数 $e,$ $d$ が \[ ed \equiv 1\ (\text{mod}{(p-1)(q-1)})\] を満たすとする. このとき, $n$ と互いに素な整数 $a,$ $b$ に対して, $a^e \equiv b\ (\text{mod}\ n)$ ならば, $b^d \equiv a\ (\text{mod}\ n)$ が成り立つ.

解答例

 こちらを参照.

問題《フェルマーの小定理とシェルピンスキー数》

 すべての正の整数 $n$ に対して $a_n = 78557\cdot 2^n+1$ は合成数であることを,
(A) $n \equiv 0$$\pmod 2$ $\Longrightarrow$ $a_n \equiv 0 \pmod 3$
(B) $n \equiv 1$$\pmod 4$ $\Longrightarrow$ $a_n \equiv 0 \pmod 5$
(C) $n \equiv 3$$\pmod{36}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{73}$
(D) $n \equiv 15$$\pmod{36}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{19}$
(E) $n \equiv 27$$\pmod{36}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{37}$
(F) $n \equiv 7$$\pmod{12}$ $\Longrightarrow$ $a_n \equiv 0 \pmod 7$
(G) $n \equiv 11$$\pmod{12}$ $\Longrightarrow$ $a_n \equiv 0 \pmod{13}$
を示すことによって証明せよ. 「フェルマーの小定理」
$a^{p-1} \equiv 1 \pmod p$ ($p$: 素数, $a$: $p$ と互いに素な整数)
と, $2^9 \equiv 1 \pmod{73}$ は証明なしに用いてよい.

解答例

 こちらを参照.

数学 II: 式と証明

問題《二項係数の関係式とフェルマーの小定理》

 $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$ の倍数である.
(参考: 1998 奈良女子大)

解答例

 こちらを参照.