Арифметика за модулем — це арифметика на колі. Два числа конгруентні за модулем n, якщо вони відрізняються на кратне n. Годинник виконує арифметику за модулем 12: через 10 годин після 5-ї буде 3, а не 15. Ця проста ідея лежить в основі всієї сучасної криптографії, хеш-функцій, кодів виправлення помилок і значної частини теорії чисел.
У кожному рядку й стовпці множина {0,1,2,3,4} з’являється рівно один раз. П’ять елементів утворюють замкнену групу щодо додавання за модулем 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 за модулем n, якщо n ділить a − b. Гаус систематизував її у 1801 році. Вона лежить в основі всієї сучасної криптографії з відкритим ключем: шифрування RSA спирається на малу теорему Ферма, яка стверджує, що a^(p-1) конгруентне 1 за модулем p для будь-якого простого p, що не ділить a. Хеш-функції використовують операції за модулем, щоб відображати великі входи у виходи фіксованого розміру. Цілі числа за модулем n утворюють повне кільце, а коли n — просте, скінченне поле.