2.2.4. Арифметика остатков

Определения и обозначения

Остаток от деления — число, показывающее, что остаётся после выделения целого числа групп делителя. Например, при делении 17 на 5 можно выделить три пятёрки, а остаток равен 2. Остаток нужен, когда важно узнать, сколько единиц не вошло в полные группы.

Деление с остатком — представление числа в виде a = bq + r при условии 0 ≤ r < b, где b — делитель, q — частное, r — остаток. Например, 17 = 5 · 3 + 2. Такая запись точно показывает, сколько полных групп получилось и что осталось.

Сравнение по модулю — запись a ≡ b (mod n), означающая, что числа имеют одинаковый остаток при делении на n. Например, 17 ≡ 5 (mod 12), потому что оба числа дают остаток 5. Это обозначение позволяет заменять число другим, более удобным для вычислений.

Класс вычетов — множество чисел, дающих один и тот же остаток при делении на выбранный модуль. По модулю 5 числа 2, 7 и 12 относятся к одному классу, поскольку у каждого остаток 2. Классы вычетов помогают группировать числа по общему свойству, не перечисляя их по одному.

Как это устроено

Остаток всегда меньше делителя: если бы остаток оказался равен делителю или был больше него, из него можно было бы выделить ещё одну полную группу. Тогда частное увеличилось бы на 1, а остаток уменьшился бы на делитель. Представление a = bq + r единственно, потому что при фиксированных a и b есть только одно число полных групп и один остаток меньше b. Например, для 17 и 5 это 3 группы и остаток 2, а не другой допустимый набор.

Если два числа дают одинаковый остаток при делении на n, то при вычитании этих чисел остатки уничтожаются. Поэтому разность делится на n: например, 17 − 5 = 12. И наоборот, если разность чисел делится на n, при делении на n числа отличаются на целое число полных групп, а их остатки совпадают. Значит, запись a ≡ b (mod n) равносильна условию, что a − b делится на n.

Пусть a = nq + r, а c = nk + s, где r и s — остатки. При сложении получаем a + c = n(q + k) + (r + s), поэтому для остатка суммы важны только r и s. При вычитании получается разность остатков; если она отрицательна, к ней можно прибавить модуль, чтобы получить допустимый остаток. После действия результат всегда приводят к числу от 0 до n − 1. Так большие слагаемые заменяются небольшими остатками.

Для произведения можно подставить записи a = nq + r и c = nk + s. В произведении все слагаемые, кроме rs, содержат множитель n и потому делятся на n; остаток определяется произведением rs. Например, вместо умножения больших чисел достаточно перемножить их остатки и сократить результат по модулю. Этот приём особенно полезен, когда полное произведение трудно или долго вычислять.

Последняя цифра числа — это его остаток при делении на 10, а признаки делимости часто тоже связаны с остатками. Например, число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. При возведении числа в степень остатки часто начинают повторяться: после повторения одного и того же остатка цикл продолжается. Поэтому для очень большого показателя достаточно определить его место в цикле, а не вычислять всю степень.

Основные правила арифметики остатков

Сначала выбери модуль, на который нужно делить, а затем замени исходные числа их остатками. После сложения, вычитания или умножения обязательно приведи результат к одному из чисел от 0 до n − 1. При делении и сокращении сначала проверь дополнительные условия: эти действия не всегда сохраняют сравнение.

Разбор задач

Остаток суммы

Найти остаток от деления суммы 738 + 465 на 7, заменив слагаемые их остатками. Нет необходимости складывать исходные числа: остаток суммы определяется остатками слагаемых. Найдём их по отдельности, сложим и проверим, помещается ли в результат ещё одна семёрка.

1. Найдём остаток 738 при делении на 7: 738 = 7 · 105 + 3, значит, остаток равен 3.
2. Найдём остаток 465: 465 = 7 · 66 + 3, значит, остаток тоже равен 3.
3. Сложим остатки: 3 + 3 = 6. Число 6 меньше 7, поэтому его уже не нужно сокращать.

Ответ: остаток равен 6. Проверка: 738 + 465 = 1203, а 1203 = 7 · 171 + 6.

Остаток произведения

Найти остаток от деления произведения 12345 · 678 на 9, не выполняя полное умножение. Вместо больших множителей найдём их остатки при делении на 9, а затем перемножим эти остатки. Способ удобен тем, что произведение исходных чисел даже не требуется вычислять.

1. Для числа 12345 сумма цифр равна 1 + 2 + 3 + 4 + 5 = 15, а 15 при делении на 9 даёт остаток 6. Значит, 12345 ≡ 6 (mod 9).
2. Для числа 678 сумма цифр равна 6 + 7 + 8 = 21, а 21 при делении на 9 даёт остаток 3. Значит, 678 ≡ 3 (mod 9).
3. Перемножим остатки: 6 · 3 = 18. Так как 18 делится на 9, остаток равен 0.

Ответ: остаток равен 0. Следовательно, произведение делится на 9.

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

Найти последнюю цифру числа 7²⁰²⁴. Последняя цифра — это остаток по модулю 10, поэтому будем находить остатки последовательных степеней числа 7. Чтобы не вычислять огромные степени, проследим, через сколько шагов остатки начнут повторяться.

1. Вычислим первые остатки: 7¹ даёт 7, 7² = 49 даёт 9, 7³ = 343 даёт 3, 7⁴ = 2401 даёт 1.
2. При умножении на 7 цикл повторяется: дальше остатки снова идут 7, 9, 3, 1. Длина цикла равна 4.
3. Разделим показатель 2024 на 4: 2024 = 4 · 506. Остатку соответствует четвёртое место в цикле, то есть 1.

Ответ: последняя цифра числа 7²⁰²⁴ — 1. Проверка рассуждения: каждый блок из четырёх умножений возвращает остаток 1, а 2024 делится на 4 без остатка.

Типичные ошибки

Некоторые записывают остаток, равный делителю или больший него. Так происходит, когда остаток принимают за любую часть, не вошедшую в записанные группы; на деле в нём уже могут скрываться дополнительные полные группы. Проверь деление: должно выполняться 0 ≤ r < b, а равенство a = bq + r должно быть точным.

После сложения или умножения остатков иногда оставляют результат больше модуля. Ошибка возникает потому, что забывают: результат действия ещё не обязательно является остатком. Раздели его на модуль и возьми остаток; например, при вычислении по модулю 7 число 10 нужно заменить на 3.

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

Деление в сравнении по модулю нельзя выполнять так же свободно, как в равенстве. Причина в том, что множитель может иметь общий делитель с модулем, и тогда деление меняет множество возможных остатков. Например, по модулю 8 сравнение 2 · 1 ≡ 2 · 5 (mod 8) верно, но после сокращения двойки получилось бы неверное сравнение 1 ≡ 5 (mod 8). Проверяй взаимную простоту сокращаемого множителя и модуля.

Связь с другими темами

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

Что запомнить

• При делении a на b число представляют как a = bq + r, где 0 ≤ r < b.
• Два числа сравнимы по модулю n тогда и только тогда, когда их разность делится на n.
• Остаток суммы определяется остатками слагаемых.
• Остаток произведения определяется остатками множителей.
• После действий результат нужно заменить единственным остатком от 0 до n − 1.
• Остатки степеней часто образуют периодический цикл.
• Арифметика остатков позволяет заменять большие числа более простыми без изменения искомого остатка.