フェルマーの小定理とオイラーの定理

$g cd (a, n) = 1$ のとき $a^{φ (n)} \equiv 1 (mod n)$ （ $n = p$ が素数なら $a^{p - 1} \equiv 1$ ）を使って指数を下げ、 $3^{2024} mod 100$ のような大きな累乗の余りを求められる

前提

オイラー関数の計算（大学数学整数論）

この技能までの道筋（26 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
互いに素な法への分解（数学A 整数の性質）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
包除原理（数学A 場合の数と確率）
オイラー関数の計算（大学数学整数論）

説明

$g cd (a, n) = 1$ のとき $a^{φ (n)} \equiv 1 (mod n)$ が成り立ちます（オイラーの定理）。 $n = p$ が素数なら $φ (p) = p - 1$ なので $a^{p - 1} \equiv 1 (mod p)$ です（フェルマーの小定理。ただし $p ∤ a$ ）。これを使うと、指数を $φ (n)$ で割った余りまで下げられます。そのため、 $3^{2024}$ を $100$ で割った余りのような大きな累乗の余りを、小さな計算で求められます。

なぜそうしてよいのか

$1$ 以上 $n$ 以下で $n$ と互いに素な整数を $r_{1}, r_{2}, \dots, r_{k}$ とします。オイラー関数の定義から $k = φ (n)$ です。これら全部に、 $n$ と互いに素な $a$ を掛けた $a r_{1}, a r_{2}, \dots, a r_{k}$ を考えます。 $a$ も $r_{i}$ も $n$ と共通の素因数をもたないので、 $a r_{i}$ も $n$ と互いに素です。また $a r_{i} \equiv a r_{j} (mod n)$ なら $n ∣ a (r_{i} - r_{j})$ であり、 $g cd (a, n) = 1$ より $n ∣ r_{i} - r_{j}$ となります。 $∣ r_{i} - r_{j} ∣ < n$ なので $r_{i} = r_{j}$ です。したがって $a r_{1}, \dots, a r_{k}$ を $n$ で割った余りは互いに異なり、どれも $n$ と互いに素です。つまり $r_{1}, \dots, r_{k}$ を並べ替えたものになっています。

並べ替えても積は変わらないので、 $a^{k} r_{1} r_{2} \dots r_{k} \equiv r_{1} r_{2} \dots r_{k} (mod n)$ が成り立ちます。 $R = r_{1} \dots r_{k}$ は $n$ と互いに素です。よって $n ∣ (a^{k} - 1) R$ から $n ∣ a^{k} - 1$ が言えて、 $a^{φ (n)} \equiv 1 (mod n)$ が得られます。 $n = p$ が素数なら $φ (p) = p - 1$ なので、フェルマーの小定理になります。

$a^{φ (n)} \equiv 1$ が分かると、指数 $e$ を $e = q φ (n) + r$ （ $0 \leq r < φ (n)$ ）と割ったとき $a^{e} = (a^{φ (n)})^{q} \cdot a^{r} \equiv 1^{q} \cdot a^{r} = a^{r} (mod n)$ となります。指数を $φ (n)$ で割った余りに取り替えてよいのは、このためです。

手順

底 $a$ と法 $n$ が互いに素か確かめる： $g cd (a, n) = 1$ 。互いに素でなければこの方法はそのまま使えない
オイラー関数を計算する： $φ (n) = n \prod_{p ∣ n} (1 - \frac{1}{p})$ 。 $n$ が素数 $p$ なら $φ (p) = p - 1$
指数 $e$ を $φ (n)$ で割る： $e = q φ (n) + r$ $(0 \leq r < φ (n))$
指数を下げる： $a^{e} \equiv a^{r} (mod n)$ 。 $r = 0$ なら $a^{e} \equiv 1$
$a^{r} mod n$ を計算する。2 乗を繰り返して $a^{2}, a^{4}, a^{8}, \dots$ の余りを作り、それらを組み合わせると速い。答えは $0$ 以上 $n - 1$ 以下で書く

例題

$3^{2024}$ を $100$ で割った余りを求めよ。

例題の解答

手順1： $100 = 2^{2} \cdot 5^{2}$ で、 $3$ は $2$ でも $5$ でも割り切れません。よって $g cd (3, 100) = 1$ です。

手順2： $φ (100) = 100 (1 - \frac{1}{2}) (1 - \frac{1}{5}) = 40$ です。したがってオイラーの定理より $3^{40} \equiv 1 (mod 100)$ です。

手順3： $2024 = 40 \cdot 50 + 24$ なので、余りは $r = 24$ です。

手順4： $3^{2024} = (3^{40})^{50} \cdot 3^{24} \equiv 3^{24} (mod 100)$ です。

手順5：2 乗を繰り返して余りを作ります。
- $3^{4} = 81$
- $3^{8} \equiv 8 1^{2} = 6561 \equiv 61$
- $3^{16} \equiv 6 1^{2} = 3721 \equiv 21$

よって $3^{24} = 3^{16} \cdot 3^{8} \equiv 21 \cdot 61 = 1281 \equiv 81 (mod 100)$ です。

したがって、余りは $81$ です。

答え: $81$

よくある誤り

$g cd (a, n) \neq = 1$ なのに $a^{φ (n)} \equiv 1$ としてしまう誤り。例えば $2^{40} \equiv 1 (mod 100)$ は誤りです（ $2^{40}$ は偶数なので、 $100$ で割った余りが $1$ になることはありません）。正しくは $2^{40} \equiv 76 (mod 100)$ です。
指数を法 $n$ （または $p$ ）で割った余りに下げてしまう誤り。例えば $2^{100} mod 7$ を $100 \equiv 2 (mod 7)$ から $2^{2} = 4$ とするのは誤りです。正しくは指数を $φ (7) = 6$ で割ります。 $100 = 6 \cdot 16 + 4$ なので $2^{100} \equiv 2^{4} = 16 \equiv 2 (mod 7)$ です。
合成数 $n$ にフェルマーの小定理の形 $a^{n - 1} \equiv 1$ を使ってしまう誤り。例えば $3^{99} \equiv 1 (mod 100)$ は誤りです。正しくは $φ (100) = 40$ を使います。 $3^{99} \equiv 3^{19} (mod 100)$ となり、実際に計算すると $3^{99} \equiv 67 (mod 100)$ です。
指数の余り $r$ が $0$ のときに $a^{e} \equiv a^{0}$ を $0$ と取り違える誤り。例えば $3^{80} \equiv 0 (mod 100)$ とするのは誤りです。正しくは $80 = 40 \cdot 2 + 0$ なので $3^{80} \equiv (3^{40})^{2} \equiv 1 (mod 100)$ です。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

法 n を法とする位数（大学数学整数論）
平方剰余とオイラーの規準（大学数学整数論）