Линейные диофантовые уравнения

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

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

Линейное диофантово уравнение записывают так: ax + by = c, где a, b и c — целые числа, а x и y требуется найти среди целых чисел. Буквы a и b называют коэффициентами при переменных. Такой вид удобен для задач, где два целых количества вместе дают заданный результат.

Целочисленное решение — пара целых чисел (x; y), которая после подстановки превращает уравнение в верное равенство. Например, для 3x + 5y = 1 пара (2; −1) подходит, потому что 3 · 2 + 5 · (−1) = 1. Проверка подстановкой позволяет убедиться, что найденная пара действительно является решением.

Наибольший общий делитель коэффициентов a и b — наибольшее натуральное число, на которое делятся оба коэффициента. Его обозначают НОД(a, b), а часто — буквой d. Этот делитель помогает понять, существуют ли решения уравнения: он должен делить правую часть c.

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

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

Пусть d — общий делитель коэффициентов a и b. Тогда a делится на d и b делится на d, поэтому при целых x и y оба произведения ax и by тоже делятся на d. Их сумма ax + by также делится на d. Если эта сумма равна c, то и c обязан делиться на d; иначе равенство невозможно.

Это условие не только необходимое, но и достаточное: уравнение ax + by = c имеет целочисленные решения тогда и только тогда, когда НОД(a, b) делит c. Если c делится на d, уравнение можно разделить на d, а целые коэффициенты a/d и b/d не имеют общего делителя больше единицы. Для таких коэффициентов можно подобрать целые x и y, дающие нужную сумму. Значит, проверка делимости сразу отвечает на вопрос о существовании решений.

Чтобы получить все решения, сначала находят одну подходящую пару (x₀; y₀). При d = НОД(a, b) остальные решения имеют вид x = x₀ + (b/d)t, y = y₀ − (a/d)t, где t — любое целое число. При изменении x на (b/d)t произведение ax увеличивается на abt/d, а произведение by уменьшается на ту же величину. Поэтому сумма остаётся равной c; общий вид охватывает все целые решения.

В задачах с дополнительными ограничениями подходят не все значения параметра. Например, если x и y — количества предметов, нужно потребовать x ≥ 0 и y ≥ 0. Подставь формулы общего решения в эти неравенства и выбери целые t, при которых оба условия выполняются. Так уравнение даёт все варианты, а ограничения оставляют только возможные по смыслу задачи.

Проверка разрешимости и запись решений уравнения ax + by = c

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

Разбор задач

Задача 1. Найдите одно целочисленное решение уравнения 3x + 5y = 1.

1. Подберём значения, чтобы сумма стала равна 1. Если взять x = 2, то 3x = 6; чтобы получить 1, к шести нужно прибавить −5.
2. Число −5 получается при y = −1, так как 5 · (−1) = −5.
3. Проверим подстановкой: 3 · 2 + 5 · (−1) = 6 − 5 = 1.

Ответ: одно решение — (2; −1).

Задача 2. Найдите все целочисленные решения уравнения 6x + 9y = 12.

1. Вычислим НОД(6, 9) = 3. Число 12 делится на 3, поэтому целые решения существуют.
2. Для поиска одной пары разделим равенство на 3: 2x + 3y = 4. Подходит x₀ = 2, y₀ = 0, потому что 2 · 2 + 3 · 0 = 4.
3. В общей формуле d = 3, поэтому x = 2 + (9/3)t = 2 + 3t, а y = 0 − (6/3)t = −2t, где t — целое число.
4. Подстановка даёт 6(2 + 3t) + 9(−2t) = 12 + 18t − 18t = 12. Значит, формула действительно сохраняет равенство.

Ответ: x = 2 + 3t, y = −2t, t ∈ ℤ.

Задача 3. Монеты стоят 7 и 11 рублей. Какими неотрицательными целыми количествами монет можно заплатить ровно 100 рублей?

1. Обозначим через x число семирублёвых монет, а через y — число монет по 11 рублей. Тогда 7x + 11y = 100, причём x ≥ 0 и y ≥ 0.
2. НОД(7, 11) = 1, поэтому решения существуют. Подходит пара x₀ = 8, y₀ = 4: 7 · 8 + 11 · 4 = 56 + 44 = 100.
3. Запишем все решения: x = 8 + 11t, y = 4 − 7t, где t — целое число. Из x ≥ 0 следует t ≥ 0, а из y ≥ 0 — t ≤ 4/7.
4. Единственное целое число между этими границами — t = 0. Значит, неотрицательное решение только одно.

Ответ: 8 монет по 7 рублей и 4 монеты по 11 рублей.

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

• Считать, что любое уравнение имеет целочисленное решение. Иногда проверяют только само равенство и забывают о делимости. Причина ошибки — перенос привычки решать уравнения с действительными числами. Найди НОД коэффициентов и проверь, делит ли он правую часть.
• Найти одну пару и объявить её единственным решением. Одна пара подтверждает, что решение есть, но не показывает остальные. Так бывает, когда забывают, что переменные могут принимать разные целые значения. Запиши общий вид с параметром и проверь, что рассматриваешь все целые t.
• Перепутать коэффициенты или знаки в формуле. Тогда добавки к ax и by не уничтожаются, и равенство может нарушиться. Ошибку легко пропустить, если формулу записывать по памяти. Подставь общий вид в исходное уравнение: слагаемые с t должны сократиться.
• Не учесть ограничения прикладной задачи. Целые решения могут быть отрицательными, хотя количество предметов не может быть меньше нуля. Часто условие о допустимых значениях проверяют только в начале, а затем о нём забывают. После записи общего решения проверь каждое ограничение для выбранных значений параметра.

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

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

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

• В линейном диофантовом уравнении переменные ищут в целых числах.
• Уравнение ax + by = c имеет целочисленные решения тогда и только тогда, когда НОД(a, b) делит c.
• Одно найденное решение позволяет записать все решения с помощью целого параметра.
• Параметр в общем решении принимает только целые значения.
• В прикладной задаче нужно дополнительно проверить ограничения на переменные.