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

Well-Known Problems and Theorems in Mathematics

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

フェルマーの小定理

フェルマーの小定理

定理《フェルマーの小定理》

(1)
$p$ が素数であるならば, すべての整数 $a$ に対して \[ a^p \equiv a \pmod p\] が成り立つ, つまり $a^p-a$ は $p$ の倍数である.
(2)
$p$ が素数であるならば, $p$ の倍数でない各整数 $a$ に対して \[ a^{p-1} \equiv 1 \pmod p\] が成り立つ, つまり $a^{p-1}-1$ は $p$ の倍数である.

証明

 $a$ が $p$ と互いに素であるとき, $a^p-a = a(a^{p-1}-1)$ が $p$ の倍数であることと $a^{p-1}-1$ が $p$ の倍数であることは同値であるから, (1) と (2) は同値である.
 (1) の証明については, こちら (合同式を利用), こちら (二項定理と数学的帰納法を利用), こちら (多項定理を利用) を参照.

オイラーの定理

定義《オイラーの $\varphi$ 関数》

 正の整数 $n$ と互いに素な $1$ 以上 $n$ 以下の整数の個数を $\varphi (n)$ で表す. この関数 $\varphi (n)$ ($n$: 正の整数) をオイラーの $\varphi$ 関数 (Euler's totient function) と呼ぶ.

定理《オイラーの定理》

 正の整数 $n$ と互いに素なすべての整数 $a$ に対して \[ a^{\varphi (n)} \equiv 1 \pmod n\] が成り立つ, つまり $a^{\varphi (n)}-1$ は $n$ の倍数である.

証明

 $n$ と互いに素な $1$ 以上 $n$ 以下の整数全体の集合を $S$ とおく. $k \in S$ のとき, $ak$ を $n$ で割った余りを $r_k$ とおく. このとき, $\{ r_k|k \in S\} = S$ となるから, $ak \equiv r_k \pmod n$ の辺々を掛けると, \[ a^{\varphi (n)}\prod _{k \in S}k \equiv \prod _{k \in S}r_k = \prod _{k \in S}k \pmod n\] となる. ここで, $\prod _{k \in S}k,$ $\prod _{k \in S}r_k$ はすべての $S$ の要素 $k$ にわたる $k$ の積, $r_k$ の積を表す. $\prod _{k \in S}k$ と $n$ は互いに素であるから, \[ a^{\varphi (n)} \equiv 1 \pmod n\] が成り立つ.

定理《オイラーの $\varphi$ 関数の乗法性》

(1)
互いに素な整数 $m,$ $n$ に対して, \[\varphi (mn) = \varphi (m)\varphi (n)\] が成り立つ.
(2)
$1$ より大きい整数 $n$ が
$n = \displaystyle\prod_{k = 1}^rp_k{}^{e_k}$ ($p_k$: 相異なる素数, $e_k$: 正の整数)
と素因数分解されるとき, \[\varphi (n) = \prod_{k = 1}^r(p_k{}^{e_k}-p_k{}^{e_k-1}) = n\prod_{k = 1}^r\left( 1-\frac{1}{p_k}\right)\] が成り立つ.

証明

(1)
正の整数 $l$ に対して, $l$ と互いに素な $1$ 以上 $l$ 以下の整数全体の集合を $S_l$ とおき, 整数 $a$ を $l$ で割った余りを $[a]_l$ で表す. 整数 $a$ が $mn$ と互いに素であるとき $[a]_m$ は $m$ と互いに素, $[a]_n$ は $n$ と互いに素であることに注意すると, $S_{mn}$ の要素 $a$ を $S_m\times S_n$ の要素 $([a]_m,[a]_n)$ にうつす写像が定まる. 中国式剰余定理によりこの写像は全単射であるから, $S_{mn}$ の要素の個数 $\varphi (mn)$ と $S_m\times S_n$ の要素の個数 $\varphi (m)\varphi (n)$ は等しい.
(2)
各番号 $k$ $(1 \leqq k \leqq n)$ に対して \[\varphi (p_k{}^{e_k}) = p_k{}^{e_k}-p_k{}^{e_k-1} = p_k{}^{e_k}\left( 1-\frac{1}{p_k}\right)\] であるから, (1) により \[\begin{aligned} \varphi (n) &= \prod_{k = 1}^r\varphi (p_k{}^{e_k}) \\ &= \prod_{k = 1}^r(p_k{}^{e_k}-p_k{}^{e_k-1}) = n\prod_{k = 1}^r\left( 1-\frac{1}{p_k}\right) \end{aligned}\] が成り立つ.

カーマイケル数

定義《カーマイケル数》

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

定理《コルセルトの判定法》

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

高校数学の問題

整数の性質

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

 $a,$ $b,$ $a',$ $b',$ $c,$ $n$ $(n > 1)$ を整数とし, $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)$ が成り立つ.
(参考: 東京農業大, $2020$ 静岡大)

解答例

 こちらを参照.

問題《シェルピンスキー数》

 すべての正の整数 $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}$ は証明なしに使ってよい.

解答例

 こちらを参照.

問題《$4n+1$ 型の素数の無限性》

 $4$ で割った余りが $1$ である素数は無限に存在するという定理を示したい. 仮に, $4$ で割った余りが $1$ である素数が $p_1,$ $\cdots,$ $p_r$ のみであるとする. $a = 2p_1\cdots p_r,$ $b = a^2+1$ とおき, $p$ を $b\,(> 1)$ の $1$ つの素因数とする.
(1)
$p$ は非負整数 $n$ を用いて $p = 4n+3$ の形に表されることを示せ.
(2)
$a^{p-1}$ を $p$ で割った余りについて「フェルマーの小定理」$a^{p-1} \equiv 1 \pmod p$ ($p$: 素数, $a$: $p$ と互いに素な整数; こちらを参照) に反する結果を導くことで, 定理を示せ.

解答例

 こちらを参照.

問題《カーマイケル数の性質》

 $n$ を $1$ より大きい整数とする. すべての整数 $a$ に対して $a^n-a$ が $n$ の倍数であり, $n$ が合成数であるとき, $n$ を「カーマイケル数」と呼ぶ. 次のことを示せ.
(1)
「カーマイケル数」は奇数である.
(2)
「カーマイケル数」は相異なる素数の積である.
ヒント: (1) では $a = n-1$ の場合を, (2) では $n$ の素因数分解における素数 $p$ の指数を $m$ として $a = p^{m-1}$ の場合を考える. (1) では二項定理 (こちらを参照) を使う.

解答例

 こちらを参照.

式と証明

問題《くくり出し公式とフェルマーの小定理》

 $n$ を正の整数, $r$ を $0 < r < n$ なる整数, $p$ を素数, $k$ を $0 < k < p$ なる整数とする. 次のことを示せ.
(1)
$r\,{}_n\mathrm C_r = n\,{}_{n-1}\mathrm C_{r-1}$ が成り立つ.
(2)
${}_p\mathrm C_k$ は $p$ の倍数である.
(3)
すべての整数 $a$ に対して, $a^p-a$ は $p$ の倍数である.
(参考: $2022$ 大阪教育大, $2014$ 富山大, $1978$ 京都大,$1974$ 早稲田大)

解答例

 こちらを参照.

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

 $p$ を素数, $n$ を正の整数とする. 次のことを示せ.
(1)
$(x_1+\cdots +x_n)^p-(x_1{}^p+\cdots +x_n{}^p)$ を展開して整理した式における各項の係数は $p$ で割り切れる.
(2)
$n^p-n$ は $p$ で割り切れる.

解答例

 こちらを参照.