Уравнения пелля и их применения

Реферат: по математике «Уравнения Пелля»

Министерство образования и науки

Муниципальное образовательное учреждение

средняя общеобразовательная школа №33

ученик 9 «А» класса

Петров Алексей Андреевич

учитель математики Фоменкова Татьяна Анатольевна

Глава 1. Линейные диофантовы уравнения…………………………………4

1.1 Что такое линейные диофантовы уравнения……………………………4

1.3 Графический способ решения линейного диофантова уравнения …. 6

1.4 Общее решение линейного диофантова уравнения …………………. 8

Глава 2. Уравнения Пелля…………………………………………………. 9

2.1 Что такое уравнения Пелля ……………………………………………..9

2.2 Пример: уравнение х 2 – 2у 2 =1 ……………………………………. 10

2.3 График уравнения Пелля …………………………………………. 11

2.4 Общее решение уравнения Пелля ………………………………………13

2.5 Решение уравнения Пелля, основанное на цепных дробях …………. 14

С понятием «уравнение» на уроках математики мы знакомимся ещё в начальной школе, а задача «решить уравнение», вероятно, наиболее часто встречающаяся задача.

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

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

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

На протяжении более трех веков человечество пыталось решить эти уравнения и до сих пор современные математики ищут наиболее эффективные методы решений уравнений Пелля и знаменитого уравнения Ферма: х n +у n =z n , n>2.

Нашей целью будет научиться находить решения диофантова уравнения первой и второй степеней, если это решение имеется.

Для этого, необходимо ответить на следующие вопросы:

1. Всегда ли линейное диофантова уравнение и уравнение Пелля имеет решение, найти условия существования решения;

2. Имеется ли алгоритм, позволяющий отыскать решение диофантова уравнения.

§1. Линейные диофантовы уравнения.

1. Что такое линейные диофантовы уравнения.

Определение : Линейные диофантовы уравнения — это диофантовы уравнения вида

ах+bу=с, (1)
где а, b и с — некоторые целые числа, причём а и b не равны нулю одновременно.
Ответим сначала на вопрос, имеет ли линейное уравнение хотя бы одно решение.

Обозначим через d наибольший общий делитель чисел а и b. Если число с не делится на d, то решений нет, поскольку при любых х и у левая часть (1) делится на d, а правая — не делится.
Пусть теперь с = kd. В этом случае решение существует. Чтобы это доказать, достаточно показать, что имеет решение уравнение
ах+bу=d. (2)
Действительно, умножив решение (т. е. каждое из чисел х и у) уравнения (2) на k, получим решение уравнения (1).

Один из методов нахождения решения уравнения (2) основан на алгоритме Евклида.

2. Алгоритм Евклида.
Алгоритм Евклида служит для нахождения наибольшего общего делителя двух целых положительных чисел. Он основан на следующем простом наблюдении. Если а = bq+r (где q — частное, а r — остаток от деления а на b), то НОД (а, b) = НОД (b, r). Действительно, из формулы деления с остатком следует, что любой общий делитель чисел b и r является также делителем числа а, а любой общий делитель чисел а и b является также делителем числа r. Поэтому множества общих делителей пар чисел (а, b) и (b, r) совпадают, а значит, совпадают и их наибольшие общие делители.
Применение алгоритма Евклида заключается в последовательном делении с остатком. Сначала мы делим большее из двух чисел на меньшее. На каждом следующем шаге мы делим число, которое на предыдущем шаге было делителем, на число, которое было остатком. Так поступаем до тех пор, пока не получим нулевой остаток. Это обязательно произойдёт через конечное число шагов, поскольку остатки всё время уменьшаются. Последний ненулевой остаток и будет наибольшим общим делителем исходных чисел.
Алгоритм Евклида, применённый к паре чисел (а, b), где а > b, может быть записан в виде цепочки равенств
a=bq₁ + r_1,

r_{n -1} =r_n q_{n +1} . Тогда d = НОД (а, b) = НОД (b, r₁ ) = . = НОД (r_{n -1} , r_n ) = r_n .
Покажем теперь, как найти решение уравнения (2) с помощью цепочки равенств (3). Выразим d=r_n из предпоследнего равенства. В полученное выражение подставим значение r_{n -1} из предыдущего равенства и т. д. Продолжая этот процесс, в конце концов получим выражение d в виде левой части уравнения (2).
Для примера рассмотрим уравнение 355х + 78у = 1.

