Уравнение Пелля: мультипликативные свойства и ациклический метод решения

Размещено на http://www.allbest.ru/

уравнение пелля: мультипликативные свойства и ациклический метод решения

В.А. Мешков, канд. техн. наук (ОИР Украины, г. Евпатория)

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

It is the new method of decision for the Pellian equation, allowing simplifying and reducing the computations. The method is generalized for Diophantine equations Giving the examples of method's working and efficiency comparison with the cyclical method.

УРАВНЕНИЯ ПЕЛЛЯ: Мультипликативные свойства И АЦИКЛИЧЕСКИЙ МЕТОД РЕШЕНИЯ

Хотя решению уравнения Пелля и связанных с ним диофантовых уравнений, приводимых к виду , посвящено много работ, интерес к этим задачам теории чисел актуален и в настоящее время. Наиболее известен циклический метод, применяемый еще с древних времен 1. Имеются некоторые разновидности и варианты этого метода (английский метод, метод непрерывных дробей, композиции форм и т.д.), но все они являются той или иной интерпретацией циклического метода (ЦМ). Оказывается, что, при некоторых значениях нахождение начального решения уравнения Пелля требует значительных вычислительных усилий. Большинство современных работ 2-4 также используют в качестве основы ЦМ и во многом опираются на анализ, проведенный, в том числе и в историческом плане, в работе 1.

Предлагаемый в данной работе ациклический метод решения (АЦМ) включает элементы ЦМ, однако не имеет жесткой привязки к фиксированному алгоритму вычислений, и является гибким методом, позволяющим искать и находить оптимальный алгоритм решения для конкретных значений A, щ, используя мультипликативные свойства.

В качестве наводящего примера рассмотрим уравнение Пелля с На пятом шаге ЦМ (см. 1, 1.9, стр.45) приходим к равенству Индийское древнее решение, позволяющее сократить вычисления, применяет возведение в квадрат этого равенства и сокращение на , т.е.

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

При этом под шагом циклического метода (ШЦМ) в соответствии с 1, стр.46 понимаем переход от уравнения , полученного в результате предыдущего го шага, к уравнению .

Это уравнение определяется по результатам операции циклического метода (ОЦМ). Каждая такая операция состоит из умножения уравнения на уравнение , что в результате дает уравнение При этом выбирается такое значение для которого при наименьшем В общем случае такое значение выбирается из ряда решений сравнения

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

(1)

ОК позволяет, если известны решения уравнений с помощью (1) получить решение уравнения

Соответственно ОД означает, что если известны решения уравнений то из решения системы (1) может быть получено решение уравнения

В дальнейшем будем использовать эквивалентные обозначения

 (2)

опуская индексы в очевидных случаях и соотношениях.

В силу квадратичности рассматриваемых уравнений, для любого натурального решения имеем эквивалентные решения в кольце целых чисел, т.е.

(3)

Достаточно часто можно ограничиться полукольцом решений

(4)

Нетрудно видеть, что ОК является составной частью ОЦМ, что может быть записано, как

Возведение в квадрат, использованное выше, также является ОК и представимо в виде матричного уравнения

3

Этот пример показывает, что и при использовании фиксированного алгоритма ЦМ имеются возможности прервать цикл, перепрыгнуть несколько шагов и сократить вычисления. Различные такие частные случаи рассмотрены в качестве примеров и упражнений в 1, разд.1.9.

Ациклический метод, используя все эти приемы, а также ОЦМ и ОК, существенно отличается систематическим использованием ОД, что в ЦМ отсутствует.

На этой основе удается еще более сократить вычисления, необходимые для решения уравнения Пелля.

Действительно, рассмотрим снова уравнение Пелля с На втором и третьем шаге ЦМ (см. 1, стр.45) имеем уравнения Применяем к этим уравнениям ОД, и в этом случае из (1) следует матричное уравнение

(5)

Это матричное уравнение соответствует системе линейных уравнений первого порядка

Нетрудно видеть, что эта система не имеет решения при , поэтому будем искать решения в полукольце (4), тогда, подставляя в первое уравнение, Применяя теперь к этому решению ОК (возведение в квадрат и сокращение), получим искомое решение .

