Начните с общего делителя
Рассмотрим уравнение ax + by = c, где коэффициенты a и b являются положительными целыми числами, а c тоже целое. Если наибольший общий делитель коэффициентов равен d, левая часть при целых x и y обязательно делится на d. Поэтому c также должно делиться на d. Для линейного уравнения с двумя неизвестными это условие не только необходимо, но и достаточно для существования целых решений. Например, уравнение 6x + 9y = 31 целых решений не имеет: левая часть делится на три, а 31 не делится. Долгий перебор здесь не нужен.
Одно решение открывает целое семейство
Теперь возьмём 6x + 9y = 30. Пара x = 2, y = 2 подходит, поскольку 12 + 18 = 30. Если увеличить x на три и уменьшить y на два, первая часть вырастет на 18, а вторая уменьшится на 18. Равенство сохранится. Все целые решения этого примера можно записать как x = 2 + 3t, y = 2 − 2t, где t является любым целым числом. Параметр помогает не выписывать бесконечный список. Для более крупных коэффициентов исходное решение удобно искать с помощью расширенного алгоритма Евклида, а не случайным угадыванием.
Смысл задачи ограничивает параметр
Целое число может быть отрицательным, но отрицательное количество коробок обычно не имеет смысла. Если в нашем примере нужны x и y не меньше нуля, получаем ограничения на t. Из x = 2 + 3t следует, что целый t не меньше нуля; из y = 2 − 2t следует, что он не больше единицы. Остаются два значения: ноль и один. Они дают пары 2 и 2, а также 5 и 0. Поэтому существование целых решений и существование подходящих неотрицательных решений являются разными вопросами. Если условие требует хотя бы один предмет каждого вида, нулевое количество тоже исключается. Тогда из двух найденных пар останется только первая. Поэтому перед окончательным ответом полезно вернуться к словам исходной задачи: допускается ли отсутствие предметов одного вида, есть ли верхняя граница количества и действительно ли речь идёт о целых единицах.
Попробуйте на практике
Найдите все неотрицательные целые решения уравнения 4x + 6y = 26. Работайте на бумаге и проверяйте каждый этап подстановкой.
- Найдите наибольший общий делитель коэффициентов и проверьте, делится ли на него правая часть. Объясните, что даёт эта проверка.
- Подберите одно целое решение. Затем определите, на сколько можно одновременно изменить x и y, чтобы добавления в левой части взаимно уничтожились.
- Запишите семейство решений через целый параметр t. Превратите условия x не меньше нуля и y не меньше нуля в ограничения для параметра.
- Выпишите допустимые пары и подставьте их в исходное уравнение. Отдельно объясните, почему другие целые значения параметра не подходят условию неотрицательности.
Как проверить результат. Можно начать с пары x = 2, y = 3 и получить x = 2 + 3t, y = 3 − 2t. Допустимы t = 0 и t = 1: пары 2, 3 и 5, 1.
Частые вопросы
Если общий делитель равен единице, решение существует всегда?
Для описанного линейного уравнения и любого целого c существуют целые решения. Но дополнительные ограничения, например неотрицательность, нужно проверять отдельно.
Достаточно найти одну подходящую пару?
Только если задание просит хотя бы одно решение. Когда нужны все решения, необходимо описать семейство и учесть условия, ограничивающие параметр.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.