РЕШЕНИЕ ДИОФАНТОВЫХ УРАВНЕНИЙ

РЕШЕНИЕ ДИОФАНТОВЫХ УРАВНЕНИЙ

Задача Диофанта: решить уравнение в целых числах: .

Решение существует только в том случае, если числа взаимно просты. В таком случае решений бесконечно много. Если найдено решение , то решениями являются также все числа вида

.

(1)

Достаточно найти какое-нибудь частное решение . Общее решение описывается формулой (1).

Для нахождения частного решения воспользуемся алгоритмом Евклида поиска наибольшего общего делителя НОД(a,b). Дополнительное условие: a > b>0. Обозначим .

Нулевой шаг алгоритма Евклида записывается в виде: ,

или . Аналогичным образом записываются и последующие шаги алгоритма Евклида вплоть до шага с номером n, когда остаток станет равным единице:

i	Вычисления	Цепочка Евклида	(2)
	…………………………………	………
i
	…………………………………
n-2
n-1
n

В последнем равенстве введем обозначения: . Тогда оно примет следующий вид:

.

Теперь осуществим обратный ход. Из равенств (n-1) и (n) исключим : ,

где .

Равенство (n-1) приведено к следующему виду:

.

Аналогичным образом исключим , используя равенство (n-2):

, т.е.

, где .

Таким образом, возникает цепочка равенств следующего вида:

, .

(3)

Каждой паре найденных чисел соответствует тождество:

.

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

.

Учитывая, что , приходим к выводу, что решением уравнения являются числа .