Из этого примера видно, что применив АЦМ, мы используем два шага ЦМ, затем с помощью ОД переходим с третьего на пятый шаг, и с помощью ОК с пятого шага на последний девятый шаг ЦМ. Таким образом, число шагов в АЦМ равно 4. Поскольку в ЦМ первый шаг -- это тривиальное равенство , то число шагов решения в ЦМ равно 8. Применение АЦМ уже в этом простом случае вдвое уменьшило число шагов, без учета того, что в ЦМ порядок чисел и сложность вычислений возрастают с каждым шагом.

В сложных случаях этот эффект гораздо значительнее, и во многом зависит от правильного отбора пробных уравнений. Выше эти пробные уравнения были получены с помощью ОЦМ, однако в АЦМ эти возможности значительно шире и не ограничиваются рамками ЦМ.

Поэтому для «трудных случаев» объем вычислений менее зависит от значений , в отличие от циклического метода, трудоемкость которого существенно и весьма неравномерно возрастает с ростом , как за счет увеличения числа шагов цикла, так и за счет возрастания с каждым шагом порядка чисел.

В наиболее простом варианте, примененном выше, АЦМ состоит из:

1) выбора начального уравнения или ;

2) получение с помощью ОЦМ следующего уравнения ;

3) анализ всего полученного к этому шагу подмножества уравнений ЦМ и принятие решения, переходить к следующему ШЦМ, или найти алгоритм АЦМ и с его помощью решение.

4) если на этапе 3 решение не удается найти, возвращаемся в п.2.

Первым существенным отличием АЦМ от ЦМ является получение и использование некоторого подмножества пробных уравнений из множества уравнений ЦМ. Вторым отличием является применение ОД, что требует «памяти». В ЦМ «памяти» нет, т.к. предыдущие уравнения больше не используются. Третьим отличием является отсутствие фиксированного алгоритма вычислений: для конкретного значения алгоритм надо найти на основании анализа полученного на данный момент подмножества уравнений. Это может вносить, на первый взгляд, субъективный момент в найденный алгоритм АЦМ. Однако этот момент присутствует всегда, когда одна и та же задача может быть решена различными способами. В данном случае нетрудно определить критерий: наилучший алгоритм АЦМ использует наименьшее подмножество пробных уравнений (или ОЦМ) и содержит наименьшее число ОК+ОД (суммарное число операций композиции и декомпозиции). Этот критерий является объективным.

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

Лемма 1. Если имеется решение и начальное решение то существуют такие решения, что

Предположим, что имеем решение . Применим ОК в виде

уравнение пелль диофантовый циклический

Будем считать, что , и с достаточной точностью Отсюда следует, что

Лемма доказана.

Лемма 2. Существуют необходимые и достаточные условия, при которых уравнение (А) имеет решение.

1) Данное уравнение эквивалентно квадратичному вычету и имеет решение, если вычет существует.

2) Из циклического метода следует, что должно существовать уравнение , что эквивалентно квадратичному вычету

Эти условия являются необходимыми для существования решения уравнения (А). Если хотя бы одно из условий не выполняется, решения не существует.

Прямого определения достаточных условий, по-видимому, не существует. Однако доказано, что если решение существует, то оно будет найдено с помощью циклического метода за период повторения [1, стр. 376-377]. В противном случае решения нет.

В АЦМ достаточные условия определяются косвенным путем с помощью мультипликативных свойств.

Пусть имеются решения уравнений . Тогда это является достаточным условием, при котором уравнение (А) имеет решения.

Доказательство. Поскольку имеем решения обобщенных уравнений Пелля, то к ним применимы ОК и ОД. Следовательно, уравнение может быть получено с помощью ОД из уравнения. Но в этом случае должно существовать решение . В противном случае решения также не существует, что противоречит начальным условиям. Лемма доказана.

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

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

(6)

где основная единица, т.е. начальное решение с , , одно из конечных квадратичных целых, соответствующих

В полукольце (4) существует соотношение, аналогичное (6), но с заменой всех знаков при . Соответственно имеем инвариант ( или норму)

и сопряженное с (6) соотношение

(7)

Из свойств основной единицы следует

(8)

Для уравнений, не имеющих решений в (8) используются только четные

Из соотношений (6-8) теперь находим

Соответственно имеем матричное представление для первой последовательности натуральных решений, определяемых квадратичным целым

(9)

Другая последовательность определяется сопряженным квадратичным целым

(10)

