Модульная арифметика — это арифметика на круге. Два числа сравнимы по модулю n, если они отличаются на кратное n. Часы работают по модулю 12: десять часов после 5 часов — это 3 часа, а не 15. Именно поэтому модульную арифметику часто называют арифметикой часов.
Каждая строка и каждый столбец содержат {0,1,2,3,4} ровно по одному разу. Пять элементов образуют замкнутую группу относительно сложения по модулю 5. Красным отмечены суммы, которые превышают 4 и «переворачиваются» обратно.
| + | 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 году в книге Disquisitiones Arithmeticae. По модулю простого числа p выполняется малая теорема Ферма: a^(p-1) ≡ 1 (mod p), если p не делит a. Модульная арифметика лежит в основе RSA-шифрования, циклических кодов, хеш-функций и генераторов псевдослучайных чисел.