1. Сначала найдём наибольший общий делитель чисел 355 и 78 с помощью алгоритма Евклида:
355= 78 • 4+43,
78=43•1+35,
43= 35•1+ 8,
35=8•4+3,
8=3•2+2,
3= 2•1 + 1,
2=1•2.
Итак, НОД (355, 78) = 1. Перепишем полученные равенства в виде
43=355 — 78•4,
35=78 — 43•1,
8=43 — 35•1,
3=35 — 8•4,
2=8 — 3•2,
1=3 — 2•1.
2. Теперь пойдём по цепочке равенств снизу вверх:
1 = 3 — 2•1 = 3 — (8 — 3•2) •1 = 3•3 — 8 = (35 — 8•4) •3 — 8 =
= 35•3 — 8•13 = 35•3 — (43 — 35•1) •13 = 35•16 — 43•13 = (78 — 43•1)•16 — 43•13 = 78•16 — 43•29 = 78•16 — (355—78•4) •29 = 78•132 — 355•29.
Найдено решение: х = -29, у = 132.
Нам осталось ответить на вопрос: как, зная одно решение линейного диофантова уравнения, найти все? Чтобы ответить на него, разберём сначала один пример.

3. Графический способ решения линейного диофантова уравнения.
Рассмотрим пример: уравнение 3х + 5у =22.
Подбором легко найти одно из решений этого уравнения, например, х=4, у =2. Применение алгоритма Евклида приводит к другому решению: х = 44, у = -22.
Нарисуем на координатной плоскости график уравнения — множество точек (х, у), таких что х и у удовлетворяют этому уравнению. Этот график представляет собой прямую (рис. 1), которую мы обозначим через l . На ней нужно найти все точки с целыми координатами (которые мы для простоты будем называть целыми точками). Из рисунка видно, что точки (4,2) и (-1,5) лежат на прямой l и на отрезке между этими точками других целых точек нет. Конечно, ссылка на график не является доказательством. Однако доказать это несложно: непосредственно проверяем, что указанные пары чисел удовлетворяют уравнению, а при у =3 и у =4 значения х, получаемые из уравнения, оказываются нецелыми.
Заметим, что если пара (х₀ , у₀ ) — решение уравнения, то пара (х₀ -5, у₀ +3) тоже решение:
3(х₀ — 5)+ 5(у₀ +3) =3х₀ – 15 + 5у₀ + 15 = 3х₀ + 5у₀ = 22.

Преобразование (х, у) → (х-5, у+3), (4)
во-первых, сохраняет прямую l (оно является параллельным переносом вдоль неё), во-вторых, переводит целые точки в целые, и поэтому любое решение уравнения переводит в решение.

Рис. 1 График уравнения 3х + 5у =22.

Применяя к уже найденному решению преобразование (4), т. е. прибавляя к х число (-5), а к у число 3, мы получим ещё одно решение, потом ещё одно и т.д. Точки, соответствующие этим решениям, располагаются на прямой 1 через равные расстояния (см. рис. 1). Ясно, что можно двигаться и в обратную сторону.
Таким образом, мы нашли бесконечную серию решений
х=4 – 5t, у=2 + 3t, где t — любое целое число.

Докажем, что любое решение имеет такой вид.

Рассуждаем от противного: пусть на прямой 1 между точками (4 – 5t, 2 + 3t) и (4 -5(t+1), 2+3(t+1)) найдётся целая точка. Применяя несколько раз параллельный перенос (4), если t 0, мы получим, что на интервале между точками (4,2) и (-1,5) тоже есть целая точка. Противоречие.
Итак, мы нашли все решения уравнения и доказали, что других нет.

4. Общее решение линейного диофантова уравнения. Перейдём теперь к рассмотрению общего случая. Рассмотрим графики уравнений (1) при фиксированных а и b и пробегающем всевозможные целые значения параметре с. Это — бесконечное множество параллельных прямых l _с , причём каждая целая точка принадлежит ровно одной такой прямой (рис.2).

Рис. 2. Графики уравнений ах+bу=d.

Введём на координатной плоскости «сложение» точек:

(х₁ , y₁ ) + (х₂ , y₂ )= (х₁₊ х₂ , y₁₊ y₂ ).
Введённая операция сложения целых точек определена также на подмножестве целых точек. Действительно, сумма двух целых точек является целой точкой.
Эта операция имеет естественную геометрическую интерпретацию: она соответствует сложению векторов с началами в начале координат и концами в данных точках. Как и обычное сложение, сложение точек имеет обратную операцию — вычитание.
Чтобы найти общее решение уравнения (1), нужно к его частному решению добавить общее решение уравнения

Осталось решить это уравнение. Снова введём d=НОД (a,b). Тогда a=a’d, b=b’d, где НОД (a’, b’)=1. Уравнение (5) перепишется в виде

а так как а’х делится на b’ и a’ взаимно просто с b’ , то х делится на b’ .

Значит, х=b’ t, откуда у=- a’ t.

Теперь можем резюмировать. Если с не делится на НОД (a,b), то уравнение (1) решений не имеет. Если же с делится на НОД (a,b), то уравнение (1) имеет бесконечно много решений, получаемых по формулам

х=х₀ +, у=у₀ —,

где t – произвольное число, d= НОД (a,b), а (x_0, y₀ ) – частное решение, которое может быть найдено с помощью алгоритма Евклида.

§2. Уравнения Пелля.

1. Что такое уравнение Пелля?
Определение: Уравнения Пелля — это уравнения вида

х 2 — mу 2 =1, (6)
где т — целое положительное число, не являющееся точным квадратом.

Они представляют собой класс диофантовых уравнений второй степени и связаны со многими важными задачами теории чисел. Прежде всего сделаем два замечания. Во-первых, при любом т. уравнение (6) имеет по крайней мере два решения: х = 1, у = 0. Эти решения мы назовём тривиальными. Во-вторых, поскольку при изменении знака у х или у левая часть уравнения (6) не изменится, достаточно ограничиться нахождением только неотрицательных решений (т. е. решений с неотрицательными х и у).

Решая уравнение Пелля, мы будем отвечать на три вопроса.
1) Существует ли хотя бы одно нетривиальное решение?
2) Если да, то как его найти?
3) Как описать все решения?

Заметим, что ограничение на параметр т является естественным. Если т — точный квадрат, то уравнение (6) не имеет нетривиальных решений.

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

2. Пример уравнения: х 2 — 2y 2 =1.

Рассмотрим уравнение Пелля при m=2: х 2 — 2y 2 =1.
Несложная выкладка показывает, что если пара (х, у) является решением рассматриваемого уравнения, то пара (3х + 4у, 2х + 3у) тоже его решение. Действительно,
(3х + 4у) 2 — 2(2х + Зy) 2 = (9х 2 + 24ху + 16у 2 ) —
— 2(4х 2 + 12ху+9у 2 )= x 2 — 2у 2 . Поэтому если х 2 — 2у 2 = 1, то и (Зх+4у) 2 – 2 (2х+Зу) 2 = 1.

Значит, исходя из тривиального решения х₀ = 1, y₀ = 0, мы можем получить бесконечную последовательность (нетривиальных) решений (x_{i ,} у_i ) с помощью рекуррентной формулы (х_i ,у_i ) = f (x_{i -1} ,y_{i -1} ), где f (х, у) = (3х + 4у, 2х + 3у). Вот несколько первых её членов: (3,2), (17,12), (99,70), (577,408).

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

Неотрицательные решения уравнения Пелля можно естественным образом упорядочить, для этого рассмотрим на координатной плоскости множество точек, удовлетворяющих соотношению х 2 — 2у 2 = 1, лежащих в первой координатной четверти. Это — график функции у=, определённой при х 1 (рис. 3).

Рис.3. График функции у=.

Будем говорить, что точка на этом графике тем больше, чем дальше она находится от точки (1,0). Поскольку функция монотонна, большей из двух точек графика будет та, у которой больше как абсцисса, так и ордината. Неотрицательные решения уравнения Пелля суть целые точки на графике. Поэтому неравенство (х’, у’) 2 — 2у 2 = 1, не совпадающее ни с одним из членов построенной последовательности (х_i ,у_i ). Поскольку х_i и y_i неограниченно возрастают, решение (х’,у’) лежит между какими-то двумя решениями из последовательности: (х_i ,у_i ) 2 -my 2 =1- это гипербола (рис. 4), асимптотами которой являются прямые . Чтобы убедится в этом, разложим левую часть уравнения на множители:

и введём новую (косоугольную) систему координат, направив ось Ох’ вдоль прямой , а ось Оу’- вдоль прямой . В системе координат Ох’у’ уравнение нашей кривой запишется в привычном виде: х’у’= const.

