Диофантовы уравнения

Диофантовым уравнением называется уравнение вида , где - известные целые числа, -целочисленные неизвестные, которые нужно найти. Решить такое уравнение – значит найти все пары  удовлетворяющие данному равенству. Их может быть и бесконечно много (и так, как правило, и будет). Как же можно “найти” бесконечное множество таких пар? Как записать ответ?

Имеется в виду, что в ответе может быть параметр, который может принимать бесконечное множество значений. Пример ответа:

. (общее решение данного уравнения)

Последняя строка означает, что - целое число. Имеется в виду здесь – произвольное целое число. То есть выполнено:

1) подставив произвольное  получим некоторое конкретное решение численное решение исходного уравнения.

2) Каждое решение исходного уравнения должно получаться при некотором целом .

Как же нам понять сколько решений имеет заданное диофантово уравнение и как их найти? Обозначим  (такими скобочками обозначают наибольший общий делитель чисел ). Тогда каждое слагаемое слева делится на . Значит, и правая часть должна делиться на . Получили необходимое условие существования решения: , где .

Если это не выполнено, то решений точно нет.

Докажем, что это же условие является также и достаточным условием существования решения, и когда оно выполнено уравнение имеет бесконечное множество решений (имеется в виду, если - ненулевые числа. Иначе у нас уравнение бы просто являлось линейным уравнением с одной переменной, такие случаи здесь не рассматриваем). На  в этом случае мы разделим обе части уравнения и получим новое, в котором   взаимно просты.

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

Пусть - какое-то одно решение данного уравнения. Для нашего примера можно взять . В общем случае существование хоть одного решения будет доказано ниже.

Тогда по определению решения выполнено ;

Рассмотрим новую пару чисел , где - произвольное целое число. И докажем, что это тоже решение исходного уравнения. Подставляем и проверяем.

 - верно. Итак, доказали, что если - какое-то одно решение, то любая пара вида  - тоже решение. То есть доказали (1). Теперь нужно еще доказать, что любое решение исходного уравнения имеет вид  для некоторого целого

Итак, пусть - решение исходного уравнения. Тогда имеем по определению решения . И кроме того для нашего первого рассмотренного решения выполнено . Вычтем из первого равенства второе, получим ;

. Справа целое число, кратное 5, значит слева тоже. Поскольку 3 и 5 взаимно просты,  кратно 5. Обозначим . Тогда слева 15t, значит справа тоже. . Откуда и получим . Итак доказали (2).

Осталось для полного счастья доказать, что всегда найдется такое произвольное решение  (в случае, когда , после сокращения).

Для этого нужно возьмем такие целые  что  (они существуют, поскольку , по теореме о линейном разложении НОД, подробнее о ней в другом листочке). А потом просто возьмем . Как находить такие тоже в листочке другом. Если небольшие  то можно перебором. Всегда найдется такой  от 0 до .