フェルマーの小定理
フェルマーの小定理
定理《フェルマーの小定理》
- (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) の証明については, こちら (合同式を利用), こちら (二項定理と数学的帰納法を利用), こちら (多項定理を利用) を参照.
(1) の証明については, こちら (合同式を利用), こちら (二項定理と数学的帰納法を利用), こちら (多項定理を利用) を参照.
別証明:「群論」の「ラグランジュの定理」を利用
$p$ 元体の乗法群 $\mathbb F_p{}^\times$ の位数 $p-1$ であるから, ラグランジュの定理により ${\bar a}^{p-1} = 1$ $(\bar a \in \mathbb F_p{}^\times)$ が成り立つ.
よって, 整数係数多項式 $x^{p-1}-1$ は $p$ で割り切れる.
ゆえに, 整数 $a$ に対して, $a$ を $p$ で割った余りが $i$ であるとき,
\[ a^{p-1}-1 \equiv i^{p-1}-1 \equiv 0 \pmod p\]
が成り立つ.
オイラーの定理
定義《オイラーの $\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$ が成り立つ.
$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$ は合成数であることを,
を示すことによって証明せよ.
「フェルマーの小定理」
と, $2^9 \equiv 1 \pmod{73}$ は証明なしに使ってよい.
| (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$ と互いに素な整数) |
解答例
こちらを参照.
問題《$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)
- 「カーマイケル数」は相異なる素数の積である.
解答例
こちらを参照.
式と証明
問題《くくり出し公式とフェルマーの小定理》
$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$ で割り切れる.
解答例
こちらを参照.