§ 12. Сравнения. Перебор остатков

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

Сравнением по модулю называют равенство остатков при делении двух целых чисел на одно и то же натуральное число. Записывают это так: a ≡ b (mod m). Например, 17 ≡ 5 (mod 12), потому что оба числа при делении на 12 дают остаток 5. Такая запись позволяет говорить об одинаковом поведении чисел при делении, даже если сами числа различны.

Модуль сравнения — натуральное число m, по которому сравнивают остатки. Условие a ≡ b (mod m) равносильно тому, что разность a − b делится на m. Например, разность 17 − 5 равна 12 и делится на 12. Проверка делимости разности часто быстрее, чем отдельное деление обоих чисел.

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

Система вычетов — набор чисел, представляющий все возможные остатки по заданному модулю. Для модуля 4 такой системой служат числа 0, 1, 2, 3. Каждый целый аргумент можно заменить одним из них, поэтому система вычетов становится основой полного перебора в задачах.

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

При делении с остатком целое число a представляется как a = qm + r, где q — целое частное, а 0 ≤ r < m. Если два числа имеют одинаковый остаток r, то их разность равна разности соответствующих кратных m и потому делится на m. И наоборот, если a − b делится на m, числа отличаются на целое число полных групп по m, так что остатки у них совпадают. Поэтому сравнение можно проверять либо по остаткам, либо по делимости разности.

При переборе достаточно взять остатки от 0 до m − 1, потому что деление с остатком даёт именно один из этих вариантов. Любое целое n можно записать как n = qm + r, и тогда n сравнимо с r по модулю m. Если выражение состоит из сложений, вычитаний и умножений, замену аргумента на r можно перенести на всё выражение. Так бесконечное множество целых значений сводится к конечному набору проверок.

Сравнения сохраняются при сложении и вычитании, потому что разность результатов будет суммой или разностью чисел, кратных модулю. При умножении разность произведений тоже делится на модуль: если a ≡ b и c ≡ d, то ac − bd = a(c − d) + d(a − b). Каждое слагаемое справа делится на m, значит, делится и вся разность. Поэтому можно заменять числа их остатками до вычисления суммы, разности или произведения.

Чтобы исследовать выражение по модулю m, сначала перечисляют все остатки аргумента 0, 1, …, m − 1, а затем подставляют каждый из них. Получившиеся значения можно снова заменить остатками по тому же модулю. Если для всех вариантов выражение даёт остаток 0, оно делится на m при любом целом аргументе. Перебор доказывает утверждение именно потому, что список включает все возможные классы чисел по выбранному модулю.

С делением в сравнениях нужно быть осторожным: оно не является обычным сокращением равных множителей. Без изменения модуля множитель разрешено сократить, если он взаимно прост с модулем, то есть не имеет с ним общих делителей, кроме 1. Если множитель имеет общий делитель с модулем, сокращение может дать неверное сравнение. Например, 2 ≡ 8 (mod 6), но 1 и 4 не сравнимы по модулю 6.

Основные действия со сравнениями

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

Разбор задач

Проверить, верно ли сравнение 47 ≡ 5 (mod 7)

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

1. Вычислим разность: 47 − 5 = 42.
2. Проверим делимость разности на модуль: 42 = 7 · 6, значит, 42 делится на 7.
3. По критерию сравнимости получаем 47 ≡ 5 (mod 7). Для проверки остатками: 47 = 7 · 6 + 5, а число 5 при делении на 7 тоже имеет остаток 5.

Ответ: сравнение верно. Оба способа приводят к одному выводу: остатки совпадают, а разность делится на модуль.

Найти остаток от деления 3⁸ на 7

Большую степень можно не вычислять целиком: после каждого умножения заменяем результат его остатком по модулю 7. Так числа остаются небольшими, но сравнение с исходной степенью сохраняется. Начнём с первых степеней числа 3.

1. Имеем 3¹ ≡ 3 (mod 7) и 3² ≡ 9 ≡ 2 (mod 7).
2. Умножаем сравнимые остатки: 3³ ≡ 2 · 3 = 6 (mod 7), затем 3⁴ ≡ 6 · 3 = 18 ≡ 4 (mod 7).
3. Продолжаем цикл: 3⁵ ≡ 4 · 3 = 12 ≡ 5, 3⁶ ≡ 5 · 3 = 15 ≡ 1 (mod 7).
4. Поскольку 3⁶ ≡ 1 (mod 7), получаем 3⁸ = 3⁶ · 3² ≡ 1 · 2 ≡ 2 (mod 7).

Ответ: остаток равен 2. Проверка опирается на умножение сравнений, поэтому каждое промежуточное сокращение числа до остатка законно.

Доказать, что n³ − n делится на 6 при любом целом n

По модулю 6 любой целый n сравним с одним из остатков 0, 1, 2, 3, 4, 5. Достаточно подставить все шесть значений в n³ − n и проверить, что результат сравним с нулём по модулю 6. Это полный перебор, так как других остатков при делении на 6 нет.

1. При остатке 0 выражение даёт 0³ − 0 = 0.
2. При остатках 1 и 5 получаем 1³ − 1 = 0 и 5³ − 5 = 120, что делится на 6.
3. При остатках 2 и 4 получаем 2³ − 2 = 6 и 4³ − 4 = 60, оба числа делятся на 6.
4. При остатке 3 получаем 3³ − 3 = 24, также кратное 6. Значит, для каждого возможного остатка выражение сравнимо с нулём по модулю 6.

Ответ: n³ − n делится на 6 при любом целом n. Замена n его остатком не меняет значение выражения по модулю 6, поэтому проверка шести случаев доказывает утверждение для всех целых чисел.

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

Сравнение иногда принимают за обычное равенство и решают, что сравнимые числа должны совпадать. Это происходит из-за знака ≡, похожего на знак равенства, но числа могут отличаться на ненулевое кратное модуля. Например, 12 ≡ 2 (mod 5), хотя 12 и 2 — разные числа. Проверяй, делится ли их разность на указанный модуль.

Другая ошибка — не указать модуль или незаметно заменить его во время решения. Сравнимость всегда относится к конкретному m: одни и те же числа могут быть сравнимы по одному модулю и не быть сравнимыми по другому. Это забывают, когда переходят между вычислениями и записывают только знак ≡. Каждый раз указывай mod m и сверяй, что модуль не изменился без объяснения.

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

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

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

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

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

• a ≡ b (mod m) тогда и только тогда, когда m делит a − b.
• Сравнимые числа имеют одинаковый остаток при делении на модуль.
• По модулю m достаточно рассматривать остатки 0, 1, …, m − 1.
• Сравнения можно складывать, вычитать и перемножать.
• Перебор остатков требует проверить каждый остаток по выбранному модулю.
• Сокращать множитель в сравнении можно только при соблюдении условий.