Пусть соответствует решению с наименьшими натуральными , тогда для решений внутри первого цикла Для рассматриваемого случая имеем в (6) только эти два квадратичных целых [1, стр.299, упр.7.1], что и доказывает теорему.

Определение. Простыми обобщенными уравнениями Пелля будем называть уравнения, имеющие только две непересекающиеся последовательности решений.

Следствие 1. Пусть известны два последовательных решения уравнения (А), простое число. Тогда с помощью ОД можем найти решение уравнения Пелля если оно неизвестно.

Для случая, когда эти решения относятся к непересекающимся последовательностям и решение уравнения Пелля можно найти с помощью ОК и сокращения.

Имеем

Теперь находим композицию

Отсюда получаем полезную формулу для практического решения уравнения Пелля

(11)

Следствие 2. Пусть известны решения уравнений простые числа. Тогда с помощью ОД можем найти решение уравнения если оно неизвестно.

Пусть теперь

Для этого случая решение можно найти с помощью ОК и сокращения.

Аналогично имеем формулу для практического решения обобщенного уравнения Пелля

(12)

Следствие 3. Пусть известны решения уравнений простое число. Аналогичная формула, позволяющая найти решение уравнения имеет вид

(13)

Следствие 4. Полученные соотношения (9-13) остаются справедливыми и в тех случаях, когда не являются простыми числами, но соответствуют простым обобщенным уравнениям Пелля.

Следствие 5. Для простых обобщенных уравнений Пелля ОД соответствует ОК с сокращением в кольце целых чисел (4).

Действительно, в соответствии с (1) ОД определяется соотношением

Умножим теперь последнее равенство на сопряженную матрицу и получим



В дальнейшем ОД= ОК с сокращением будем записывать в виде

(14)

Теорема. Пусть - число ШЦМ, необходимое для нахождения решения уравнения Пелля с помощью ЦМ. Тогда в худшем случае алгоритм АЦМ содержит последовательных ШЦМ и одну ОД.

Доказательство.Начальное уравнение ЦМ имеет вид , и после каждого -го ШЦМ имеем уравнение Из основного свойства ЦМ следует, что Если - четное число, то не имеет пары, а после последовательных ШЦМ имеем первую пару уравнений с . Если - нечетное число, то все уравнения имеют пару, и первая соответствует значениям . Таким образом, необходимая пара уравнений получается за шагов, целая часть числа.

Используя теперь свойства кольца (4) и применяя ОД в виде



найдем решение уравнения Пелля. Теорема доказана.

На практике такой худший алгоритм АЦМ может реализоваться для ЦМ с малым числом шагов. В «трудных» случаях эффективность АЦМ резко возрастает.

Рассмотрим теперь, как в конкретных случаях можно находить алгоритм решения АЦМ.

При использовании некоторого числа последовательных операций ЦМ нет необходимости вычислять Как показано в [1, стр.50, упр.1.9.4-5], для того, чтобы определить необходимое число шагов в ЦМ, не надо вычислять решение. Таким же образом находим минимальное множество начальных шагов ЦМ, необходимых для построения алгоритма АЦМ. На каждом шаге достаточно вычислять значения , используя рекуррентные формулы Начальные значения соответствуют Для рассмотренного выше примера полная таблица всех значений за цикл имеет вид

	0	1	2	3	4	5	6	7	8
	1	8	7	5	9	9	5	7	8
	1	-3	6	-7	-2	-7	6	-3	1

Из таблицы следует, что для алгоритма АЦМ достаточно два первых шага ЦМ (закрашены серым). Далее ход решения соответствует уже полученному выше и кратко записывается в виде



Здесь знаком обозначаем ОК с сокращением общих множителей и для случаев, рассмотренных в Следствиях 1-5, совпадающих с ОД. Соответственно ОД в кольце целых чисел (3) или (4), соответствующий второй строчке (14) будем обозначать ОЦМ, после того, как найдено значение , соответствует ОД= ОК с сокращением. Например,

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

Так, для после трех ШЦМ имеем таблицу

	0	1	2	3
	1	12	13	11
	1	5	6	-3

Алгоритм АЦМ аналогичен предыдущему, и содержит 3 ШЦМ. Получаем решение

