合同式
“合同式は時計算——一周すれば元に戻る。”
数式
a ≡ b (mod n) ⟺ n | (a − b)読み方: a と b が mod n で合同であるとは、n で割った余りが等しいこと——つまり n が a−b を割り切ること
- a ≡ b
- — a と b が合同（余りが同じ）であることを示す記号
- mod n
- — 法（modulus）n を基準に測ることを意味する——時計なら 12
- n | (a−b)
- — n が a−b を割り切る（差が n の倍数である）
きっかけ
時計では、9時の5時間後は14時ではなく2時です。この「一周したら最初に戻る」計算が合同式（モジュラー算術）です。
やさしく言うと
合同式とは、ある数 n に達すると 0 に巻き戻る計算のことです。二つの数は、n で割った余りが等しいとき「合同」といい、a ≡ b (mod n) と書きます。大事なのは余りだけです。
直感
数直線をまっすぐ伸ばす代わりに、n個の目盛りを持つ円（時計の文字盤）に巻きつけると想像してください。n を超えたら 0 に戻ります。12時間制の時計では 17:00 は 5 の位置に来る——だから 17 と 5 は mod 12 で合同です。大きな数は「輪の上の位置」に折りたたまれます。
どう作られるか
鍵となるのは余りです。a を n で割った余りが、a の「mod n での値」です。足し算・引き算・掛け算はすべて余りのまま成り立つので、大きな数そのものは必要なく、余りだけを扱えばよいのです。(a+b) mod n は、それぞれの余りを足してから mod n をとった値になります。
例
なぜ 17 ≡ 5 (mod 12) なのか：17 − 5 = 12 は 12 の倍数です。時計では 17:00 は午後5時。また 25 mod 7 = 4 で、これは 25 = 3·7 + 4 だからです。
よくある誤解
一般的な約束では、余りは負の数になりません。例えば −1 mod 5 は −1 ではなく 4 です（−1 = (−1)·5 + 4 だから）。時計で1時間戻ると11時になるのと同じ感覚です。
どこで使うか
現代暗号（RSA、楕円曲線暗号）の中核、ハッシュ関数やチェックサム（ISBNやクレジットカードの検証）、曜日やカレンダーの計算、乱数生成器、12音階の音楽理論——周期的な計算はすべて合同式で動いています。
どこから来たか
ガウスは1801年の著書『Disquisitiones Arithmeticae（整数論研究）』で合同記号 ≡ を導入し、数論を体系化しました。数論を「数学の女王」と呼んだ人物の代表的な道具です。
前提概念
確認問題
25 mod 7 はいくつですか？（25 を 7 で割った余り）
- 3
- 4✓
- 5
- 11
練習
17 mod 5 を計算しましょう。
答え: 2
- 17 = 3·5 + 2
- 余りは 2
ポイント: a mod n は、n で割ったときの余りです。
(7 + 8) mod 12 を計算しましょう。
答え: 3
- 7 + 8 = 15
- 15 mod 12 = 3（一周してから 3）
ポイント: 時計算——12を超えたら 0 からやり直す。
(4 × 6) mod 5 を計算しましょう。
答え: 4
- 4 × 6 = 24
- 24 = 4·5 + 4、余り 4
ポイント: 掛け算も余りのまま成り立ちます。
今日が月曜日なら、100日後は何曜日ですか？（mod 7 を使う）
答え: 1
- 100 mod 7 = 2（98 = 14·7 なので、余り 2）
- 月曜日 + 2日 = 水曜日
ポイント: 曜日は mod 7——7日ごとに最初に戻ります。