Рис.4. График уравнения x 2 -my 2 =1

При любом m гипербола проходит через точку (1, 0) и симметрична относительно обеих координатных осей.

Вместе с гиперболой х 2 — mу 2 = 1, рассмотрим серию кривых l_{n ,} задаваемых уравнениями х 2 — m у 2 =n, где п — всевозможные целые числа (рис. 5). Кривые l _n при n0 представляют собой гиперболы, а l ₀ — это пара прямых у =, являющихся общими асимптотами этого семейства гипербол.

Рис.5 Графики уравнений х 2 — m у 2 =n.

Поскольку для любой целой точки величина х 2 — ту 2 является целым числом, каждая целая точка попадает на один из графиков l_n . Так как т не является точным квадратом, на l ₀ (паре асимптот) лежит лишь начало координат. Все остальные целые точки лежат на гиперболах.

С каждой гиперболой l_n связана сопряжённая ей гипербола l _{— n} . Если мы выберем на одной из гипербол пару центрально-симметричных относительно начала координат точек, то на сопряжённой гиперболе можно выбрать такую пару центрально-симметричных точек, чтобы все четыре точки были вершинами параллелограмм со сторонами, параллельными асимптотам. Такие пары точек будем называть сопряжёнными друг другу. Действительно, если в системе координат, оси которой идут вдоль асимптот, пара симметричных точек имеет координаты (х’, у’) и (-х’, -у’), то сопряжённой ей в той же системе координат является пара симметричных точек (х’,-у’) и (-х’,у’).

4. Общее решение уравнения Пелля.

Если уравнение Пелля имеет хотя бы одно нетривиальное решение, то, умножая его многократно на себя, можно найти бесконечно много решений. При этом все решения можно найти аналогично тому, как мы действовали в частном случае m =2. Двигаясь по графику уравнения (рис.6) из точки (1,0) в направлении положительных значений y , находим первое нетривиальное решение. Это решение назовём основным .

Рис.6. График уравнения x 2 -3y 2 =1

Теорема 1. Все нетривиальные положительные решения получаются многократным умножением основного решения на себя.

Доказательство. Рассмотрим последовательность (x₁ ,y₁ ), (x₂ ,y₂ ), …, (x_n ,y_n ),… решений, получаемых из основного решения (x₁ ,y₁ ) последовательным умножением на него. Предположим, что на графике уравнения между двумя её членами (x_n ,y_n ) и (x_{n +1} ,y_{n +1} ) имеется некоторое решение. Умножив его на (x₁ ,-y₁ ), получим новое решение, лежащее между (x_{n -1} ,y_{n -1} ) и (x_n ,y_n ). Действительно, умножение на (x₁ ,-y₁ ) является обратной операцией к умножению на (x₁ ,y₁ ). Проделав такую операцию n раз, получим решение, лежащее между (1,0) и (x₁ ,y₁ ). Это противоречит тому, что (x₁ ,y₁ ) – основное решение.

Теорема 2. Любое уравнение Пелля имеет нетривиальное решение.

5. Решение уравнения Пелля, основанное на цепных дробях.

Введем понятие цепных дробей.

Любое нецелое число можно представить в виде, где -целое число, а>1. Действительно, в качестве нужно взять целую часть числа , а в качестве — обратное число к его дробной части . Такое представление единственное , поскольку из условия >1следует, 0 у>0 и >1, то х+у>2у.

Значит, 1=х 2 – mу 2 = (х — у)(х+у)>(х — у)· 2у.

Исследовательская работа. Уравнение Пелля

XX городская конференция-фестиваль творчества молодёжи и школьников.

Исследовательская работа

Уравнение Пелля

Автор: Садовой Иван

Чувашская Республика

Чебоксары — 2005 год.

Постановка задачи …………………………………………………………….. 3 Способы отыскания всех решений …………………………………………. 4

3. Способы отыскания наименьшего решения ………………………………… 5

Приложение 1. Уравнение Пелля в древнегреческой литературе

Приложение 2. Пакет программ для компьютера

