D13 Диофантовы уравнения: общий метод (оценка + перебор остатков)

Метод состоит в том, что задачи вида «найдите все целые (натуральные, неотрицательные) решения уравнения» решаются по единому алгоритму, а не интуитивными догадками. Вместо того чтобы искать ответ наугад, мы последовательно сужаем множество кандидатов, пока не останется конечный список, который можно проверить.

Интуиция: представьте, что вы ищете потерянные ключи в большом доме. Если сразу обыскивать все комнаты одновременно — хаос. Правильная стратегия: сначала оцените, в каких комнатах вы вообще бывали (оценка области), потом исключите те, куда ключи физически не могли попасть (остатки по модулю), затем переберите оставшееся.

Метод объединяет пять инструментов, которые применяются в порядке возрастания сложности:
1. Оценка области — получаем конечный ящик, в котором живут все решения.
2. Анализ остатков — исключаем большинство кандидатов из ящика.
3. Факторизация — сводим уравнение к произведению, анализируем делители.
4. Параметризация — описываем бесконечное семейство решений аналитически.
5. Спуск/подъём — доказываем, что решений нет, через противоречие с минимальностью.

Этот метод — метаалгоритм: в конкретной задаче вы включаете один-два из этих инструментов. Умение быстро выбрать правильный инструмент приходит с практикой, но сам алгоритм принятия решений можно формализовать.

• Теорема Безу (линейные диофантовы уравнения). Уравнение $ax + by = c$ имеет целые решения тогда и только тогда, когда $\gcd(a,b) \mid c$. Если $(x_0, y_0)$ — одно решение, то общее: $x = x_0 + \frac{b}{d}t$, $y = y_0 - \frac{a}{d}t$, $t \in \mathbb{Z}$, где $d = \gcd(a,b)$. Когда использовать: уравнение линейно по всем переменным.

• Лемма об остатках. Если $a \equiv r \pmod{m}$, то $a^2 \equiv r^2 \pmod{m}$. Квадраты по модулю $3$ дают остатки $0$ или $1$; по модулю $4$ — остатки $0$ или $1$; по модулю $8$ — остатки $0, 1, 4$. Когда использовать: уравнение содержит квадраты; нужно показать, что решений нет или ограничить остатки.

• Факторизационный приём. Если уравнение $f(x,y)=N$ допускает разложение $f(x,y) = A(x,y)\cdot B(x,y)$, то каждая пара $(A,B)$ — делитель числа $N$, и число таких пар конечно. Когда использовать: после перегруппировки левая часть распадается в произведение (особенно $x^2 - y^2 = N$, $xy + ax + by = c$).

• Оценка через неравенство. Из уравнения $P(x,y)=0$ оцениваем: $|x| \leq C$ и $|y| \leq C$ для некоторого явного $C$. Когда использовать: уравнение содержит сумму неотрицательных слагаемых (квадраты, модули), что автоматически ограничивает каждое из них.

• Параметрическое описание решений. Для $x^2 + y^2 = z^2$ (примитивные тройки): $x = m^2 - n^2$, $y = 2mn$, $z = m^2 + n^2$ при $m > n > 0$, $\gcd(m,n)=1$, $m \not\equiv n \pmod{2}$. Когда использовать: задача просит описать все решения, а не просто найти конечный список.

• Шаг 1 — ограничение области: выразите одну переменную через другие и оцените, при каких значениях выражение остаётся целым и лежит в нужном диапазоне. Для $x^2 + y^2 = N$ сразу пишите $|x| \leq \sqrt{N}$, $|y| \leq \sqrt{N}$.

• Шаг 2 — выбор модуля: испытайте уравнение по $\bmod 3$, $\bmod 4$, $\bmod 7$, $\bmod 8$. Выбирайте тот модуль, при котором одна из сторон уравнения принимает мало значений (квадраты по $\bmod 4$ дают лишь $0$ и $1$).

• Шаг 3 — перебор остатков: составьте таблицу значений левой и правой частей по выбранному модулю; ищите, при каком остатке уравнение вообще может иметь решение.

• Шаг 4 — факторизация: если видите $a^2 - b^2$, немедленно пишите $(a-b)(a+b)$; если видите $xy + ax + by$, добавьте $ab$ к обеим частям и разложите $(x+b)(y+a) = c + ab$; ищите делители числа в правой части.

• Шаг 5 — анализ делителей: если произведение $AB = N$, перебирайте все пары делителей: $A = d_1$, $B = d_2$, $d_1 d_2 = N$, решайте систему $A = d_1$, $B = d_2$ для каждой пары. Не забывайте про отрицательные делители!

• Шаг 6 — параметризация или спуск: если решений бесконечно много, описывайте их формулой с параметром $t \in \mathbb{Z}$. Если подозреваете, что решений нет, примените метод бесконечного спуска или найдите инвариант, делающий левую и правую части несовместимыми.

• Проверка граничных случаев: после получения кандидатов не забудьте подставить их обратно в исходное уравнение — факторизация иногда вводит посторонние решения.

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

Структурные признаки (форма выражения, объекты):
- Уравнение степени 1 по всем переменным: линейное диофантово $ax+by=c$ - Уравнение вида $x^2 - y^2 = N$ или $xy = N$ — сигнал на факторизацию
- Уравнение вида $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$ — после умножения даёт факторизацию
- Сумма квадратов равна числу: $x^2 + y^2 = N$ - В правой части стоит простое число или степень простого — делителей мало

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

Задача 1. Линейное диофантово уравнение

