С. Н. Бочкин Xojiogyes@yandex ru

Вид материала

Подобный материал:

Решение квадратных диофантовых уравнений

С.Н. Бочкин

Xojiogyes@yandex.ru

Научный руководитель: к.т.н., доцент В.Н. Задорожный

Омский государственный технический университет

Предлагается эффективный алгоритм решения квадратных диофантовых уравнений. Задача формулируется следующим образом: заданы положительные целые числа a, b и с. Требуется установить, существуют ли положительные целые числа x и y, такие, что ax²+ by = c?

Задача находится в классе NP полных задач. Возможный вариант исследования данной задачи на предмет наличия корней – перебор всех возможных пар значений x и y. При проведении данного исследования средствами ЭВМ, перебор будет являться ресурсоемким и, ввиду ограниченных возможностей компьютера, сможет охватить большой набор комбинаций коэффициентов, затратив на это большое количество времени. Например, на ЭВМ, способной выполнять триллион операций в секунду, чтобы получить корни уравнения 370x² + 8900y = 45620000 потребуется затратить 10³ лет.

Таким образом, требуется разработать алгоритм решения квадратных диофантовых уравнений, который позволит сделать вывод о наличии корней либо об их отсутствии за более короткий промежуток времени.

Для начала необходимо ввести критерии неразрешимости уравнения.

Во-первых, с должно делиться на наибольший общий делитель а и b.

Во-вторых, должно выполняться условие с > min(a,b).

Предлагается решать задачу путем построения алгоритма для решения линейных диофантовых уравнений, и в дальнейшем искать решения квадратных диофантовых уравнений на множестве решений линейных диофантовых уравнений.

Докажем, что множество решений квадратных уравнений лежит на множестве решений линейных диофантовых уравнений. Общий вид нашего уравнения следующий:

ax²+ by = c.

Произведя замену x² = t, получаем:

at + by = c.

Решая данное линейное уравнение, мы найдем множество решений, включающее все решения исходного уравнения, и останется выбрать из них те значения t, которые являются целыми квадратами уравнения t = x².

Для решения линейных уравнений был использован расширенный алгоритм Евклида [3]. Проиллюстрируем его на примере решения уравнения 23t + 97y = 1.

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

Алгоритм представляет собой последовательность итераций, состоящих из 3 шагов. Ниже представлен рассматриваемый пример состоящий из четырех итераций

Итерация 1:

Шаг 1. Выбирается максимальный из коэффициентов а и b:

Max(23,97) = 97.

Шаг 2. Производится деление найденного максимального элемента на минимальный. Максимальный элемент записывается как произведение частного и минимального элемента плюс остаток от деления:

23t + 23×4y + 5y = 1.

Шаг 3. Производится вынесение за скобки общего множителя и замена выражения, находящегося в скобках, на переменную:

23(t + 4y) + 5y = 1;

a = t + 4y;

23a + 5y = 1.

Итерации повторяются до тех пор, пока наименьший коэффициент при одной из переменных не станет равным единице.

Итерация 2 имеет вид:

Шаг 1. Max(23,5) = 23.

Шаг 2. 5×4a + 3a + 5y = 1.

Шаг 3. 5(4a + y) + 3a = 1;

b = 4a + y;

5b + 3a = 1.

Проверяется условие равенства наименьшего коэффициента единице. Поскольку оно не выполняется производится следующая итерация.

Итерация 3:

Шаг 1. Max(5,3) = 5.

Шаг 2. 2b + 3b + 3a = 1.

Шаг 3. 3(a + b) + 2b = 1;

c = a + b;

3c + 2b = 1.

Проверяется условие равенства наименьшего коэффициента единице. Поскольку оно не выполняется производится следующая итерация.

Итерация 4:

Шаг 1. Max(3,2) = 3.

Шаг 2. c + 2c + 2b = 1.

Шаг 3. 2(c + b) + c = 1;

d = c + b;

2d + c = 1.

На данной итерации мы получили переменную с, у которой коэффициент равен единице, после чего можно произвести обратные подстановки.

c = 1 – 2d,

Принимая d = 1, получаем:

с = -1; Подставляя с = –1 получаем:

b = d – c = 2; Подставляя b = 2 получаем:

a = c – b = -3; Подставляя a = –3 получаем:

y = b – 4a = 14; Подставляя y = 14 получаем:

t = a – 4y = –59.

Множество решений исходного уравнения лежит на множестве чисел

x = x + bn;

y = y – an.

В рассматриваемом примере это:

x = x + 97n;

y = y – 23n.

После применения расширенного алгоритма Евклида, зная, что решение исходного уравнения находится в полученном множестве, можно, путем наращивания n, осуществить поиск возможного решения по формуле x = x + 97n. После каждого вычисления формулы необходимо проверить, является ли найденное значение квадратом целого числа. Если данное условие выполняется, то корень найден и ответ на исходную задачу получен, если нет, то необходимо продолжать поиск.

Для рассматриваемого примера можно сделать вывод, что корни линейного уравнения существуют (так как алгоритм нашел значения x и y), для квадратного диофантового уравнения решений не найдено.

Проверим работу алгоритма на следующих трех тестовых задачах.

11x²+ 7y = 4027. В результате получено решение x = 16, y = -25;

11x²+ 7y = 4026. В результате получено решение x = 18, y = -66;

3500x² + 8000y = 12200000.

Время, затраченное на поиск решений, не превысило 5 секунд. При увеличении коэффициентов время, затрачиваемое на выполнение алгоритма, возрастает незначительно. Например, время поиска корней третьего уравнения составляет 7 секунд.

Библиографический список

Гэри М., Джогсан Д. Вычислительные машины и трудоёмкие задачи: пер. с англ. – М.: Мир, 1982. – 416 с., ил.
Матиясевич Ю.В. Диофантовость перечислимых множеств – ДАН СССР, 191, 2, 1970, 279-282.
Бугаенко В. О. Уравнения Пелля – М.: МЦНМО, 2001г, 32с.

Blog

С. Н. Бочкин Xojiogyes@yandex ru

Решение квадратных диофантовых уравнений

С.Н. Бочкин