Как решить уравнение в целых числах: 54x + 21y = 906

Дано: уравнение $54x + 21y = 906$. Найти: все его решения в целых числах и отдельно те, в которых $x$ и $y$ натуральные.

Уравнение вида $ax + by = c$ с целыми коэффициентами называют линейным диофантовым, и решается оно по жёсткой схеме: проверить разрешимость по НОД коэффициентов, найти одно частное решение расширенным алгоритмом Евклида, а из него получить сразу все остальные. Здесь $\gcd(54, 21) = 3$, правая часть 906 на 3 делится, поэтому решения есть: общее решение $x = 2 + 7t$, $y = 38 - 18t$ при любом целом $t$, а в натуральных числах подходят ровно три пары: (2; 38), (9; 20), (16; 2). Калькулятор сверху прогоняет ту же цепочку для любых коэффициентов и показывает целые точки на прямой, ниже - решение по шагам.

Решение по шагам

Дано. $a = 54$, $b = 21$, $c = 906$.

Найти. Все целые пары $(x, y)$ с $54x + 21y = 906$ и все натуральные среди них.

Шаг 1. Проверяем разрешимость по НОД коэффициентов.

$$\gcd(54, 21) = 3, \qquad 906 : 3 = 302.$$

Левая часть при любых целых $x$ и $y$ кратна тройке: и 54, и 21 делятся на 3, значит на 3 делится и вся сумма. Тогда и правая часть обязана делиться на 3, иначе равенство невозможно ни при каких целых числах. Она делится нацело, остатка нет, и решения существуют. Сам НОД удобно получить алгоритмом Евклида: $54 = 2 \cdot 21 + 12$, затем $21 = 1 \cdot 12 + 9$, $12 = 1 \cdot 9 + 3$ и $9 = 3 \cdot 3 + 0$, последний ненулевой остаток равен 3.

Шаг 2. Сокращаем уравнение на НОД.

$$18x + 7y = 302.$$

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

Шаг 3. Находим частное решение расширенным алгоритмом Евклида.

Сначала прогоняем обычную лестницу делений для пары 18 и 7:

$$18 = 2 \cdot 7 + 4, \qquad 7 = 1 \cdot 4 + 3, \qquad 4 = 1 \cdot 3 + 1.$$

Теперь раскручиваем её в обратную сторону, выражая единицу через исходные числа:

$$\begin{aligned} 1 &= 4 - 3 = 4 - (7 - 4) = 2 \cdot 4 - 7 \\ &= 2 \cdot (18 - 2 \cdot 7) - 7 = 2 \cdot 18 - 5 \cdot 7. \end{aligned}$$

Получилось соотношение Безу $18 \cdot 2 + 7 \cdot (-5) = 1$. Правая часть у нас не единица, а 302, поэтому домножаем обе части на 302:

$$18 \cdot 604 + 7 \cdot (-1510) = 302.$$

Пара $(604;\ -1510)$ - уже честное решение, просто некрасивое.

Шаг 4. Сдвигаем частное решение к удобному.

Уменьшать $x$ можно шагами по 7 (коэффициент при $y$ в сокращённом уравнении), одновременно увеличивая $y$ на 18. Делим 604 на 7 с остатком: $604 = 86 \cdot 7 + 2$, значит после 86 шагов получим $x_0 = 2$. Второе число считаем прямой подстановкой:

$$y_0 = \frac{302 - 18 \cdot 2}{7} = \frac{266}{7} = 38.$$

Проверка в исходном уравнении: $54 \cdot 2 + 21 \cdot 38 = 108 + 798 = 906$. Сходится.

Шаг 5. Записываем общее решение.

$$x = 2 + 7t, \qquad y = 38 - 18t, \qquad t \in \mathbb{Z}.$$

Шаги 7 и 18 - это в точности коэффициенты сокращённого уравнения, поменянные местами, причём у $y$ шаг идёт с минусом. Подставим несколько значений параметра и убедимся, что сумма не меняется:

Шаг 6. Отбираем решения в натуральных числах.

Требуем $x \ge 1$ и $y \ge 1$ одновременно:

$$2 + 7t \ge 1 \;\Longrightarrow\; t \ge -\tfrac{1}{7}, \qquad 38 - 18t \ge 1 \;\Longrightarrow\; t \le \tfrac{37}{18} \approx 2{,}06.$$

Целые $t$ из промежутка от $-1/7$ до $2{,}06$ - это $t = 0$, $t = 1$ и $t = 2$. Больше подходящих значений параметра нет, потому что дальше в обе стороны одна из координат уходит в минус.

Ответ. Общее решение: $x = 2 + 7t$, $y = 38 - 18t$, где $t$ - любое целое число. В натуральных числах ровно три решения: $(2;\ 38)$, $(9;\ 20)$, $(16;\ 2)$.

Формула и откуда она берётся

Всё держится на одном факте: множество чисел вида $ax + by$ при целых $x$ и $y$ - это в точности множество кратных числу $d = \gcd(a, b)$. В одну сторону это очевидно: раз $d$ делит и $a$, и $b$, то делит и любую их комбинацию. В другую сторону работает соотношение Безу - расширенный алгоритм Евклида предъявляет конкретные целые числа, для которых $ax + by = d$, а домножением на любое целое из $d$ получаем любое кратное. Отсюда критерий разрешимости в одну строку:

$$ax + by = c \text{ разрешимо в целых числах} \iff d \mid c.$$

Структура ответа тоже выводится за пару строк. Пусть $(x_0, y_0)$ и $(x, y)$ - два решения. Вычтем одно равенство из другого:

$$a(x - x_0) + b(y - y_0) = 0 \quad\Longrightarrow\quad \frac{a}{d}(x - x_0) = -\frac{b}{d}(y - y_0).$$

Числа $a/d$ и $b/d$ взаимно просты, поэтому $b/d$ обязано делить разность $x - x_0$ целиком. Значит $x - x_0 = (b/d)\,t$ для некоторого целого $t$, а тогда $y - y_0 = -(a/d)\,t$. Это и есть общая формула:

$$x = x_0 + \frac{b}{d}\,t, \qquad y = y_0 - \frac{a}{d}\,t.$$

Геометрически картина такая: уравнение задаёт прямую на плоскости, а решения - это узлы целочисленной решётки, на которую прямая попала. Узлы идут вдоль прямой равномерно, с шагом $b/d$ по горизонтали, поэтому решений либо бесконечно много, либо нет вообще. Промежуточного варианта «ровно два решения» у линейного уравнения не бывает - конечным число решений становится только после дополнительного условия вроде натуральности обеих координат. Именно это и рисует калькулятор сверху в режиме целых точек.

Второй способ: перейти к сравнению по модулю

На контрольной обратную подстановку часто заменяют более коротким приёмом. Возьмём сокращённое уравнение $18x + 7y = 302$ и посмотрим на него по модулю 7: слагаемое $7y$ исчезает, и остаётся сравнение с одним неизвестным.

$$18x \equiv 302 \pmod 7 \quad\Longrightarrow\quad 4x \equiv 1 \pmod 7.$$

Здесь $18 = 2 \cdot 7 + 4$ и $302 = 43 \cdot 7 + 1$, поэтому коэффициенты сразу заменены на остатки. Дальше перебираем семь вариантов $x = 0, 1, \dots, 6$ и находим тот, где произведение даёт остаток 1: подходит $x = 2$, так как $4 \cdot 2 = 8 = 7 + 1$. Значит $x \equiv 2 \pmod 7$, то есть $x = 2 + 7t$ - тот же ответ, что дала обратная подстановка, но без раскручивания лестницы.

Модуль всегда берут по меньшему из коэффициентов: перебирать придётся меньше вариантов. Способ особенно хорош, когда коэффициенты небольшие, а вот при двух трёхзначных числах перебор становится долгим, и расширенный алгоритм выигрывает. По сути мы ищем обратный элемент к 4 по модулю 7, и тот же самый шаг стоит внутри асимметричной криптографии рядом с быстрым возведением в степень по модулю.

Когда решений нет и сколько их в натуральных числах

