Математика · объяснение и практика

Когда у ax + by = c существуют целые решения

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

Синяя и оранжевая половины складываются в целый круг.

В теме Теория чисел: углубление · Учебная карта

Главная мысль

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

Обычное линейное решение не гарантирует целое

Над действительными числами уравнение с двумя неизвестными обычно задаёт прямую. Но целочисленная задача спрашивает, проходит ли она через узлы решётки. Любой общий делитель a и b делит левую часть при целых x и y, поэтому он должен делить c. Например, 10x+15y = 7 невозможно в целых числах: левая часть кратна пяти, правая нет.

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

Как описать все целые пары

Рассмотрим 6x+9y = 30. Делим на три и получаем 2x+3y = 10. Подходит x₀ = 2, y₀ = 2. Прибавление трёх к x увеличивает левую часть сокращённого уравнения на шесть, а вычитание двух из y уменьшает её на столько же. Поэтому все пары x = 2+3t, y = 2−2t при целом t сохраняют равенство.

Чтобы увидеть полноту, вычтем частное решение из произвольного: 2(x−2) = −3(y−2). Взаимная простота двух и трёх заставляет x−2 делиться на три, а y−2 на два с согласованным знаком. Значит, никакие другие целые пары вне серии не скрылись. Это важный шаг: проверка сохранения равенства показывает допустимость серии, а аргумент делимости — её полноту.

Пример

Выберите неотрицательные решения 6x+9y = 30 из найденной серии.

Условия 2+3t ≥ 0 и 2−2t ≥ 0 дают целые t = 0 или t = 1. Получаем (2; 2) и (5; 0). Целых решений бесконечно много, но требование неотрицательности оставляет две пары.

Дополнительные условия меняют окончательный ответ

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

Если a и b одновременно равны нулю, формула с делением на их НОД не применяется. Остаётся равенство 0 = c: при c = 0 подходят все целые пары, иначе ни одна. Один нулевой коэффициент тоже удобно рассмотреть напрямую. Такая проверка не позволяет общему красивому выражению скрыть случаи, где исходная задача уже стала проще.

От чтения к действию

А теперь — вы

Имеет ли 14x+21y = 10 целые решения?

Частые вопросы

Если НОД делит c, неотрицательное решение обязательно есть?

Нет. Критерий гарантирует целые пары без ограничений на знаки. Неотрицательность нужно исследовать отдельно.

Почему одной найденной пары недостаточно?

Она подтверждает существование, но не описывает все решения. Для полноты нужна параметрическая серия и обоснование, что любая целая пара входит в неё.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться