合同式（mod）の定義と計算
合同式は「割り算の余り」を扱う強力なツールです。
合同式の定義
整数 a と b が同じ余りで m で割れるとき、a ≡ b (mod m) と書く。
a ≡ b (mod m) ⟺ m | (a−b) ⟺ a と b を m で割った余りが等しい
合同式の基本性質
a≡b、c≡d (mod m) のとき：
・a+c ≡ b+d (mod m) （足し算）
・a−c ≡ b−d (mod m) （引き算）
・ac ≡ bd (mod m) （掛け算）
・an ≡ bn (mod m) （べき乗）
📘 例題①（合同式の計算）
17 ≡ 2 (mod 5)、23 ≡ 3 (mod 5) を使って 17×23 を 5 で割った余りを求めよ。
17×23 ≡ 2×3 = 6 ≡ 1 (mod 5)
解答：余りは 1
17 ≡ 2 (mod 5)、23 ≡ 3 (mod 5) を使って 17×23 を 5 で割った余りを求めよ。
17×23 ≡ 2×3 = 6 ≡ 1 (mod 5)
解答：余りは 1
📘 例題②（べき乗の余り）
3100 を 7 で割った余りを求めよ。
3¹≡3、3²≡2、3³≡6、3⁴≡4、3⁵≡5、3⁶≡1 (mod 7)（周期6）
100 = 6×16+4 → 3100≡3⁴≡4 (mod 7)
解答：余りは 4
3100 を 7 で割った余りを求めよ。
3¹≡3、3²≡2、3³≡6、3⁴≡4、3⁵≡5、3⁶≡1 (mod 7)（周期6）
100 = 6×16+4 → 3100≡3⁴≡4 (mod 7)
解答：余りは 4
💡 ポイント
- 合同式は足し算・引き算・掛け算・べき乗が使える
- 割り算は mod m と互いに素な数でのみ可能
- べき乗の余りは周期性を探す
練習問題
- 210 を 3 で割った余りを合同式を使って求めよ。
- 520 を 7 で割った余りを求めよ（まず 5 のべき乗の周期を調べよ）。
- 13×17×19 を 5 で割った余りを合同式で求めよ。
解答・解説
- 2≡−1(mod 3) → 210≡(−1)10=1(mod 3) → 余り1
- 5¹≡5、5²≡4、5³≡6、5⁴≡2、5⁵≡3、5⁶≡1(mod 7)（周期6）。20=6×3+2 → 520≡5²≡4(mod 7) → 余り4
- 13≡3、17≡2、19≡4(mod 5) → 3×2×4=24≡4(mod 5) → 余り4