Арифметика по модулю простыми словами (Часы и почему все решает остаток)

Стрелка показывает девять, а самолет вылетает через пять часов. Никто не отвечает «в четырнадцать». Вы говорите «в два», причем делаете это не задумываясь, потому что на циферблате четырнадцати нет. Часы заворачиваются на двенадцати и начинают отсчет заново. Арифметикой по модулю вы занимаетесь с того дня, как научились понимать время по часам, просто обозначений вам никто не показывал.

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

Эта статья и есть картинка: что такое остаток на самом деле, почему вам разрешено сокращать числа до вычисления, что происходит с отрицательными числами и со степенями и откуда берется единственная честная трудность, деление.

Остаток это место, куда вы попали, а не то, что осталось

Обычное определение говорит, что $a \bmod n$ это остаток от деления $a$ на $n$. Это верно, и это же является причиной, по которой тема кажется повинностью: слово «остаток» звучит как обрезок, оставшийся после деления, как нечто второстепенное.

Картинка лучше: круговая дорожка, на ней $n$ меток, занумерованных от $0$ до $n-1$. Чтобы найти $a \bmod n$, встаньте на $0$ и пройдите по дорожке $a$ шагов. Место остановки и есть ответ. Пройти 17 шагов по дорожке с 5 метками значит обойти ее три полных раза (15 шагов) и сделать еще 2 шага, поэтому вы останавливаетесь на метке 2. Отсюда $17 \bmod 5 = 2$. Полные круги это частное, а место остановки это остаток.

Эта картинка делает две вещи, которых определение не делает. Остаток у нее всегда попадает в промежуток от $0$ до $n-1$, ведь других меток просто нет. И она объясняет, почему два числа могут быть «одним и тем же» по модулю $n$, даже если они дико различаются: $2$, $17$, $102$ и $5{,}000{,}002$ на дорожке с 5 метками останавливаются на метке 2. Они отличаются кругами, а дорожка круги не запоминает.

Математики записывают эту мысль как сравнение:

$$17 \equiv 2 \pmod{5}$$

Читайте так: «17 останавливается там же, где 2, на дорожке с 5 метками». Тройная черта это не знак равенства, потому что 17 и 2 не равны. Она говорит, что эти числа взаимозаменяемы для любого вопроса, которому важно только положение на дорожке. Точная формулировка: $a \equiv b \pmod{n}$ означает, что $n$ делит $a - b$, а это всего лишь другой способ сказать, что два числа отличаются на целое число кругов.

Сложение и умножение интересует только то, где вы стоите

Вот факт, который превращает арифметику по модулю в инструмент, а не в диковинку. Если вы собираетесь сложить два числа и затем взять остаток, можно взять остатки сначала, сложить их и сократить снова. Ответ получится тот же самый. То же верно для вычитания и умножения.

На дорожке это очевидно. Прибавить 17 значит пройти 17 шагов, то есть три круга плюс 2 шага. Три круга возвращают вас туда, откуда вы вышли, и ничего не меняют, поэтому прибавить 17 и прибавить 2 это ровно одно и то же. Круги, спрятанные внутри числа, являются балластом, и они остаются балластом и при сложении, и при умножении, потому что кратное $n$, умноженное на что угодно, остается кратным $n$.

Если выписать, взяв $a = qn + r$ и $b = pn + s$:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

Все, что стоит в первой скобке, это круги. Уцелевает только $rs$, поэтому $ab \bmod n$ равно $rs \bmod n$. Остатки несут всю информацию, которая нужна для ответа.

Именно поэтому подсказка в модуле арифметики Math Zen советует сокращать шаг за шагом, а не считать полное значение. Допустим, вам нужно $123 \times 456 \bmod 7$. Можно перемножить до 56,088 и поделить в столбик на 7. А можно заметить, что $123 = 119 + 4$, значит $123 \equiv 4$, и $456 = 455 + 1$, значит $456 \equiv 1$, и ответ равен $4 \times 1 = 4$. Два маленьких сокращения заменяют умножение четырехзначных чисел. Привычка такая: не давайте числу вырасти больше $n$, если вам нужен только его остаток.

Отрицательные числа идут в другую сторону

Картинка с дорожкой справляется и с тем случаем, на котором спотыкается большинство. Чему равно $-3 \bmod 5$?

Пройдите от 0 три шага назад по дорожке с 5 метками. Вы минуете 4, затем 3 и попадаете на 2. Значит, $-3 \equiv 2 \pmod{5}$. Отрицательное число это просто ход в обратную сторону, та же идея, что и в статье Отрицательные числа простыми словами, а остаток это по-прежнему место остановки, по-прежнему между $0$ и $n-1$.

