Арифметика остатков: что можно делать по модулю и чего нельзя

Если ты объяснишь, почему остаток произведения считается по остаткам множителей, откуда берётся признак делимости на 9 и почему по модулю 6 нельзя сокращать на 2, - листай до «Теперь сам».

Как думаешь, нужно ли считать 2568 цифр

1000! - произведение всех чисел от 1 до 1000 - занимает 2568 десятичных цифр. Прошлая глава показала, сколько стоит такое число: список разрядов и проход по нему на каждом умножении.

Теперь пусть само число не нужно, а нужен его остаток от деления на 1 000 003. Прежде чем читать дальше, ответь себе: обязательно ли сначала получить все 2568 цифр, а потом делить? Или остаток можно узнать, ни разу не увидев числа длиннее десяти цифр?

На что это похоже

Представь циферблат. Сейчас десять часов, через пять часов будет три - стрелка прошла через двенадцать и начала заново. Через сто часов будет два: стрелка сделала восемь полных оборотов и ещё четыре часа, и обороты для ответа не важны.

Циферблат не помнит, сколько раз стрелка обошла круг. Он хранит только положение на круге - остаток. И чтобы узнать, где стрелка окажется, складывать можно прямо положения: десять плюс четыре - четырнадцать, это два.

Механизм: почему остатков достаточно

Любое число раскладывается на целое число оборотов и остаток: a = q · m + r, где 0 ≤ r < m. Число m называют модулем; запись a mod m без скобок - действие: остаток от деления a на m. Два числа сравнимы по модулю m, если остатки у них одинаковые; пишут a ≡ b (mod m). То же самое другими словами: разность a − b делится на m. 17 ≡ 2 (mod 5), потому что 17 − 2 = 15.

Возьмём два числа: a = q₁ · m + r₁ и b = q₂ · m + r₂.

a + b = (q₁ + q₂) · m + (r₁ + r₂)
a · b = (q₁q₂m + q₁r₂ + q₂r₁) · m + r₁ · r₂
        └────── всё, что делится на m ──────┘   └ то, что решает остаток

В обеих строках первое слагаемое делится на m и на остаток не влияет. Значит остаток суммы - это остаток от r₁ + r₂, а остаток произведения - остаток от r₁ · r₂. Обороты можно выбросить до действия, а не после.

Это и есть причина, по которой в формулах раздела стоит именно остаток, а не «обрежем число до последних цифр как-нибудь»: остаток - единственный способ укоротить число, который переживает сложение и умножение.

С делением так не выходит. Вот таблицы умножения ненулевых остатков по модулям 6 и 7:

mod 6    1  2  3  4  5          mod 7    1  2  3  4  5  6
  1      1  2  3  4  5            1      1  2  3  4  5  6
  2      2  4  0  2  4            2      2  4  6  1  3  5
  3      3  0  3  0  3            3      3  6  2  5  1  4
  4      4  2  0  4  2            4      4  1  5  2  6  3
  5      5  4  3  2  1            5      5  3  1  6  4  2
                                  6      6  5  4  3  2  1

По модулю 7 в каждой строке все остатки встречаются по одному разу. По модулю 6 в строках 2, 3 и 4 есть нули и повторы: 2 · 3 = 0, 2 · 1 = 2 · 4. Спросить «на что умножили двойку, чтобы получить 2» нельзя - ответов два. Разделить на 3 единицу нельзя вовсе: в строке тройки единицы нет.

Правило

Если a ≡ a' и b ≡ b' по модулю m, то a + b ≡ a' + b', a − b ≡ a' − b' и a · b ≡ a' · b'. Поэтому в выражении из сложений, вычитаний и умножений остаток можно брать после любого действия, и ответ не изменится. Делить и сокращать по модулю в общем случае нельзя: из a · c ≡ b · c не следует a ≡ b. Остатки не упорядочены: из a mod m < b mod m ничего не следует про a и b.

Разбор: остаток факториала без факториала

r = 1
i = 2
while i <= 1000:
    r = r * i % 1000003
    i = i + 1
print(r)

Умножение и остаток в Python равноправны и выполняются слева направо: сначала r * i, потом остаток. Печатает 864722, шагов 3001 - по три на виток. Перед каждым умножением r меньше 1 000 003, множитель не больше 1000, произведение меньше 1,1 · 10⁹. Ответ на вопрос из начала: ни одного длинного числа не понадобилось.

