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

Найти все целые x и y, такие, что ax + by = c (где a, b, c – целые числа).

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

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

Пример

2x + 5y = 17 (2)

Сначала найдём множество решений уравнения 2x + 5y = 1.

2 × 3 – 5 × 1 = 1, поэтому можем считать, что x₀ = 3, y₀ = –1.

Поскольку мы решаем уравнение 2x + 5y = 17, а не 2x + 5y = 1, то значения x₀ и y₀ нужно увеличить в 17 раз.

Получим: 17x₀ = 51, 17y₀ = –17.

В этом случае 2 × (17x₀) + 5 × (17y₀) = 17.

Но задача состоит в том, чтобы найти все пары целых чисел, удовлетворяющих равенству (2).

Если увеличить 17x₀ на 5t, а 17y₀ уменьшить на 2t (где t – некоторое целое число), то пара чисел x = 17x₀ + 5t и y = 17y₀ – 2t будет удовлетворять условию (2), поскольку слагаемое 2x увеличится на 10t, а слагаемое 5y уменьшится на 10t.

Итак, ответ:

x = 51 + 5t, y = –17 – 2t.

Примечание

Некоторые линейные диофантовы уравнения имеют пустое множество решений, например, 6x + 21y = 2. При этом левая часть равенства кратна 3, а правая часть равенства не кратна 3.