フェルマーの小定理
合同式の発展として、大きなべき乗の余りを瞬時に求める強力な定理です。
フェルマーの小定理
p が素数、a が p の倍数でない整数のとき：
ap−1 ≡ 1 (mod p)
同値な表現：ap ≡ a (mod p)（a が p の倍数でも成立）
📘 例題①
2100 を 101 で割った余りを求めよ。
101 は素数。フェルマーの小定理より 2100 ≡ 1 (mod 101)
解答：余りは 1
2100 を 101 で割った余りを求めよ。
101 は素数。フェルマーの小定理より 2100 ≡ 1 (mod 101)
解答：余りは 1
📘 例題②
32023 を 7 で割った余りを求めよ。
7 は素数。36 ≡ 1 (mod 7)（フェルマーより p−1=6）
2023 = 6×337 + 1 → 32023 ≡ 31 ≡ 3 (mod 7)
解答：余りは 3
32023 を 7 で割った余りを求めよ。
7 は素数。36 ≡ 1 (mod 7)（フェルマーより p−1=6）
2023 = 6×337 + 1 → 32023 ≡ 31 ≡ 3 (mod 7)
解答：余りは 3
📘 例題③（逆元への応用）
3x ≡ 1 (mod 7) の解を求めよ（フェルマーの小定理を使え）。
36≡1(mod 7) → 3×3⁵≡1(mod 7) → x≡3⁵=243≡243−7×34=243−238=5(mod 7)
解答：x ≡ 5 (mod 7)
3x ≡ 1 (mod 7) の解を求めよ（フェルマーの小定理を使え）。
36≡1(mod 7) → 3×3⁵≡1(mod 7) → x≡3⁵=243≡243−7×34=243−238=5(mod 7)
解答：x ≡ 5 (mod 7)
💡 ポイント
- ap−1≡1(mod p)（p：素数、p∤a）
- 指数を p−1 で割った余りに簡略化
- 逆元：a の逆元は ap−2 (mod p)
練習問題
- 512 を 13 で割った余りを求めよ。
- 71000 を 11 で割った余りを求めよ。
- 4x ≡ 1 (mod 13) をフェルマーの小定理を用いて解け。
解答・解説
- 13 は素数。512≡1(mod 13) → 余り1
- 11 は素数。710≡1(mod 11)。1000=10×100 → 71000≡1100=1(mod 11) → 余り1
- 412≡1(mod 13) → 4×411≡1 → x≡411(mod 13)。4²=16≡3、4⁴≡9、4⁸≡81≡3、411=4⁸×4²×4¹≡3×3×4=36≡10(mod 13) → x≡10(mod 13)