Сравни с прошлой главой: там само число пришлось бы держать списком разрядов и проходить его целиком на каждом из тысячи умножений. Здесь цена линейна, потому что длина чисел заперта модулем.

Разбор: признак делимости на 9 и чего он стоит

Школьное правило: число делится на 9, если сумма его цифр делится на 9. Теперь видно, откуда оно. 10 ≡ 1 (mod 9), значит и 100 = 10 · 10 ≡ 1, и любая степень десяти сравнима с единицей. Число 4 · 100 + 2 · 10 + 8 сравнимо с 4 + 2 + 8. Сумма цифр - это и есть число, посчитанное по модулю 9.

Отсюда старая бухгалтерская проверка умножения. 123 456 · 654 321 = 80 779 853 376. Суммы цифр множителей: 21 и 21, по модулю 9 это 3 и 3, произведение 9, то есть 0. Сумма цифр результата: 63, по модулю 9 это 0. Сошлось. Если бы в результате была ошибка в одной цифре, остаток почти наверняка получился бы другим.

«Почти» - и есть граница приёма. Проверка по модулю 9 не видит перестановку цифр: сумма та же. И не видит ошибку ровно на 9. Из всех неверных ответов она пропускает примерно каждый девятый. Совпадение остатков - не доказательство равенства, а несовпадение - доказательство неравенства; тот же принцип был у хешей в Рабине-Карпе.

Теперь про сокращение. 2 · 3 ≡ 2 · 0 (mod 6): слева 6, справа 0, остатки равны. Сократи двойку - получится 3 ≡ 0 (mod 6), неправда. Сокращение на c - это деление на c, а таблица выше показала, что по модулю 6 на двойку делить нельзя. По модулю 7 то же сокращение законно при любом ненулевом c.

Что ломается без этого

Первое: остаток взят поздно. r = r * i в цикле и % m в самом конце - числа успевают вырасти. В Python это тихо превращает линейную программу в квадратичную, в C - в переполнение, на тренажёре - в ошибку точности.

Второе: произведение двух остатков не помещается в тип. Остатки меньше m, произведение - до m². При m около миллиарда это 10¹⁸: в 64 бита входит, в 53 бита точности тренажёра и JavaScript - нет. Правило: модуль не больше корня из предела типа. На тренажёре это 94 906 265.

Третье: деление посреди формулы. Число сочетаний - это n! / (k! · (n − k)!). Посчитать три факториала по модулю и поделить один остаток на другие нельзя: получится другое число или дробь.

Четвёртое: отрицательный остаток. В Python -7 % 5 равно 3, в C, Java и JavaScript - -2. Формулы с вычитанием при переносе на другой язык надо завершать (x % m + m) % m.

Пятое: сравнение остатков. a % m < b % m не говорит, что a < b. По остаткам нельзя искать наибольшее и нельзя сортировать.

Зачем это в работе

Индекс в хеш-таблице - остаток хеша от деления на число ячеек. Выбор сервера для пользователя - user_id % N. Следующая позиция в кольцевом буфере - (i + 1) % n. Всё это та же арифметика на круге.

Контрольные цифры. Последняя цифра штрихкода подобрана так, чтобы сумма всех цифр, в которой каждая вторая цифра взята с множителем 3, делилась на 10. Номер банковского счёта в формате IBAN проверяется остатком от деления на 97: правильный номер даёт единицу. Касса и банк ловят опечатку до того, как пойдут искать товар или счёт.

Счёт вариантов. Число способов что-то сделать быстро перерастает любой тип, и в задачах просят ответ по модулю - обычно большого простого числа. Простого - затем, что по простому модулю можно делить, и про это два следующих урока.

Криптография. Все действия RSA и обмена ключами - умножения по модулю длиной в тысячи бит. Модуль держит длину чисел постоянной, и поэтому счёт «сколько умножений» там честен.

Теперь сам

1. Найди 17 · 23 mod 5, не перемножая 17 и 23.
2. Делится ли 123 456 789 на 9? А на 3?
3. По модулю 6 найди x, отличный от 1, для которого 4 · x ≡ 4. Что это говорит о сокращении на 4?
4. Чему равно -7 % 5 в Python и в C?