Рассмотрим вспомогательные приемы, позволяющие упростить вычисления в АЦМ. В зависимости от конкретного, строить алгоритм решения и выбирать пробные уравнения следует так, чтобы кратчайшим путем получить уравнения, где правая часть имеет значения из ряда Для первых двух случаев решение уравнения Пелля получаем возведением в квадрат, как это было сделано выше для . Фактически в этих случаях решение вычисляется по формулам

(15)

В последнем случае решение получаем в два этапа

(16)

Аналогично для значений , когда решений не существует, но есть решение находим

(17)

Заметим, что (15-17) можно рассматривать, как соотношения между рациональными числами, у которых числитель и знаменатель натуральные взаимно простые числа. Соответственно для правой части (16-17) свойства должны обеспечивать это условие.

Нетрудно найти условия, когда решения существуют. В этом случае имеем уравнение , что является частным случаем сравнения

Таким образом, необходимым условием является существование квадратичного вычета по модулю .

С другой стороны, из существования решения , и теории, изложенной в 1, (раздел 1.7) следует, что в этом случае является суммой двух квадратов, и также суммой двух квадратов будут решения

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

(18)

Понятно, что значения характеризуют точность рационального приближения, а наилучшие приближения соответствуют значениям

В качестве конкретных примеров рассмотрим частные случаи уравнения Пелля, предложенные в свое время Ферма (см. 1, стр.46-48). Для значений это случаи . При этом отмечается, что первый случай трудный, а два следующих очень трудные.

В первом случае имеем , где последнее выражение в правой части означает, что

С помощью формулы (16)получаем первое решение для

Далее применяем первую формулу (15) и получаем решение уравнения Пелля, т.е. первое решение для

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

.

Теперь нетрудно получить решение тем же способом, что и (11-12). Вычисления удобно свести в таблицу

A	p	q
109	261	25	26134062	2534061		2253406126134062
149	61	5	611862	51861		251861611862

Из этих примеров следует, что АЦМ основан на целенаправленном поиске пробных уравнений для значений т.к. решение для далее можно вычислить просто по формулам.

С ростом значений находить нужные пробные уравнения методом проб или с помощью рациональных приближений может оказаться затруднительным, и тогда следует применять ОЦМ. Рассмотрим случаи которые считаются самыми трудными из предложенных Ферма.

Для первого из них с помощью ОЦМ получим ряд пробных уравнений ЦМ, записываемых в виде

Этих данных уже достаточно для использования алгоритма АЦМ:

Имея это решение, далее с помощью формул находим решение для и затем решения

Аналогично (12) вычисляем решение для

Однако для уравнения с такой способ вычислений не подходит по причинам, которые будут понятны ниже. В данном случае, варьируем с помощью ОЦМ, но полученное подмножество пробных уравнений не принадлежит ЦМ.

(14)

Этих уравнений оказывается достаточно, чтобы найти решение с помощью АЦМ.

И теперь по формулам нетрудно получить решение для

Оказывается, что в случае решений с взаимно простыми нет, как и решений .

Это общее свойство уравнений с В этом случае имеем

Но разность двух квадратов не может быть равна нечетному числу, умноженному на 2. Далее рассмотрим



Если нечетны, то

.

Поэтому предыдущее равенство невозможно, что и доказывает указанные выше свойства уравнений с

Аналогичное рассмотрение для уравнений с нечетное, показывает, что решений с и в этом случае не существует, но для решения с нечетными существуют.

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

С современной точки зрения и современных вычислительных возможностей предложенные Ферма уравнения не являются слишком трудными. В приложении рассмотрены более сложные задачи и проведено сравнение эффективности современных компьютерных алгоритмов, основанных на ЦМ, с эффективностью алгоритмов АЦМ. Для этого использовались результаты 5, где найдено, что значения являются рекордными по числу шагов ЦМ, в том смысле, что уравнения Пелля с меньшими , решаются за меньшее число шагов. Кроме этих значений сравнение зффективности проведено для всех значений, рассмотренных в статье. Дополнительно рассмотрен случай , для которого приведено решение АЦМ. Для случая такого решения не приводим, чтобы читатель мог использовать его для самоконтроля.

Для достаточно больших задача нахождения алгоритма АЦМ становится все более нетривиальной, и интересным представляется вопрос о существовании наиболее короткого и тем самым наиболее эффективного алгоритма. В рассмотренных примерах эффективность увеличивалась с ростом , и для последних рассмотренных значений выигрыш только за счет уменьшения шагов вычисления составил более чем в 30 раз. При этом реализуется принцип: больше анализируем, меньше вычисляем.

