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

Введение.

Эта страница появилась благодаря Казакову Ю.В., который интересуется именно этой тематекой, и я надеюсь пришлет еще не мало интересных алгоритмов. В качестве некоторой вводной, публикую его статью Диофантова задача о «рациональном кубоиде».. Надеюсь, что она Вас заинтересует, если да пишите Юрию Казакову, а я буду рад, если пришлете мне алгоритмы, которые появяться в результате Ваших работ. Наверх

Диофантово уравнение ax+by=c.

Пусть задано диофантово уравнение:

	ax+by=c, где a,b,c- целые

Его частное решение можно найти следующим образом: Находим наибольший общий делитель чисел a и b - НОД(a,b) и запомним частные qi (см. НОД) деления чисел |a| и |b| по алгоритму Евклида. Если НОД(a,b)=c=0, то уравнению удовлетворяют любые целые x и y. Если НОД(a,b) не равен 0 и c на НОД(a,b) не делится, то уравнение не имеет решения. Иначе производим сокращение коэффициентов a,b,c и получаем уравнение того же вида со взаимно простыми a,b,c. Далее находим u и v, такие, что |a|u+|b|v=1 умножив u и v на csgn(a) и csgn(b) соответственно, находим частное решение уравнения x0,y0. Общее решение тогда имеет вид x=x0+kb, y=y0-ka.

Процедура имеет 3 выходных параметра это s типа string для описания ситуации с решением (есть, нет, все целые и т.п.), и частные решения x0,y0 типа integer. Наверх

Диофантово уравнение x2+y2=d2.

Алгоритм прислан Казаковым Ю.В..

Необходимо найти все разложения числа d2 на сумму двух квадратов x2 и y2. x и y - положительные целые числа больше 0. ( Альтернативная формулировка. Найти все прямоугольные треугольники, имеющие целочисленные стороны и длину гипотенузы равную d).

Условие существования разложения d2 на сумму двух целых квадратов требует, чтобы в разложении числа d на множители присутствовало, хотя бы одно простое число вида (4*t+1). То есть должно иметь место представление:

где множитель s не содержит простых сомножителей вида (4*t+1). Количество решений уравнения будет зависить от ki, но не будет зависить от числа s, так как если существует набор пар при s=1, то естественно будет существовать набор и для любого другого s, только каждый элемент пары разложения будут умножен на s. Заметим, что для существования разложения необходимо найти три числа (w,r,q), такие что

	d=w(r2+q2)

тогда

	x=w(r2-q2), y=2wrq.

Таким образом находяться все пары (x,y). Заметим что для пары (x,y) симметричная ей пара (y,x) так же удовлетворяет уравнению, но мы ее в алгоритме на выход не доставляем.

Алгоритм использует выражение вида trunc(a)=a для определения является ли число a целым. Наверх