D8 Анализ остатков по конкретному модулю

Метод состоит в том, что для конкретной задачи выбирается один определённый модуль $m$ (например, $3$, $4$, $7$, $8$, $9$), вычисляются все возможные остатки нужного выражения, и делается вывод о делимости или невозможности.

Отличие от общего метода сравнений (D3): здесь акцент не на теоретических свойствах сравнений, а на практическом выборе конкретного модуля под конкретную задачу. Это рабочий инструмент: «смотришь на задачу, видишь квадраты — берёшь $m = 4$ или $m = 8$; видишь кубы — берёшь $m = 7$ или $m = 9$; нужно последнее число — берёшь $m = 10$».

Метод очень часто встречается на олимпиадах потому, что проверка остатков — быстрый и надёжный способ отсечь «лишние» решения. Основная идея: конечное множество остатков по модулю $m$ — это «рентген» числа, который показывает его «фазу». Если у двух частей уравнения несовместные фазы — задача решена.

На практике 90% задач этого типа решаются перебором конечной таблицы остатков: $n \bmod m$ для $n = 0, 1, \ldots, m-1$ подставляется в обе части уравнения, и проверяется, есть ли совпадение.

• Квадраты по модулю 4: $n^2 \equiv 0$ или $1 \pmod{4}$ (для любого целого $n@@LATEXBLOCK_0_0@@). *$Когда использовать:* при уравнениях с кубами, требующих кратности 7.

• Кубы по модулю 9: $n^3 \equiv 0, 1, 8 \pmod{9}$ (то есть $0$ или $\pm 1$$). *$Когда использовать:* стандартный инструмент для кубических диофантовых уравнений.

• Составить таблицу остатков. Для выбранного $m$ выпиши $f(0), f(1), \ldots, f(m-1)$ по модулю $m$. Это занимает 1–2 минуты и сразу даёт картину.

• Перебор всех случаев. Разбей все целые числа на $m$ классов по остатку при делении на $m$. Для каждого класса проверь условие задачи.

• Сравнение множеств допустимых остатков. Если левая часть принимает остатки из $A$, правая из $B$, и $A \cap B = \emptyset$ — противоречие.

• Сужение перебора. Вместо перебора всех натуральных чисел перебираешь только $m$ классов — радикальное сокращение поиска.

• Комбинирование нескольких модулей. Если модуль $m_1$ не даёт противоречия — пробуй $m_2$. Часто нужна пара: сначала $m = 4$ (чётность квадрата), потом $m = 3$ (делимость на 3).

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

Структурные признаки (форма выражения, объекты):
- Уравнение содержит квадраты — рефлекс: $m = 4$ или $m = 8$ - Уравнение содержит кубы — рефлекс: $m = 7$ или $m = 9$ - Нужна последняя цифра числа — $m = 10$ - Нужна делимость на $3$ — $m = 3$; на $9$ — $m = 9$

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

Задача 1. Докажите, что уравнение $x^2 + y^2 = 8k + 6$ не имеет целых решений при любом целом $k$.

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

Как думать (рассуждение ученика$):
1. $Что вижу?* Сумма квадратов должна быть равна $8k + 6 \equiv 6 \pmod 8$. Вижу квадраты — сразу беру $m = 8$.$2. *$Составляю таблицу $n^2 \bmod 8$:$
-$ $0^2 = 0$, $1^2 = 1$, $2^2 = 4$, $3^2 = 9 \equiv 1$, $4^2 = 16 \equiv 0$.
- Период: $\{0, 1, 4, 1, 0, 1, 4, 1\}$ — то есть квадрат по $\bmod 8 \in \{0, 1, 4\}$.$3. *$Сумма двух квадратов по $\bmod 8$:* $0+0=0$, $0+1=1$, $0+4=4$, $1+1=2$, $1+4=5$, $4+4=8\equiv 0$. Все возможные: $\{0,1,2,4,5\}$. Значение $6$ не входит!

Решение:

Значения $n^2 \bmod 8$ для $n = 0, 1, \ldots, 7$: $0, 1, 4, 1, 0, 1, 4, 1$. Итого $x^2 \bmod 8 \in \{0, 1, 4\}$.

Возможные значения $x^2 + y^2 \bmod 8$: $0+0=0$, $0+1=1$, $0+4=4$, $1+1=2$, $1+4=5$, $4+4=0$ — итого $\{0, 1, 2, 4, 5\}$.

Число $8k+6 \equiv 6 \pmod{8}$, но $6 \notin \{0,1,2,4,5\}$. Противоречие.

Ответ: уравнение не имеет целых решений.

Что в этой задаче было главным: выбор $m = 8$ (а не $4$!) позволил поймать остаток $6$, который исключается именно по модулю $8$.

Задача 2. При каких натуральных $n$ число $n^3 + 2n$ делится на $9$?

Источник: тренировочная (ВсОШ, муниципальный этап)

Как думать (рассуждение ученика$):
1. $Что вижу?* Делимость кубического выражения на $9$. Берём $m = 9$.$2. *$Составляю таблицу $n^3 + 2n \bmod 9$ для $n = 0, \ldots, 8$.$
3. $Ноль получается при $n \equiv 0, 4, 5 \pmod 9$.$

$Решение:

Проверим $n^3 + 2n \bmod 9$ для $n = 0, 1, \ldots, 8$:

Делится на $9$ при $n \equiv 0, 4, 5 \pmod{9}$.

Ответ: $n^3 + 2n$ делится на $9$ тогда и только тогда, когда $n \equiv 0, 4$ или $5 \pmod{9}$.

Что в этой задаче было главным: перебор конечной таблицы по $m = 9$ — прямолинейный и надёжный подход.

• Ошибка: выбрать слишком маленький модуль (например $m = 2$ для задачи с квадратами). → Почему неверно: по $m = 2$ квадрат даёт $0$ или $1$ — слишком мало информации. → Как избежать: квадраты → $m \in \{3, 4, 8\}$; кубы → $m \in \{7, 9\}$.

• Ошибка: не составить полную таблицу, пропустить некоторые классы. → Почему неверно: пропущенный случай может дать ложное противоречие. → Как избежать: всегда проверяй все $n = 0, 1, \ldots, m-1$ — ни один класс не пропускай.

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

• Ошибка: неверно вычислить остаток при больших значениях. → Почему неверно: арифметическая ошибка в таблице — и вывод неверен. → Как избежать: считай поэтапно: сначала $n^2 \bmod m$, потом $n^3 = n^2 \cdot n \bmod m$.