合同式の応用（余りの問題）
合同式を使うと大きな数の余りや整数問題が効率よく解けます。
📘 例題①（大きな数の余り）
20242024 を 9 で割った余りを求めよ。
2024 = 2+0+2+4 = 8 → 2024≡8≡−1(mod 9)
20242024≡(−1)2024=1(mod 9)
解答：余りは 1
20242024 を 9 で割った余りを求めよ。
2024 = 2+0+2+4 = 8 → 2024≡8≡−1(mod 9)
20242024≡(−1)2024=1(mod 9)
解答：余りは 1
📘 例題②（整除の証明）
n が整数のとき、n³−n は 6 の倍数であることを示せ。
n³−n = n(n−1)(n+1)（3連続整数の積）
連続3整数は 2 の倍数を1つと 3 の倍数を1つ含む → 2×3=6 の倍数 ■
n が整数のとき、n³−n は 6 の倍数であることを示せ。
n³−n = n(n−1)(n+1)（3連続整数の積）
連続3整数は 2 の倍数を1つと 3 の倍数を1つ含む → 2×3=6 の倍数 ■
📘 例題③（合同方程式）
3x ≡ 2 (mod 7) を解け。
3×5=15≡1(mod 7) なので 3の逆元は5。両辺に5を掛ける：
x ≡ 5×2 = 10 ≡ 3 (mod 7)
解答：x ≡ 3 (mod 7)
3x ≡ 2 (mod 7) を解け。
3×5=15≡1(mod 7) なので 3の逆元は5。両辺に5を掛ける：
x ≡ 5×2 = 10 ≡ 3 (mod 7)
解答：x ≡ 3 (mod 7)
💡 ポイント
- 9 の倍数の判定：各桁の和が9の倍数
- 3 の倍数の判定：各桁の和が3の倍数
- n(n−1)(n+1) は連続3整数の積 → 6の倍数
- 合同方程式は逆元（ax≡1(mod m) の解）を使う
練習問題
- 7100 を 10 で割った余りを求めよ（一の位）。
- n が整数のとき、n²を4で割った余りは0か1しかないことを示せ。
- 2x ≡ 1 (mod 5) を解け。
解答・解説
- 7¹≡7、7²≡9、7³≡3、7⁴≡1(mod 10)（周期4）。100=4×25 → 7100≡1(mod 10) → 余り1（一の位は1）
- n≡0,1,2,3(mod 4) として n²≡0,1,0,1(mod 4) → 余りは0か1のみ ■
- 2×3=6≡1(mod 5) なので逆元は3。x≡3×1=3(mod 5) → x≡3(mod 5)