§ 4. Сравнения

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

Запись a ≡ b (mod m) называется сравнением a и b по модулю m. Она означает, что разность a − b делится на m, то есть существует целое число k, для которого a − b = km. Например, 17 ≡ 5 (mod 6), потому что 17 − 5 = 12 делится на 6. Такое обозначение позволяет заменить одно число другим, если для задачи важен только остаток.

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

Класс вычетов по модулю m — это множество всех целых чисел, имеющих один и тот же остаток при делении на m. Например, класс остатка 2 по модулю 5 объединяет …, −8, −3, 2, 7, 12, … . Все числа этого класса отличаются друг от друга на число, делящееся на 5. Классов всего m: по одному для каждого остатка 0, 1, …, m − 1.

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

При делении целого числа на m остаток принимает одно из значений 0, 1, …, m − 1. Если два числа имеют одинаковый остаток r, их можно представить как a = qm + r и b = pm + r. Тогда a − b = (q − p)m, поэтому разность делится на m и числа сравнимы. Обратно, если a − b делится на m, числа отличаются на целое число полных групп по m, а остаток у них один и тот же. Так получается критерий: одинаковый остаток равносилен делимости разности.

Сравнения можно складывать и вычитать, потому что разности исходных пар делятся на m. Например, если a − b и c − d делятся на m, то и сумма (a + c) − (b + d), и разность (a − c) − (b − d) делятся на m. Для умножения разность ac − bd можно записать как c(a − b) + b(c − d). Оба слагаемых делятся на m, значит, делится и вся разность; потому ac ≡ bd (mod m).

Если a ≡ b (mod m), то a − b делится на m. Разность степеней aⁿ − bⁿ раскладывается на произведение (a − b)(aⁿ⁻¹ + aⁿ⁻²b + … + bⁿ⁻¹), поэтому она тоже делится на m. Значит, сравнение можно возвести в натуральную степень. Но из сравнения степеней нельзя всегда восстановить сравнение оснований: например, 1² ≡ 4² (mod 5), хотя 1 и 4 не сравнимы по модулю 5.

Для проверки делимости числа N на m достаточно показать, что N ≡ 0 (mod m). При вычислении остатка большого выражения числа заменяют меньшими сравнимыми с ними: например, 47 ≡ 2 (mod 5), поэтому вместо остатка от деления 47ⁿ на 5 можно рассматривать 2ⁿ. У степеней часто повторяются остатки, что позволяет сократить вычисления. Период нужно установить именно для выбранного модуля, а не предполагать заранее.

Из a ≡ b (mod m) можно получить ac ≡ bc (mod m), поскольку разность ac − bc равна c(a − b). Обратное сокращение множителя требует осторожности: из m | c(a − b) не всегда следует m | (a − b). Если НОД(c, m) = 1, то c и m взаимно просты, и тогда делимость произведения на m влечёт делимость второго множителя на m. Если НОД больше 1, сначала можно разделить сравнение и модуль на этот общий делитель, но полученное сравнение будет иметь меньший модуль.

Основные свойства сравнений по модулю m

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

Разбор задач

Проверить, сравнимы ли 47 и 11 по модулю 6.

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

1. Находим разность: 47 − 11 = 36.
2. Проверяем делимость: 36 = 6 · 6, значит, 36 делится на 6.
3. По критерию сравнения заключаем, что 47 ≡ 11 (mod 6).

Ответ: числа сравнимы по модулю 6. Проверка через остатки даёт тот же результат: оба числа при делении на 6 дают остаток 5.

Найти остаток от деления числа 7¹⁰⁰ на 5.

Большую степень напрямую вычислять неудобно. Вместо этого заменим основание числом с тем же остатком по модулю 5, а затем выясним, как повторяются остатки степеней. Такая замена сохраняет остаток всей степени, потому что сравнение можно возводить в натуральную степень.

1. Так как 7 ≡ 2 (mod 5), получаем 7¹⁰⁰ ≡ 2¹⁰⁰ (mod 5).
2. Вычислим первые остатки: 2¹ ≡ 2, 2² ≡ 4, 2³ ≡ 3, 2⁴ ≡ 1 (mod 5). Далее остатки повторяются с периодом 4, так как при умножении на 2 цикл начинается заново.
3. Поскольку 100 делится на 4, остаток 2¹⁰⁰ совпадает с остатком 2⁴, то есть равен 1.

Ответ: остаток равен 1. Здесь использована периодичность именно степеней 2 по модулю 5; при другом модуле цикл может быть другим.

Решить сравнение 6x ≡ 9 (mod 15).

Сразу сокращать 6 нельзя: НОД(6, 15) = 3, а не 1. При этом все три числа 6, 9 и 15 делятся на 3, поэтому можно разделить обе части и модуль на 3. После этого получим равносильное сравнение с меньшим модулем, где коэффициент при x уже взаимно прост с модулем.

1. Делим сравнение на 3 и получаем 2x ≡ 3 (mod 5).
2. Число 2 взаимно просто с 5. Умножаем обе части на 3, обратное к 2 по модулю 5, поскольку 2 · 3 = 6 ≡ 1 (mod 5).
3. Получаем x ≡ 9 ≡ 4 (mod 5).

Ответ: x ≡ 4 (mod 5). Если нужны решения по модулю 15, это x ≡ 4, 9 или 14 (mod 15): каждое из этих чисел имеет остаток 4 при делении на 5.

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

Сравнение иногда принимают за равенство, потому что знак ≡ напоминает знак =. Но равенство требует совпадения самих чисел, а сравнение — только делимости разности на указанный модуль. Например, 17 и 5 не равны, но сравнимы по модулю 6. Для самопроверки вычтите числа и проверьте, делится ли разность на модуль.

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

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

Из сравнимости степеней иногда ошибочно заключают, что сравнимы основания. Возведение в степень сохраняет сравнение, но обратная операция не всегда верна: например, квадраты 1 и 4 сравнимы по модулю 5, а основания — нет. Проверяйте обратный вывод отдельно по определению, то есть делится ли разность оснований на модуль.

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

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

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

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