Представляет интерес, что хотя отдельные приемы прерывания цикла известны с древних времен, сформулировать АЦМ в общем случае удалось только в настоящей работе.

Литература

[1] Эдвардс Г. Последняя Теорема Ферма. Генетическое введение в алгебраическую теорию чисел. М., Мир, 1980.

[2] Lenstra Jr. H.W. Solving the Pell Equation. Notices of AMS, v.49, p.182-192.

[3] Barbeau E.J. Pell's equation. Problem Books in Mathematics. Springer-Verlag, N.Y., 2003.

[4] Williams H.C. Solving the Pell Equation. Number Theory for the millennium, III (Urbana, IL, 2000), A.K. Peters, Natick, MA, 2002, p. 397-435.

[5] Oliveira e Silva T. Large fundamental solutions of Pell equation. Web site.http://www.iee ta. pt/~tos/.

Приложение 1. Сравнение зффективности циклического и ациклического методов

На сайтах Интернета существуют компьютерные программы решения уравнения Пелля и обобщенного уравнения Пелля, например, использованная в 5. Эффективность алгоритма будем оценивать по числу шагов ЦМ или АЦМ, необходимых для получения решения. Далее представлены результаты, полученные для некоторых «трудных» случаев, компьютерное исследование которых проведено в 5 на основе ЦМ, и для ряда более простых случаев. Поскольку в АЦМ для решения уравнения Пелля достаточно найти решения обобщенных уравнений Пелля для , то число шагов АЦМ соответствует получению этих значений. Далее решение уравнения Пелля мы не приводим, т.к. оно вычисляется по формулам (15-17).

Табл. П1. Число шагов для получения решений в ЦМ и АЦМ.

Значения А	61	67	109	139	149	421	433	991	1201
ЦМ	2	-	4	-	2	8	-	-	-
ЦМ	-	4	-	6	-	-	-	22	-
ЦМ	7	-	11	-	7	25	15	-	33
ЦМ	14	8	22	12	14	50	30	44	66
АЦМ	2	4	1	5	1	5	7	14	11

Значения А	1549	3061	9221	56149	92821
ЦМ	15	23	-	121	169
ЦМ	-	-	-	-	-
ЦМ	51	74	24	349	503
ЦМ	102	148	48	698	1006
АЦМ	8	9	10	24	31

Приложение 2. АЦМ алгоритмы для некоторых уравнений Пелля.

	0	1	2	3	4	5	6	7	8
	1	31	29	31	29	35	43	23	40
	1	-30	5	-6	25	-39	-22	21	29

	9	10	11
	18	28	26
	-23	9	-35

	0	1	2	3	4	5	6
	1	35	37	33	31	29	19
	1	24	7	-16	15	-24	35

	0	1	2	3	4	5
	1	39	45	40	38	32
	1	-28	-17	-3	35	-15

	0	1	2	3	4	5	6
	1	55	53	52	50	60	38
	1	-36	7	-51	11	49	-33

	0	1	2	3	4	5	6	7	8
	1	237	243	192	207	193	185	279	282
	1	20	145	-133	100	-189	116	187	125
		4·5	5·29	-7·19	4·5·5	-3·3·3·7	4·29	17·11

	9	10	11	12	13	14	15	16	17
	218	265	143	207	249	213	207	268	227
	-69	-204	175	-76	-77	140	-95	-165	28
	-3·23	-4·3·17		-4·19	7·11	5·4·7	5·19	5·11·3

	1	2	3	7	8	9
	305	307	302	302	292	395
	204	7	-231	-33	229	276
	4·3·17		-3·7·11	-3·11		3·4·23

	10	11	12	13	14	15	16	17	18
	157	337	335	358	254	301	299	271	273
	-247	-84	-231	-153	185	-12	285	-68	269
	-13·19	-4·3·7	-3·7·11	-3·3·17	5·37	-3·4	3·5·19	-4·17

	18+	19	20	21	22	23	24
	341	265	323	362	196	194	372
	-345	-84	-137	-279	195	-283	-161
	-3·5·23	-3·4·7		-3·3·31	3·5·13		-7·23

Приложение 3. Последовательность вычислений в АЦМ



Размещено на Allbest.ru

...