Переход к остаткам позволяет решать задачи, в которых «в лоб» пришлось бы делать огромные вычисления.
Дни недели повторяются каждые 7 дней: день недели — это остаток от деления номера дня на 7. Пример. 1 сентября 2026 года — вторник. Какой день недели 1 июня 2027 года? С 1 сентября до 1 июня проходит 30 + 31 + 30 + 31 + 31 + 28 + 31 + 30 + 31 = 273 дня, 273 ≡ 0 pmod 7 — тоже вторник.
Остатки степеней. Найдём остатки от деления на 7 степеней числа 3: 3¹ ≡ 3, 3² = 9 ≡ 2, 3³ ≡ 3 · 2 = 6, 3⁴ ≡ 3 · 6 = 18 ≡ 4, 3⁵ ≡ 12 ≡ 5, 3⁶ ≡ 15 ≡ 1, 3⁷ ≡ 3, … Остатки 3, 2, 6, 4, 5, 1 повторяются с периодом 6.
Теорема о периодичности остатков. Для любых натуральных a и m остатки от деления a, a², a³, … на m с некоторого момента начинают периодически повторяться — как только появится остаток, который уже встречался.
Пример. Остаток от деления 332²²³ на 7: 332 ≡ 3, значит, 332²²³ ≡ 3²²³; 223 = 6 · 37 + 1, поэтому 3²²³ ≡ 3¹ = 3 pmod 7.
Признаки делимости. 10 ≡ 1 pmod 9, поэтому число сравнимо с суммой своих цифр по модулю 9 (и по модулю 3). 10 ≡ -1 pmod11, поэтому число делится на 11 тогда и только тогда, когда разность сумм его цифр на чётных и на нечётных местах делится на 11. Пример. 918 082: (9 + 8 + 8) - (1 + 0 + 2) = 22 — делится на 11.
Последняя цифра числа — его остаток от деления на 10: последние цифры степеней тоже повторяются.