2.2.5. Решение задач с помощью сравнений

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

Сравнение чисел по модулю m означает, что числа при делении на m дают одинаковые остатки. Например, 17 и 5 сравнимы по модулю 6, потому что оба дают остаток 5. Такое понятие позволяет заменить большое число небольшим остатком.

Запись a ≡ b (mod m) читается: «a сравнимо с b по модулю m». Число m называют натуральным модулем и берут m > 1. Запись сразу показывает, относительно какого деления сравниваются числа.

Модуль сравнения — это число m, по которому находят остатки и проверяют их совпадение. Один и тот же набор чисел может сравниваться по-разному при разных модулях. Поэтому модуль всегда нужно указывать.

Сравнение связано с делимостью: a ≡ b (mod m) тогда и только тогда, когда разность a − b делится на m. Это даёт второй способ проверки сравнения, особенно удобный, когда разность легко вычислить.

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

Пусть при делении a и b на m получается один и тот же остаток r. Тогда a = m · q₁ + r, а b = m · q₂ + r, где q₁ и q₂ — частные. Вычитая равенства, получаем a − b = m · (q₁ − q₂), поэтому разность делится на m. Именно одинаковый остаток исчезает при вычитании.

Проверить сравнение можно двумя способами. Первый — разделить оба числа на m и сравнить остатки, второй — вычислить a − b и проверить делимость этой разности на m. Первый путь нагляден, а второй часто быстрее, если разность является очевидным кратным модуля.

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

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

В задаче сначала ищут величину, которая повторяется, и выбирают её длину в качестве модуля. Затем исходные числа заменяют остатками, выполняют более простые действия и получают остаток ответа. В конце этот остаток переводят обратно в условие: например, в номер дня недели или в остаток от деления.

Основные способы работы со сравнениями

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

Разбор задач

1. Проверка сравнения

Условие: проверьте, верно ли 47 ≡ 5 (mod 7). Выберем способ через разность, потому что числа уже даны в удобном виде.

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

Ответ: 47 ≡ 5 (mod 7) — верно. При делении обоих чисел на 7 остаток равен 5.

2. Остаток от деления степени

Условие: найдите остаток от деления 3⁴⁰ на 7. Большую степень не вычисляем, а рассматриваем последовательность остатков по модулю 7.

1. Получаем: 3¹ ≡ 3, 3² ≡ 2, 3³ ≡ 6, 3⁴ ≡ 4, 3⁵ ≡ 5, 3⁶ ≡ 1 (mod 7).
2. После шести умножений остаток снова стал равен 1, поэтому остатки повторяются с периодом 6.
3. Делим показатель 40 на 6: 40 = 6 · 6 + 4. Значит, 3⁴⁰ имеет такой же остаток, как 3⁴.
4. Так как 3⁴ = 81, а 81 при делении на 7 даёт остаток 4, получаем результат.

Ответ: остаток равен 4.

3. День недели через 1000 дней

Условие: сегодня вторник. Какой день недели будет через 1000 дней? Дни недели образуют цикл длиной 7, поэтому используем модуль 7.

1. Находим остаток: 1000 = 7 · 142 + 6, значит, 1000 ≡ 6 (mod 7).
2. Через 7 дней наступает тот же день, поэтому полные недели не меняют название дня.
3. От вторника отсчитываем ещё 6 дней: среда, четверг, пятница, суббота, воскресенье, понедельник.

Ответ: через 1000 дней будет понедельник.

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

Считать числа сравнимыми, если одно делится на другое. Это неверно: сравнимость определяется остатками по конкретному модулю, а не отношением чисел. Проверьте остатки или делимость разности на указанный модуль.

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

Путать остаток с частным. В записи деления с остатком частное показывает, сколько раз модуль помещается в числе, а остаток — что осталось. Для сравнения нужны именно остатки, поэтому после деления выпишите их отдельно.

Делать вывод по разности без проверки делимости. Сам факт, что разность получилась большой или чётной, ещё ничего не доказывает. Разделите её на модуль или представьте в виде произведения модуля и целого числа.

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

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

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

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

• a ≡ b (mod m) означает, что a и b дают одинаковые остатки при делении на m.
• Числа a и b сравнимы по модулю m тогда и только тогда, когда m делит a − b.
• Сравнимые числа можно заменять друг другом при вычислениях с тем же модулем.
• Сравнения с одинаковым модулем можно складывать и перемножать.
• В задачах на повторение цикла модуль равен длине цикла.