Уравнение Пелля имеет большое значение в теории диофантовых уравнений. Например, было доказано, что любое диофантово уравнение сводится к уравнению четвёртой степени, которое в частных случаях сводится к уравнением Пелля. Таким способом с помощью уравнения Пелля была решена десятая проблема Гильберта. С помощью решений уравнения Пелля легче приближать «чистые» иррациональности, чем другими методами. Стоит отметить, что точность приближения действительных чисел очень важна в производстве механических часов (точность часов пропорциональна качеству приближения). Так же в кристаллографии используют представление чисел квадратичной формой, частным случаем которой и является уравнение Пелля.

Изучением данной проблемы интересовался сам Архимед. Сохранился текст задачи, которую он послал своему оппоненту Эратосфену. Она сводилась к уравнению Пелля с коэффициентом a = 4729494. Дальнейшее изучение было произведено в Индии, где впервые был сформулирован метод (индийский) нахождения наименьшего решения для любого коэффициента. Позже в Англии Броункнером был разработан другой метод (английский), аналогичный предыдущему, но более удобный. Но у известного математика Леонарда Эйлера осталось впечатление, что решение принадлежит другому английскому математику Пеллю, поэтому он и назвал это уравнение уравнением Пелля. В XIX-XX веках выяснилось, что решения уравнения Пелля являются числителями и знаменателями подходящих дробей к «чистым» иррациональностям. С тех пор изучением проблемы стали заниматься многие знаменитые математики. были исследованы обобщённые уравнения Пелля, но проблема актуальна и сейчас. В настоящее время появилась возможность использования компьютера для дальнейших построений оптимальных алгоритмов решения уравнения Пелля. В связи с этим стала актуальна проблема поиска «быстрых» алгоритмов, чему и посвящена данная работа.

Уравнение вида x2 – ay2 = 1 (1), где a – целое положительное число, не являющееся квадратом, называется уравнением Пелля или неопределённым уравнением Ферма.

Каждое уравнение Пелля имеет решение (±1;0), которое называется тривиальным. Все остальные решения называются нетривиальными.

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

Ограничение на a является естественным. Если а — квадрат, то разность двух квадратов равна 1 только тогда, когда первый из них единица, а второй ноль. Если же a — отрицательное число, то решения очевидны: если a = -1, то решениями являются пары (±1;0) и (0;±1), если , то только (±1;0).

Решений уравнения Пелля бесконечно много. Доказывается это с помощью бинома Ньютона следующим образом. Двучлен , где x0,y0 — наименьшее нетривиальное решение, возводится в n-ую степень и раскладывается по биному Ньютона. Если привести подобные слагаемые, то получается выражение вида , где хn, уn — целые числа. Далее надо провести аналогичные операции для сопряжённого двучлена. В результате получается следующая система уравнений:

Далее следует перемножить эти равенства и свернуть по формуле разности квадратов, в результате получается уравнение с переменными хn и уn (1). Получается, пара чисел хn, уn тоже является решением. Т. к. число n может принимать бесконечное множество значений, то решений уравнения (1) тоже бесконечное множество.

2.Способы отыскания всех решений

Существует три метода нахождения «всех» решений уравнения (1).

Первый способ основан на формулах (2). Доказывается, что все абсолютно все решения получаются в результате возведения в n-ую степень двучлена . Этот способ удобен при нахождении решения «вручную», так как надо работать с целыми числами, выполняется «мало» операций и не требуется никаких данных, кроме наименьшего решения. Но при компьютерной реализации возникают проблемы. Во-первых, сложность представления. Требуется создавать множество дополнительных переменных, вводить треугольник Паскаля и n+1 слагаемых, возводить в степени «большие» числа, для чего на многих языках программирования требуется создавать отдельную функцию. Во-вторых, надо работать с n+1 «большими» числами (в данной работе число a называется «большим», если a > ), для чего требуется создавать новый тип чисел и разрабатывать для них все необходимые операции (суммирование, умножение, разность, деление, хранение). К тому же требуется найти наименьшее решения, что является проблематичным. Этот вопрос рассмотрен в следующем пункте.

Второй способ основан на операции «гиперболический поворот», переводящей одну целочисленную точку на графике в следующую. Он основан на следующих формулах:

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

Третий способ разработан преподавателем Самарского медико-технического лицея . Он основан на методе нахождения наименьшего решения, поэтому подробное описание приведено в следующем пункте. Конечный результат имеет следующий вид:

где P — числители подходящей цепной дроби, Pn=x, t -«шаг», k — период, rtk, stk — коэффициенты, получаемые при умножении неполных частных бесконечной цепной дроби, rtk

