合同算術は円の上の算術である。2 つの数が n を法として合同であるとは、その差が n の倍数であることを意味する。時計は mod 12 の計算をしており、5時の10時間後は 15 ではなく 3 になる。この単純な考え方が、現代暗号、ハッシュ関数、誤り訂正符号、そして数論の大部分の基礎にある。
各行と各列には {0,1,2,3,4} がちょうど一度ずつ現れる。5 個の元は mod 5 の加法について閉じた群をなす。赤は 5 以上になって巻き戻る和を示す。
| + | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
合同算術は合同関係を定義する。a と b が mod n で合同であるとは、n が a-b を割り切ることである。ガウスは 1801 年にこれを体系化した。現代の公開鍵暗号の基盤であり、RSA 暗号はフェルマーの小定理、すなわち a を割らない素数 p に対して a^(p-1) ≡ 1 (mod p) が成り立つことに依拠している。ハッシュ関数は巨大な入力を固定長の出力へ写すために合同演算を使う。mod n の整数全体は環をなし、n が素数なら有限体になる。