Поменяем в нашем уравнении правую часть на 100 и посмотрим, что изменится. НОД коэффициентов прежний, $\gcd(54, 21) = 3$, а вот 100 на 3 не делится: $100 = 3 \cdot 33 + 1$. Левая часть кратна трём при любых целых $x$ и $y$, правая - нет, поэтому уравнение $54x + 21y = 100$ решений в целых числах не имеет вовсе. Никаких вычислений дальше делать не нужно, ответ «решений нет» и есть полный ответ. Проверить делимость проще всего, разложив коэффициенты на простые множители или прогнав два деления Евклида.

Количество натуральных решений оценивается заранее. Целые точки идут с шагом $b/d$ по $x$, а годный отрезок тянется от $x = 0$ до $x = c/a$, поэтому решений примерно

$$N \approx \frac{c/a}{b/d} = \frac{c \cdot d}{a \cdot b} = \frac{906 \cdot 3}{54 \cdot 21} \approx 2{,}4.$$

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

Если в уравнении фигурирует делимость на неизвестный модуль, первым делом выясняют, простое ли число стоит в основании: от этого зависит и существование обратного элемента, и применимость малой теоремы Ферма - как это проверить число на простоту, разобрано отдельно.

Частые ошибки

• Забывают сократить уравнение на НОД. Если работать с исходными 54 и 21, шаг по $x$ получится равным 21, а не 7, и две трети решений просто выпадут из ответа.
• Берут НОД правой части. Условие разрешимости проверяется только по коэффициентам при неизвестных, число $c$ в НОД не входит - оно лишь обязано на него делиться.
• Теряют знак минус у второго шага. В общем решении шаги идут с разными знаками: $x$ растёт на $b/d$, $y$ убывает на $a/d$. Одинаковые знаки сразу ломают проверку подстановкой.
• Останавливаются на частном решении. Пара $(604;\ -1510)$ формально верна, но задание требует общее решение, а не одну пару. Без параметра $t$ ответ неполон.
• Путают целые и натуральные. В целых числах решений бесконечно много всегда, когда они вообще есть, а вопрос «сколько решений» имеет смысл только для натуральных или неотрицательных.
• Ошибаются в границах при отборе. Неравенства решаются каждое отдельно, а параметр берётся из пересечения промежутков; дробные концы округляются внутрь промежутка, а не наружу.

FAQ

Сколько решений у линейного уравнения в целых числах? Либо ни одного, либо бесконечно много. Если $\gcd(a, b)$ не делит $c$, решений нет; если делит, то по одному на каждое целое значение параметра $t$. Конечным число становится, только когда добавлено ограничение вроде натуральности или отрезка значений.

Обязательно ли частное решение искать алгоритмом Евклида? Нет. Для маленьких коэффициентов пару часто видно подбором: например, в уравнении $3x + 5y = 1$ сразу заметно решение $x = 2$, $y = -1$. Расширенный алгоритм нужен там, где подбор безнадёжен, и он же гарантирует результат за считанные шаги.

Что делать, если неизвестных три? Уравнение $ax + by + cz = e$ решают в два приёма: вводят вспомогательную переменную для суммы $ax + by$, находят все её допустимые значения из уравнения с $z$, а затем решают внутреннее уравнение тем же способом. Ответ получается с двумя параметрами.

А если уравнение нелинейное? Общего алгоритма для диофантовых уравнений в принципе не существует, это результат по десятой проблеме Гильберта. Каждый класс разбирают своими приёмами: разложением на множители, оценками, остатками. Классический пример со своей теорией - уравнение Пелля вида $x^2 - Dy^2 = 1$.

Коротко

1. Считаем $\gcd(54, 21) = 3$ и проверяем делимость: $906 : 3 = 302$, значит решения есть.
2. Сокращаем уравнение на НОД: $18x + 7y = 302$ с взаимно простыми коэффициентами.
3. Расширенным алгоритмом Евклида получаем $18 \cdot 2 + 7 \cdot (-5) = 1$, домножаем на 302 и сдвигаем к удобной паре $x_0 = 2$, $y_0 = 38$.
4. Записываем общее решение: $x = 2 + 7t$, $y = 38 - 18t$ при любом целом $t$.
5. Из условий $x \ge 1$ и $y \ge 1$ получаем $t = 0, 1, 2$, то есть три натуральных решения: $(2;\ 38)$, $(9;\ 20)$, $(16;\ 2)$.