yt. С помощью этих коэффициентов можно установить «шаг». Например, можно находить только решения, индекс которых делится на 4 или любое другое число. Стоит заметить, что при «ручном» вычислении решений с небольшим индексом формулы (4) совершенно не подходят. Но всё обстоит иначе с компьютерной реализацией. Они требуют столько же операций, переменных, как и формулы (3), но гораздо быстрей работают. В этом алгоритме есть и недостатки: требуется «начальная подготовка», нахождение коэффициентов, но при нахождении «больших» n время «начальной подготовки» будет очень мало по сравнению с временем действия алгоритмов. Стоит заметить, что во многих частных случаях stk-2=1, и тогда скорость будет ещё выше.

3.Способы отыскания наименьшего решения

Индийский (или циклический) метод и английский с появлением теории цепных дробей перестали применяться и «ушли» в историю математики.

Индийский способ (способ 4).

Сначала берут два целых числа, подставляют в правую часть уравнения (1) и находят результат. Выбирают такие числа, чтобы правая часть была близка к единице. Далее получившееся уравнение умножается на уравнение (1). Скобки раскрывают, выделяют полные квадраты и подбирают новые числа, удовлетворяющие неравенству. Далее сокращают обе части равенства на НОД и опять умножают на уравнение (1) и т. д. пока в правой части не получится единица. Недостатки алгоритма огромны: требуется множество проверок, действий, переменных. Но самым проблематичным является первый этап. Оказывается, для приближения можно брать далеко не любые целые числа, поэтому при компьютерной реализации надо перебирать и проверять множество чисел, что занимает большую часть времени. При «ручном» нахождении наименьшего решения этим алгоритмом можно легко ошибиться.

Английский способ (способ 5).

Алгоритм, основанный на цепных дробях, выполняется следующим образом: раскладывается в цепную дробь, которая будет периодична со второго полного частного. Далее находится период k и вычисляется выражение kn, где n — такое наименьшее натуральное число, что kn чётно. Далее находится подходящая дробь с таким индексом, числитель и знаменатель которой и будут наименьшим решением. Доказательство несложно, но опять требует применения множества теорем из теории цепных дробей. Поэтому рассмотрим только этапы решения. Сначала требуется доказать, что все решения уравнения (1) являются числителями и знаменателями подходящих дробей. Вторым этапом находится индекс, при котором модуль правой части уравнения (1) равен 1. Далее находится окончательный индекс. Теперь вернёмся к нахождению «всех» решений и рассмотрим вывод формул (4).

Если в вышеприведённом доказательстве рассматривать все частные, то легко доказать, что все решения уравнения (1) будут числителями и знаменателями подходящих дробей с индексом kn. Теперь рассмотрим процесс образования подходящих дробей. Известны формулы:

где Pn и Qn числитель и знаменатель n-ной подходящей дроби, an — n-ое неполное частное. Если Pn-1 и Qn-1 разложить опять, перегруппировать и продолжать этот процесс, то коэффициенты будут иметь следующий вид:

т. к. через период k все полные частные начинают повторяться, то и коэффициенты будут зависеть только от остатка деления индекса дроби на k. Стоит заметить, что эти коэффициенты универсальны: с их помощи можно ускорить компьютерное нахождение любой подходящей дроби к иррациональности (не только решения уравнения (1)). Но будем рассматривать только те дроби, которые будут решением уравнения Пелля. Т. к. их индекс имеет вид kn, то мы должны находить rtk и stk коэффициенты, где t — «шаг». Подставляя коэффициенты в формулы (4), мы можем найти любое решение.

Теперь обратимся к высказанному утверждению, что если в частном случае данный алгоритм более быстрый, то и при других коэффициентах он тоже будет наиболее быстрым. Отметим, что чем меньше числа, тем быстрее будут производиться с ними операции. Легко заметить, что наименьшее решение и коэффициенты роста получаются по одним и тем же формулам, разница только в начальных членах. Для большинства натуральных чисел коэффициенты роста будут больше наименьшего решения, поэтому в формулах (4) происходит распределение «громоздкости» больших чисел и, как следствие, повышение скорости вычислений, но и повышение расходования памяти. В современных языках программирования возможно использование памяти до 2 ГБ, так что можно «принести в жертву» скорости лишний килобайт.

1. . Уравнение Пелля.

XX городская конференция-фестиваль творчества молодёжи и школьников.