Короткий путь: прибавляйте круги, пока число не станет положительным. $-3 + 5 = 2$. Для $-14 \bmod 5$ прибавьте 15 (три круга) и получите 1. Калькуляторы и языки программирования расходятся в том, каким должен быть отрицательный остаток, и некоторые выдают $-4$ для $-14 \bmod 5$, поэтому на контрольной всегда называйте ответом неотрицательную метку на дорожке, а соглашение своего калькулятора проверяйте прежде, чем ему доверять.

С вычитанием та же история. $3 - 8 \pmod{5}$ равно $-5$, то есть ровно один круг назад, поэтому ответ 0. Или сократите сначала: $8 \equiv 3$, значит $3 - 3 = 0$.

Последняя цифра огромной степени

Это та задача, которая убеждает людей, что тему стоит знать, и она является прямым следствием правила сокращать заранее.

Последняя цифра числа это число по модулю 10, потому что десятки, сотни и все, что выше, кратны 10 и возвращаются на 0 на дорожке с 10 метками. Поэтому вопрос «какая последняя цифра у $7^{100}$» это вопрос «чему равно $7^{100} \bmod 10$», и считать $7^{100}$ не придется никогда.

Вместо этого посмотрим, как степени 7 шагают по дорожке с 10 метками, сокращаясь каждый раз:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

Как только вы попали в 1, цикл начинается заново: 7, 9, 3, 1, 7, 9, 3, 1, с периодом 4. Поскольку $100 = 4 \times 25$, сотая степень стоит в конце полного цикла, на том же месте, что и $7^4$, и ее последняя цифра равна 1.

У каждого основания есть свой цикл по модулю 10, и почти все они короткие. Степени 2 идут по кругу 2, 4, 8, 6. Степени 3 по кругу 3, 9, 7, 1. Степени 5 и 6 не двигаются вовсе. Метод всегда один: найдите длину цикла, сокращая по ходу дела, поделите показатель на длину цикла, и остаток от этого деления скажет, в каком месте цикла вы стоите. Это та же идея степеней как повторного умножения, только запущенная по круговой дорожке, а не по прямой.

Почему работает признак делимости на 9 по сумме цифр

Всех учат, что число делится на 9, если его цифры в сумме дают кратное 9, и почти никому не объясняют, почему. Арифметика по модулю превращает это в рассуждение на одну строку.

Десять это круг плюс один на дорожке с 9 метками: $10 \equiv 1 \pmod{9}$. Тогда $100 = 10 \times 10 \equiv 1 \times 1 = 1$, и любая степень десяти тоже сравнима с 1. Поэтому число вида $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ сравнимо с $4 + 5 + 2 + 7 = 18 \pmod{9}$, а 18 это $0$ на дорожке с 9 метками, поэтому 4,527 делится на 9. Сумма цифр это не фокус. Это само число, увиденное по модулю 9.

Признак для 3 работает по той же причине, ведь $10 \equiv 1 \pmod{3}$ тоже. Признак для 11 берется из $10 \equiv -1 \pmod{11}$, из-за чего степени десяти чередуются между $1$ и $-1$, и получается знакочередующаяся сумма цифр. Все признаки делимости, которые вам велели выучить, это один факт, «сократите степени десяти», примененный к разным дорожкам.

Контрольные цифры: арифметика по модулю в вашем кошельке

Каждый ISBN, каждый номер банковской карты и каждый штрихкод заканчиваются цифрой, единственная работа которой состоит в том, чтобы быть остатком.

Последняя цифра тринадцатизначного ISBN выбирается так, чтобы взвешенная сумма всех тринадцати цифр, с весами, чередующимися 1 и 3, была сравнима с $0 \pmod{10}$. Ошибитесь в одной цифре, и сумма окажется в другом месте дорожки с 10 метками, а сканер ее отвергнет. Банковские карты используют алгоритм Луна, чуть более хитрое взвешивание, которое вдобавок ловит большинство случаев, когда две соседние цифры переставлены местами, и снова за счет проверки суммы по модулю 10.

Это скромные родственники гораздо более крупного применения. Современное шифрование опирается на то, что возвести число в степень по модулю очень большого $n$ легко, а обратить этот процесс без секретного ключа нет. Поиск цикла, который вы проделали выше для $7^{100}$, это та же самая операция, только поднятая до чисел с сотнями знаков, и правило сокращать по ходу дела является единственной причиной, по которой ее вообще можно вычислить.

Деление это место, где дорожка становится неровной

Сложение, вычитание и умножение ведут себя на дорожке в точности так же, как на числовой прямой. Деление нет, и именно здесь тема оправдывает свою репутацию.

На обычной числовой прямой поделить на 4 значит умножить на $\tfrac{1}{4}$, на то число, которое в произведении с 4 дает 1. Есть ли на дорожке с 12 метками метка, которая в произведении с 4 попадает на 1? Переберем все: $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$, и набор 4, 8, 0 повторяется до бесконечности. На 1 он не попадает никогда. Значит, на дорожке с 12 метками деления на 4 просто не существует.

