Подскажите, как решить уравнение в целых числах ?

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

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

Пример

2x + 5y = 17 (2)

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

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

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

Получим: 17x0 = 51, 17y0 = –17.

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

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

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

Итак, ответ:

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

Примечание

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