D3 Сравнения по модулю

Метод состоит в том, что вместо работы с точными значениями целых чисел мы переходим к их остаткам при делении на некоторое натуральное число $m$ — модуль. Запись $a \equiv b \pmod{m}$ означает, что $m \mid (a - b)$, то есть $a$ и $b$ дают одинаковый остаток при делении на $m$.

Интуиция: представь, что у тебя есть циферблат с $m$ делениями. Все числа, отличающиеся на кратное $m$, оказываются в одной точке — в одном классе вычетов. Вместо бесконечной числовой прямой мы работаем с конечным множеством из $m$ классов $\{0, 1, 2, \ldots, m-1\}$. Это превращает бесконечную задачу в конечную — перебор.

Почему метод существует как отдельная единица? Потому что арифметические операции (сложение, умножение, возведение в степень) совместимы со взятием остатка: $(a+b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$. Это позволяет заменять числа на их остатки, не теряя информацию о делимости. Сравнения — это алгебра остатков, и в ней есть своя «таблица умножения».

Главное применение: доказательство невозможности (нет решений в целых числах), нахождение последней цифры или остатка степени при делении, и установление необходимых условий на решения диофантовых уравнений. Метод работает, потому что если уравнение $f(x,y) = 0$ не имеет решений по модулю $m$ для некоторого $m$, то решений в целых числах тоже нет.

• Свойства совместимости: если $a \equiv b \pmod{m}$ и $c \equiv d \pmod{m}$, то $a+c \equiv b+d \pmod{m}$ и $ac \equiv bd \pmod{m}$. Условие: всегда. Когда использовать: при упрощении сложных выражений — заменяй каждый множитель его остатком.

• Возведение в степень: $a \equiv b \pmod{m} \Rightarrow a^k \equiv b^k \pmod{m}$. Условие: $k \geq 0$ целое. Когда использовать: при вычислении $n^k \bmod m$ — заменяй основание на его остаток.

• Малая теорема Ферма: $a^{p-1} \equiv 1 \pmod{p}$ при $\gcd(a, p) = 1$, где $p$ — простое. Условие: $p$ простое, $p \nmid a$. Когда использовать: при вычислении $a^n \bmod p$ — периодичность степеней с периодом, делящим $p-1$.

• Теорема Эйлера: $a^{\varphi(m)} \equiv 1 \pmod{m}$ при $\gcd(a, m) = 1$. Условие: $\gcd(a,m)=1$. Когда использовать: обобщение МТФ для составного модуля.

• Квадраты по модулю: квадрат целого числа даёт только определённые остатки. Например: $n^2 \bmod 4 \in \{0, 1\}$; $n^2 \bmod 8 \in \{0, 1, 4\}$; $n^2 \bmod 3 \in \{0, 1\}$. Когда использовать: при встрече уравнений с квадратами — сразу проверяй допустимые остатки.

• Выбор модуля. Смотри на структуру задачи: если есть квадраты — пробуй $m \in \{3, 4, 8\}$; если кубы — $m = 7$ или $m = 9$; если степени — ищи $m$ такое, что основание имеет малый порядок.

• Таблица остатков степени. Вычисли $a^0, a^1, a^2, \ldots$ по модулю $m$, пока не замкнётся цикл. Период всегда делит $\varphi(m)$. Затем редуцируй показатель по этому периоду.

• Перебор всех классов вычетов. Если надо доказать что-то для всех $n$, разбей на случаи $n \equiv 0, 1, \ldots, m-1 \pmod{m}$ и проверь каждый.

• Доказательство отсутствия решений. Покажи, что левая часть уравнения по модулю $m$ принимает только значения из множества $A$, правая — из множества $B$, и $A \cap B = \emptyset$.

• Анализ НОД через сравнения. Если $d = \gcd(a,b)$, то $a \equiv 0 \pmod{d}$ и $b \equiv 0 \pmod{d}$; используй это для сужения возможных значений.

• Подъём по модулю (для нахождения всех решений). Сначала найди решения по небольшому модулю $m$, затем уточняй до $m^2$, $m^3$ — метод Гензеля.

Поверхностные признаки (что буквально написано):
- «Докажите, что выражение делится на $k$» / «не делится на $k$»
- «Найдите последнюю цифру» или «найдите остаток от деления ... на ...»
- «Докажите, что уравнение не имеет целочисленных решений»
- «Найдите все натуральные $n$, при которых $f(n)$ делится на $g(n)$»

Структурные признаки (форма выражения, объекты):
- В задаче фигурируют степени ($n^k$, $a^n$) — значит, порядок по модулю будет маленьким
- Уравнение вида $a^2 + b^2 = c^2 + \ldots$ — квадраты ограничены по остаткам
- Произведения нескольких целых чисел — модуль позволяет разбить на случаи
- В выражении есть факториал или биномиальный коэффициент

Цель задачи (что от тебя хотят):
- Доказать делимость или неделимость
- Доказать невозможность (нет решений)
- Найти все решения диофантового уравнения
- Вычислить последнюю цифру или конкретный остаток большой степени

Задача 1. Докажите, что уравнение $x^2 + y^2 = 3z^2$ не имеет решений в натуральных числах.

Источник: классическая олимпиадная задача (тренировочная)

Как думать (рассуждение ученика$):
1. $Что я вижу? Уравнение с квадратами и целыми числами. Надо доказать отсутствие решений — это триггер для сравнений по модулю.$2. *$Какой модуль? Вижу квадраты — пробую $m = 4$ или $m = 3$. Попробую $m = 4$: квадрат целого числа по модулю 4 даёт только $0$ или $1$. Значит $x^2 + y^2 \bmod 4 \in \{0, 1, 2\}$. А $3z^2 \bmod 4 \in \{0, 3\}$ (так как $z^2 \in \{0,1\}$, и $3 \cdot 1 = 3$). Пересечение: только $0$. То есть оба должны делиться на $4.
3. $Что дальше?* Если $x^2 + y^2 \equiv 0 \pmod{4}$, то оба $x$ и $y$ чётны; $3z^2 \equiv 0 \pmod 4$ означает $z$ чётно. Сокращаем на 2 — и получаем то же уравнение с меньшими числами. Это бесконечный спуск!$4. *$Ключевая идея:* нет наименьшего натурального решения — значит, решений нет.

Решение:

Предположим, что $(x, y, z)$ — натуральное решение. Рассмотрим уравнение по модулю $4$.

Квадрат целого числа по модулю $4$ равен $0$ или $1$. Поэтому:$$x^2 + y^2 \equiv 0, 1, \text{ или } 2 \pmod{4}.$$ С другой стороны, $3z^2 \equiv 0$ или $3 \pmod{4}$.

Единственное общее значение — $0$. Значит $x^2 \equiv y^2 \equiv 0 \pmod{4}$ и $z^2 \equiv 0 \pmod{4}$, откуда $x, y, z$ — все чётные.

Пишем $x = 2x_1$, $y = 2y_1$, $z = 2z_1$. Подставляем:$$4x_1^2 + 4y_1^2 = 3 \cdot 4z_1^2 \Rightarrow x_1^2 + y_1^2 = 3z_1^2.$$

Получили то же уравнение с тройкой $(x_1, y_1, z_1) < (x, y, z)$. Продолжая, приходим к противоречию с принципом наименьшего числа.

Ответ: решений нет.

Что в этой задаче было главным: выбор модуля $4$ ограничил остатки квадратов — это и дало противоречие (а вместе с ним — спуск). Связка «сравнения → бесконечный спуск» очень частая.

Задача 2. Найдите остаток от деления $7^{2024}$ на $100$.

Источник: тренировочная (стандартный тип задач ВсОШ)

Как думать (рассуждение ученика$):
1. $Что вижу?* Большая степень числа, нужен остаток от деления на $100$. Это «последние две цифры» — триггер для сравнений.$2. *$Как действовать? Нужно найти период степеней $7$ по модулю $100$. По теореме Эйлера: $\varphi(100) = 40$, значит $7^{40} \equiv 1 \pmod{100}$.$3. *$Редуцирую показатель: $2024 = 40 \cdot 50 + 24$, значит $7^{2024} \equiv 7^{24} \pmod{100}$.$4. *$Вычисляю $7^{24}$: считаю последовательно: $7^2 = 49$; $7^4 = 49^2 = 2401 \equiv 1 \pmod{100}$. Период не $40$, а всего $4$! $2024 = 4 \cdot 506$, значит $7^{2024} \equiv (7^4)^{506} \equiv 1^{506} \equiv 1 \pmod{100}$.

Решение:

Найдём период степеней $7$ по модулю $100$:$$7^1 \equiv 7,\quad 7^2 \equiv 49,\quad 7^3 \equiv 343 \equiv 43,\quad 7^4 \equiv 7 \cdot 43 = 301 \equiv 1 \pmod{100}.$$

Период равен $4$. Так как $2024 = 4 \cdot 506$:$$7^{2024} = (7^4)^{506} \equiv 1^{506} = 1 \pmod{100}.$$

Ответ: $1$.

Что в этой задаче было главным: не стоит слепо применять $\varphi(m)$ — истинный период может быть значительно меньше. Всегда вычисляй таблицу степеней и ищи реальный порядок.

• Ошибка: делать вывод из $a^2 \equiv b^2 \pmod{m}$, что $a \equiv b \pmod{m}$. → Почему неверно: $a^2 - b^2 = (a-b)(a+b)$, и делимость произведения не означает делимость каждого множителя. → Как избежать: рассматривай оба случая $a \equiv b$ и $a \equiv -b$.

• Ошибка: брать первый попавшийся модуль (например, $m=10$) без обоснования. → Почему неверно: можно не поймать нужное противоречие. → Как избежать: смотри на степени в задаче: квадраты → $m=4$ или $m=8$; кубы → $m=7$ или $m=9$; показывают «не делится на 3» → $m=3$.

• Ошибка: неверно применять МТФ, не проверив $\gcd(a, p) = 1$. → Почему неверно: если $p \mid a$, то $a^{p-1} \equiv 0 \not\equiv 1 \pmod p$. → Как избежать: всегда проверяй условие взаимной простоты перед применением МТФ или теоремы Эйлера.

• Ошибка: путать порядок числа и $\varphi(m)$. Писать $7^{40} \equiv 1 \pmod{100}$ и использовать период $40$, хотя реальный период меньше. → Почему неверно: ответ будет верным, но рассчитывать на период $\varphi(m)$ неэффективно и может запутать. → Как избежать: всегда проверяй малые степени перед редукцией.

• Ошибка: «нашёл решение по модулю — значит решение есть». → Почему неверно: отсутствие противоречия по одному модулю не означает существование решений в целых числах. → Как избежать: сравнения дают только необходимые условия (используй для доказательства несуществования), но не достаточные (для существования нужна конструкция).

• Ошибка: делить сравнение $ka \equiv kb \pmod{m}$ на $k$ и получать $a \equiv b \pmod{m}$. → Почему неверно: деление допустимо только если $\gcd(k, m) = 1$, иначе модуль изменяется: $ka \equiv kb \pmod{m} \Rightarrow a \equiv b \pmod{m/\gcd(k,m)}$. → Как избежать: запомни правило сокращения сравнений с корректировкой модуля.