Причина в том, что у 4 и 12 есть общий делитель. Возьмите кратное 4, добавьте или уберите круги по 12, и у вас все равно останется кратное 4, поэтому попасть на 1 дальше кратного 12 невозможно. Попробуйте вместо нее 5: $5 \times 5 = 25 = 24 + 1 \equiv 1$, значит, 5 обратна самой себе на дорожке с 12 метками, и делить на 5 можно спокойно. Правило такое: у $a$ есть обратный элемент по модулю $n$ ровно тогда, когда у $a$ и $n$ нет общего делителя, кроме 1.

У этого правила есть яркое следствие. Если $n$ простое, то ни одно число от $1$ до $n - 1$ не имеет с ним общего делителя, поэтому обратный элемент есть у каждой ненулевой метки и делить можно свободно. Простые дорожки это те, на которых работают все четыре действия, и это немалая часть причины, по которой простые числа, запас которых гарантирует бесконечность множества простых чисел, стоят в центре теории чисел и криптографии.

Откуда берутся ошибки

У арифметики по модулю мало подвижных частей, и ошибки соответственно вполне определенные.

Первая это сокращение показателя вместо основания. В $7^{100} \bmod 10$ вы можете сократить 7 по модулю 10 (оно уже сокращено) и можете сократить показатель по модулю длины цикла, как только эту длину узнаете, но не можете сократить 100 по модулю 10 и считать $7^0$. Показатели живут на другой дорожке, на той, размер которой равен длине цикла, и смешение двух дорожек является самой частой ошибкой в этой теме.

Вторая это отрицательный остаток. $-14 \bmod 5$ равно 1, а не $-4$. Положение на дорожке одно и то же, но общепринятое имя есть только у одного из них, и в ответах ждут неотрицательное.

Третья это деление без проверки обратного элемента. Сокращать общий множитель в обеих частях сравнения законно только тогда, когда у этого множителя нет ничего общего с модулем. Из $4 \times 2 \equiv 4 \times 5 \pmod{12}$, что верно, поскольку обе части равны 8, нельзя сократить 4 и заключить, что $2 \equiv 5$, а это неверно. Круги, которые вы выбрасываете при сокращении, обязаны быть кругами исходной дорожки.

Четвертая это забытое сокращение в конце. Получить $rs = 21$ на дорожке с 7 метками и написать 21 не то чтобы неправильно, но и ответом это не является. Ответ это метка на дорожке, а 21 это три круга, поэтому метка равна 0.

Где помогает Math Zen

В модуле арифметики Math Zen есть отдельный блок под арифметику по модулю, и прогрессия выстроена вокруг привычки сокращать заранее, а не вокруг обозначений. Первые задачи спрашивают простые остатки и сравнения с маленькими модулями, пока вопрос «куда я попадаю» не начнет решаться сам. Средние блоки подмешивают отрицательные числа и произведения, где смысл в том, чтобы сократить каждый множитель до умножения и назвать неотрицательный остаток. Поздние блоки это задачи на последнюю цифру и длину цикла, те самые, что встречаются на олимпиадных работах и вступительных испытаниях и что наказывают всякого, кто попробует вычислить степень целиком.

Поскольку занятия короткие, а задачи возвращаются через нарастающие промежутки, как описано в статье интервальное повторение в практике математики, поиск цикла становится рефлексом, а не процедурой, которую вы ищете в справочнике. У большинства людей нет пробела в арифметике по модулю, который закрыла бы глава учебника. У них есть одна картинка, дорожка, которую им никто не нарисовал, и около сорока повторений, которых никто не сделал.

Главный вывод

Арифметика по модулю это арифметика на круговой дорожке с $n$ метками. Остаток это место, куда вы попали, пройдя $a$ шагов, полные круги забываются, а два числа сравнимы, когда попадают на одну метку. Поскольку круги ничего не добавляют ни к суммам, ни к произведениям, каждое число можно сократить до его остатка прежде, чем складывать или умножать, и это единственное разрешение превращает неподъемные вычисления, вроде последней цифры $7^{100}$, в короткие циклы, которые можно проследить от руки. Признаки делимости это степени десяти, сокращенные по модулю 9, 3 или 11. Контрольные цифры это остатки, которые ловят опечатки. Деление работает только тогда, когда у числа нет общего делителя с дорожкой, и именно поэтому простые дорожки особые.

Когда задача по модулю встает, нарисуйте дорожку. Спросите, куда попадает каждая часть, сокращайте по ходу дела и держите показатель на его собственной дорожке. Ответ это метка между $0$ и $n - 1$, и картинка доведет вас до него раньше, чем формула.