Условие: Найдите все натуральные числа $x, y$, удовлетворяющие уравнению $2x + 3y = 100$.

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что я вижу? Линейное уравнение с двумя натуральными неизвестными. Триггер: «найдите все натуральные решения», уравнение 1-й степени.$2. *$Метод: линейное диофантово уравнение. $\gcd(2,3)=1$ делит 100 — решения существуют.$3. *$Первый ход: выражу $x$ через $y$: $x = \frac{100 - 3y}{2}$. Для натуральности $x$ нужно: (а) $100 - 3y > 0$, т.е. $y \leq 33$; (б) $100 - 3y$ чётно, т.е. $3y$ чётно, т.е. $y$ чётно.$4. *$Дальнейшие действия:* $y = 2k$, $k \geq 1$. Тогда $x = \frac{100-6k}{2} = 50 - 3k$. Условие $x \geq 1$: $50 - 3k \geq 1 \Rightarrow k \leq 16$. Итого $k \in \{1, 2, \ldots, 16\}$.

Решение:

Выразим $x$ через $y$:$x = \frac{100 - 3y}{2}.$ Чтобы $x$ было натуральным: $y$ чётно и $y \leq 33$. Пусть $y = 2k$, тогда$x = 50 - 3k, \quad k \in \mathbb{N}.$ Условие $x \geq 1$: $50 - 3k \geq 1 \Rightarrow k \leq 16$. Таким образом, $k = 1, 2, \ldots, 16$.

Ответ: Ровно 16 решений: $(x,y) = (50-3k,\ 2k)$ при $k = 1, 2, \ldots, 16$.

Что в этой задаче было главным: параметризация через чётность сразу сводит бесконечный перебор к конечному диапазону параметра $k$. Оценка сверху и снизу замыкает список.

Задача 2. Факторизация: уравнение $\frac{1}{x} + \frac{1}{y} = \frac{1}{12}$

Условие: Найдите все пары натуральных чисел $(x, y)$, для которых $\dfrac{1}{x} + \dfrac{1}{y} = \dfrac{1}{12}$.

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

Как думать (рассуждение ученика$):
1. $Что я вижу?* Уравнение с дробями, натуральные решения. Триггер: «найдите все натуральные $(x,y)$».$2. *$Первый ход: умножим обе части на $12xy$:$12y + 12x = xy.$ $3. *$Ключевая идея: перенесём всё в одну сторону и сфакторизуем:$$xy - 12x - 12y = 0 \Rightarrow xy - 12x - 12y + 144 = 144 \Rightarrow (x-12)(y-12) = 144.$$ $4. *$Теперь: нужно найти все разложения $144 = d_1 \cdot d_2$, $d_1, d_2 \geq 1$ (так как $x,y > 12$ при натуральных $x,y$). Из каждого разложения: $x = d_1 + 12$, $y = d_2 + 12$.

Решение:

Умножим на $12xy$:$$12(x+y) = xy \Rightarrow (x-12)(y-12) = 144.$$ Число $144$ имеет делители $d_1 \in \{1,2,3,4,6,8,9,12,16,18,24,36,48,72,144\}$. Для каждого $d_1$ берём $d_2 = 144/d_1$:

Учитывая симметрию (пары $(x,y)$ и $(y,x)$ считаем разными), получаем 15 пар.

Ответ: 15 пар натуральных чисел.

Что в этой задаче было главным: добавление $144 = 12^2$ к обеим частям — стандартный трюк для уравнений с $\frac{1}{x}+\frac{1}{y}$. После факторизации задача сводится к тривиальному перебору делителей.

• Ошибка: забываем про отрицательные делители. В задаче $(x-a)(y-b)=N$ пара $(-d_1, -d_2)$ тоже даёт $N$, если $N > 0$. → Почему неверно: пропускаем решения с $x < a$ или $y < b$. → Как избежать: всегда перечисляйте ВСЕ делители числа $N$, включая отрицательные, если задача не ограничивает натуральными числами.

• Ошибка: неправильный выбор модуля приводит к потере времени. Пробуем $\bmod 6$, а нужно $\bmod 4$. → Почему неверно: таблица остатков квадратов по $\bmod 6$ даёт много значений и не отсеивает кандидатов. → Как избежать: квадраты — сразу $\bmod 4$ или $\bmod 8$; кубы — $\bmod 7$ или $\bmod 9$.

• Ошибка: не проверяем посторонние решения после факторизации. Умножение обеих частей на $xy$ может вводить решения $x=0$ или $y=0$. → Почему неверно: $x=0$ делает исходное выражение бессмысленным. → Как избежать: подставляйте все найденные кандидаты в исходное уравнение.

• Ошибка: при оценке области забываем про симметрию. Оцениваем $x \leq C$, но не учитываем, что $y$ может быть большим. → Почему неверно: оценка $x^2 + y^2 = N$ даёт $|x| \leq \sqrt{N}$ И $|y| \leq \sqrt{N}$ одновременно — обе переменные ограничены. → Как избежать: явно выписывайте ограничения на каждую переменную по отдельности.

• Ошибка: при линейном уравнении пишем только одно частное решение, не общее. → Почему неверно: задача просит ВСЕ решения. → Как избежать: после нахождения $(x_0, y_0)$ сразу пишите общую формулу $x = x_0 + \frac{b}{d}t$, $y = y_0 - \frac{a}{d}t$, затем накладывайте ограничения (натуральность, положительность).

• Ошибка: параметризуем, не проверяя условие взаимной простоты. Для пифагоровых троек формула $x = m^2-n^2$, $y=2mn$, $z=m^2+n^2$ описывает ПРИМИТИВНЫЕ тройки только при $\gcd(m,n)=1$ и $m \not\equiv n \pmod{2}$. → Как избежать: всегда выписывайте условия применимости параметризации.