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

Тип диофантова уравнения

Уравнение Пелля для n  = 2 и шесть его целочисленных решений

Уравнение Пелля , также называемое уравнением Пелля–Ферма , — это любое диофантово уравнение вида , где n — заданное положительное целое число , не являющееся квадратом , а целочисленные решения ищутся для x и y . В декартовых координатах уравнение представляется гиперболой ; решения возникают везде, где кривая проходит через точку, координаты x и y которой являются целыми числами, например, тривиальное решение с x  = 1 и y  = 0. Жозеф Луи Лагранж доказал, что, пока n не является полным квадратом , уравнение Пелля имеет бесконечно много различных целочисленных решений. Эти решения можно использовать для точной аппроксимации квадратного корня из  n рациональными числами вида  x / y . ${\displaystyle x^{2}-ny^{2}=1,}$

Это уравнение впервые было широко изучено в Индии, начиная с Брахмагупты , ^[1] который нашел целочисленное решение в своем труде Brāhmasphuṭasiddhānta около 628 года. ^[2] Бхаскара II в 12 веке и Нараяна Пандит в 14 веке оба нашли общие решения уравнения Пелла и других квадратных неопределенных уравнений. Бхаскаре II обычно приписывают разработку метода чакравалы , основанного на работах Джаядевы и Брахмагупты. Решения конкретных примеров уравнения Пелла, таких как числа Пелла, возникающие из уравнения с n  = 2, были известны гораздо дольше, со времен Пифагора в Греции и аналогичной даты в Индии. Уильям Брункер был первым европейцем, решившим уравнение Пелла. Название уравнения Пелла возникло из-за того, что Леонард Эйлер ошибочно приписал решение уравнения Брункером Джону Пеллу . ^{[3] [4] [примечание 1]} ${\displaystyle 92x^{2}+1=y^{2}}$

История

Еще в 400 году до нашей эры в Индии и Греции математики изучали числа, возникающие из случая n  = 2 уравнения Пелля,

${\displaystyle x^{2}-2y^{2}=1,}$

и из тесно связанного уравнения

${\displaystyle x^{2}-2y^{2}=-1}$

из-за связи этих уравнений с квадратным корнем из 2. [ ^5] Действительно, если x и y — положительные целые числа, удовлетворяющие этому уравнению, то x / y является приближением √ 2. Числа x и y, появляющиеся в этих приближениях, называемые числами сторон и диаметров , были известны пифагорейцам , и Прокл заметил, что в противоположном направлении эти числа подчиняются одному из этих двух уравнений. ^[5] Аналогично, Баудхаяна обнаружил, что x = 17, y = 12 и x = 577, y = 408 являются двумя решениями уравнения Пелля, и что 17/12 и 577/408 являются очень близкими приближениями к квадратному корню из 2. ^[6]

Позже Архимед аппроксимировал квадратный корень из 3 рациональным числом 1351/780. Хотя он не объяснил свои методы, это приближение может быть получено тем же способом, как решение уравнения Пелля. ^[5] Аналогично, задача Архимеда о скоте — древняя текстовая задача о нахождении количества скота, принадлежащего богу солнца Гелиосу — может быть решена, переформулировав ее как уравнение Пелля. В рукописи, содержащей задачу, говорится, что она была придумана Архимедом и записана в письме к Эратосфену , ^[7] и приписывание ее Архимеду сегодня общепринято. ^{[8] [9]}

Около 250 г. н.э. Диофант рассмотрел уравнение

${\displaystyle a^{2}x^{2}+c=y^{2},}$

где a и c — фиксированные числа, а x и y — переменные, для которых нужно решить. Это уравнение по форме отличается от уравнения Пелля, но эквивалентно ему. Диофант решил уравнение для ( a ,  c ), равного (1, 1), (1, −1), (1, 12) и (3, 9). Аль-Караджи , персидский математик 10-го века, работал над проблемами, похожими на проблемы Диофанта. ^[10]

В индийской математике Брахмагупта открыл, что

${\displaystyle (x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2},}$

форма того, что сейчас известно как тождество Брахмагупты . Используя это, он смог «составить» тройки и которые были решениями , чтобы сгенерировать новые тройки ${\displaystyle (x_{1},y_{1},k_{1})}$ ${\displaystyle (x_{2},y_{2},k_{2})}$ ${\displaystyle x^{2}-Ny^{2}=k}$

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2},x_{1}y_{2}+x_{2}y_{1},k_{1}k_{2})}$и ${\displaystyle (x_{1}x_{2}-Ny_{1}y_{2},x_{1}y_{2}-x_{2}y_{1},k_{1}k_{2}).}$

Это не только дало возможность генерировать бесконечно много решений, начиная с одного решения, но также, разделив такую ​​композицию на , можно было часто получить целочисленные или «почти целочисленные» решения. Например, для , Брахмагупта составил тройку (10, 1, 8) (так как ) с собой, чтобы получить новую тройку (192, 20, 64). Деление всего на 64 («8» для и ) дало тройку (24, 5/2, 1), которая при составлении с собой дала искомое целочисленное решение (1151, 120, 1). Брахмагупта решил много уравнений Пелла этим методом, доказав, что он дает решения, начиная с целочисленного решения для k = ±1, ±2 или ±4. ^[11] ${\displaystyle x^{2}-Ny^{2}=1}$ ${\displaystyle k_{1}k_{2}}$ ${\displaystyle N=92}$ ${\displaystyle 10^{2}-92(1^{2})=8}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x^{2}-Ny^{2}=k}$

Первый общий метод решения уравнения Пелля (для всех N ) был дан Бхаскарой II в 1150 году, расширяя методы Брахмагупты. Называемый методом чакравала (циклическим) , он начинается с выбора двух относительно простых целых чисел и , затем составляет тройку (то есть такую, которая удовлетворяет ) с тривиальной тройкой, чтобы получить тройку , которую можно уменьшить до ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle (a,b,k)}$ ${\displaystyle a^{2}-Nb^{2}=k}$ ${\displaystyle (m,1,m^{2}-N)}$ ${\displaystyle {\big (}am+Nb,a+bm,k(m^{2}-N){\big )}}$

${\displaystyle \left({\frac {am+Nb}{k}},{\frac {a+bm}{k}},{\frac {m^{2}-N}{k}}\right).}$

Когда выбирается так, что является целым числом, то и два других числа в тройке являются целыми числами. Среди таких , метод выбирает тот, который минимизирует и повторяет процесс. Этот метод всегда заканчивается решением. Бхаскара использовал его, чтобы дать решение x  =  ${\displaystyle m}$ ${\displaystyle {\frac {a+bm}{k}}}$ ${\displaystyle m}$ ${\displaystyle {\frac {m^{2}-N}{k}}}$1 766 319 049 , у  = 226 153 980 для случая N  = 61. ^[11]

Несколько европейских математиков заново открыли, как решить уравнение Пелля в 17 веке. Пьер де Ферма нашел, как решить уравнение , и в письме 1657 года бросил вызов английским математикам. ^[12] В письме Кенелму Дигби Бернар Френикль де Бесси сказал, что Ферма нашел наименьшее решение для N до 150, и бросил вызов Джону Уоллису , чтобы тот решил случаи N = 151 или 313. И Уоллис, и Уильям Брункер дали решения этих задач, хотя Уоллис в письме предполагает, что решение было дано Брункером. ^[13]

Связь Джона Пелла с уравнением заключается в том, что он пересмотрел перевод Томаса Бранкера ^[14] книги Иоганна Рана 1659 года Teutsche Algebra ^{[примечание 2]} на английский язык, с обсуждением решения уравнения Брункера. Леонард Эйлер ошибочно считал, что это решение принадлежит Пеллю, в результате чего он назвал уравнение в честь Пелла. ^[4]

Общая теория уравнения Пелля, основанная на цепных дробях и алгебраических манипуляциях с числами вида, была разработана Лагранжем в 1766–1769 гг. ^[15] В частности, Лагранж дал доказательство того, что алгоритм Брункера–Уоллиса всегда завершается. ${\displaystyle P+Q{\sqrt {a}},}$

Решения

Фундаментальное решение с помощью цепных дробей

Пусть обозначает последовательность подходящих дробей к правильной непрерывной дроби для . Эта последовательность уникальна. Тогда пара положительных целых чисел, решающих уравнение Пелля и минимизирующих x, удовлетворяет x ₁ = h _i и y ₁ = k _i для некоторого i . Эта пара называется фундаментальным решением . Последовательность целых чисел в правильной непрерывной дроби всегда в конечном счете периодична. Ее можно записать в виде , где — периодическая часть, повторяющаяся бесконечно. Более того, кортеж является палиндромным . Он читается одинаково как слева направо, так и справа налево. ^[16] Тогда фундаментальное решение равно ${\displaystyle h_{i}/k_{i}}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle [a_{0};a_{1},a_{2},\ldots ]}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle \left[\lfloor {\sqrt {n}}\rfloor ;{\overline {a_{1},a_{2},\ldots ,a_{p-1},2\lfloor {\sqrt {n}}\rfloor }}\right]}$ ${\displaystyle a_{1},a_{2},\ldots ,a_{p-1},2\lfloor {\sqrt {n}}\rfloor }$ ${\displaystyle (a_{1},a_{2},\ldots ,a_{p-1})}$

${\displaystyle (x_{1},y_{1})={\begin{cases}(h_{p-1},k_{p-1}),&{\text{ for }}p{\text{ even}}\\(h_{2p-1},k_{2p-1}),&{\text{ for }}p{\text{ odd}}\end{cases}}}$

Время нахождения фундаментального решения с использованием метода непрерывных дробей с помощью алгоритма Шёнхаге–Штрассена для быстрого целочисленного умножения находится в пределах логарифмического множителя размера решения, количества цифр в паре . Однако это не алгоритм полиномиального времени , поскольку количество цифр в решении может быть таким большим, как √ n , что намного больше полинома от количества цифр во входном значении n . ^[17] ${\displaystyle (x_{1},y_{1})}$

Дополнительные решения из фундаментального решения

Как только фундаментальное решение найдено, все оставшиеся решения могут быть вычислены алгебраически из ^[17]

${\displaystyle x_{k}+y_{k}{\sqrt {n}}=(x_{1}+y_{1}{\sqrt {n}})^{k},}$

Расширяя правую сторону, приравнивая коэффициенты по обеим сторонам и приравнивая остальные члены по обеим сторонам. Это дает рекуррентные соотношения ${\displaystyle {\sqrt {n}}}$

${\displaystyle x_{k+1}=x_{1}x_{k}+ny_{1}y_{k},}$

${\displaystyle y_{k+1}=x_{1}y_{k}+y_{1}x_{k}.}$

Краткая презентация и более быстрые алгоритмы

Хотя запись фундаментального решения ( x ₁ , y ₁ ) в виде пары двоичных чисел может потребовать большого количества бит, во многих случаях его можно представить более компактно в виде

${\displaystyle x_{1}+y_{1}{\sqrt {n}}=\prod _{i=1}^{t}(a_{i}+b_{i}{\sqrt {n}})^{c_{i}}}$

используя гораздо меньшие целые числа a _i , b _i и c _i .

Например, задача Архимеда о скоте эквивалентна уравнению Пелля , фундаментальное решение которого имеет ${\displaystyle x^{2}-410\,286\,423\,278\,424y^{2}=1}$206 545 цифр, если выписать явно. Однако решение также равно

${\displaystyle x_{1}+y_{1}{\sqrt {n}}=u^{2329},}$

где

${\displaystyle u=x'_{1}+y'_{1}{\sqrt {4\,729\,494}}=(300\,426\,607\,914\,281\,713\,365{\sqrt {609}}+84\,129\,507\,677\,858\,393\,258{\sqrt {7766}})^{2}}$

и и имеют только 45 и 41 десятичных знаков соответственно. ^[17] ${\displaystyle x'_{1}}$ ${\displaystyle y'_{1}}$

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

${\displaystyle \exp O({\sqrt {\log N\log \log N}}),}$

где N  = log  n — размер входных данных, аналогично квадратичному решету. ^[17]

Квантовые алгоритмы

Холлгрен показал, что квантовый компьютер может найти представление произведения, как описано выше, для решения уравнения Пелля за полиномиальное время. ^[18] Алгоритм Холлгрена, который можно интерпретировать как алгоритм для нахождения группы единиц действительного квадратичного числового поля , был распространен на более общие поля Шмидтом и Фёльмером. ^[19]

Пример

В качестве примера рассмотрим случай уравнения Пелля для n = 7, то есть:

${\displaystyle x^{2}-7y^{2}=1.}$

Цепная дробь имеет вид . Поскольку период имеет длину , которая является четным числом, то конвергенция, дающая фундаментальное решение, получается путем усечения цепной дроби непосредственно перед концом первого вхождения периода: . ${\displaystyle {\sqrt {7}}}$ ${\displaystyle [2;{\overline {1,1,1,4}}]}$ ${\displaystyle 4}$ ${\displaystyle [2;1,1,1]={\frac {8}{3}}}$

Последовательность подходящих дробей для квадратного корня из семи:

Применение формулы рекуррентности к этому решению порождает бесконечную последовательность решений

(1, 0); (8, 3); (127, 48); (2024, 765); (32257, 12192); (514088, 194307); (8193151, 3096720); (130576328, 49353213); ... (последовательность A001081 ( x ) и A001080 ( y ) в OEIS )

Для уравнения Пелля

${\displaystyle x^{2}-13y^{2}=1.}$

непрерывная дробь имеет период нечетной длины. Для этого фундаментальное решение получается путем усечения непрерывной дроби прямо перед вторым появлением периода . Таким образом, фундаментальное решение равно . ${\displaystyle {\sqrt {13}}=[3;{\overline {1,1,1,1,6}}]}$ ${\displaystyle [3;1,1,1,1,6,1,1,1,1]={\frac {649}{180}}}$ ${\displaystyle (x_{1},y_{1})=(649,180)}$

Наименьшее решение может быть очень большим. Например, наименьшее решение для — это ( ${\displaystyle x^{2}-313y^{2}=1}$32 188 120 829 134 849 , 1 819 380 158 564 160 ), и это уравнение, которое Френикл бросил Уоллису вызов решить. ^[20] Значения n, такие, что наименьшее решение больше наименьшего решения для любого меньшего значения n, равны ${\displaystyle x^{2}-ny^{2}=1}$

1, 2, 5, 10, 13, 29, 46, 53, 61, 109, 181, 277, 397, 409, 421, 541, 661, 1021, 1069, 1381, 1549, 1621, 2389, 3061, 3469, 4621, 4789, 4909, 5581, 6301, 6829, 8269, 8941, 9949, ... (последовательность A033316 в OEIS ).

(Для этих записей см. OEIS : A033315 для x и OEIS : A033319 для y .)

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

Ниже приведен список фундаментальных решений для с n ≤ 128. Когда n — целый квадрат, нет решения, кроме тривиального решения (1, 0). Значения x — это последовательность A002350, а значения y — это последовательность A002349 в OEIS . ${\displaystyle x^{2}-ny^{2}=1}$

Связи

Уравнение Пелла связано с несколькими другими важными разделами математики.

Алгебраическая теория чисел

Уравнение Пелля тесно связано с теорией алгебраических чисел , поскольку формула

${\displaystyle x^{2}-ny^{2}=(x+y{\sqrt {n}})(x-y{\sqrt {n}})}$

является нормой для кольца и для тесно связанного квадратичного поля . Таким образом, пара целых чисел решает уравнение Пелля тогда и только тогда, когда является единицей с нормой 1 в . ^[21] Теорема Дирихле о единицах , гласящая, что все единицы могут быть выражены как степени одной фундаментальной единицы (и умножения на знак), является алгебраическим переформулированием того факта, что все решения уравнения Пелля могут быть получены из фундаментального решения. ^[22] Фундаментальную единицу в общем случае можно найти, решив уравнение типа Пелля, но она не всегда напрямую соответствует фундаментальному решению самого уравнения Пелля, поскольку фундаментальная единица может иметь норму −1, а не 1, и ее коэффициенты могут быть полуцелыми числами, а не целыми числами. ${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$ ${\displaystyle \mathbb {Q} ({\sqrt {n}})}$ ${\displaystyle (x,y)}$ ${\displaystyle x+y{\sqrt {n}}}$ ${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$ ${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$

полиномы Чебышева

Демейер упоминает связь между уравнением Пелля и многочленами Чебышева : если и являются многочленами Чебышева первого и второго рода соответственно, то эти многочлены удовлетворяют форме уравнения Пелля в любом кольце многочленов , причем : ^[23] ${\displaystyle T_{i}(x)}$ ${\displaystyle U_{i}(x)}$ ${\displaystyle R[x]}$ ${\displaystyle n=x^{2}-1}$

${\displaystyle T_{i}^{2}-(x^{2}-1)U_{i-1}^{2}=1.}$

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

${\displaystyle T_{i}+U_{i-1}{\sqrt {x^{2}-1}}=(x+{\sqrt {x^{2}-1}})^{i}.}$

Далее можно заметить, что если являются решениями любого целочисленного уравнения Пелля, то и . ^[24] ${\displaystyle (x_{i},y_{i})}$ ${\displaystyle x_{i}=T_{i}(x_{1})}$ ${\displaystyle y_{i}=y_{1}U_{i-1}(x_{1})}$

Непрерывные дроби

Общую разработку решений уравнения Пелля в терминах непрерывных дробей можно представить, поскольку решения x и y приближены к квадратному корню из n и, таким образом, являются частным случаем приближений непрерывных дробей для квадратичных иррациональностей . ^[16] ${\displaystyle x^{2}-ny^{2}=1}$ ${\displaystyle {\sqrt {n}}}$

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

${\displaystyle {\begin{pmatrix}p&q\\nq&p\end{pmatrix}}}$

является матрицей единичного определителя . Произведения таких матриц принимают точно такую ​​же форму, и, таким образом, все такие произведения дают решения уравнения Пелля. Это можно понять отчасти как результат того факта, что последовательные подходящие дроби непрерывной дроби обладают одним и тем же свойством: если p _{k −1} / q _{k −1} и p _k / q _k являются двумя последовательными подходящими дробями непрерывной дроби, то матрица

${\displaystyle {\begin{pmatrix}p_{k-1}&p_{k}\\q_{k-1}&q_{k}\end{pmatrix}}}$

имеет определитель (−1) ^k .

Гладкие числа

Теорема Штёрмера применяет уравнения Пелля для нахождения пар последовательных гладких чисел , положительных целых чисел, простые множители которых меньше заданного значения. ^{[25] [26]} В рамках этой теории Штёрмер также исследовал отношения делимости среди решений уравнения Пелля; в частности, он показал, что каждое решение, отличное от фундаментального решения, имеет простой множитель , который не делит  n . ^[25]

Отрицательное уравнение Пелля

Отрицательное уравнение Пелля имеет вид

${\displaystyle x^{2}-ny^{2}=-1}$

и также широко изучалось. Его можно решить тем же методом непрерывных дробей, и оно имеет решения тогда и только тогда, когда период непрерывной дроби имеет нечетную длину. Однако неизвестно, какие корни имеют нечетную длину периода, и, следовательно, неизвестно, когда отрицательное уравнение Пелля разрешимо. Необходимое (но не достаточное) условие разрешимости состоит в том, что n не делится на 4 или на простое число вида 4 k  + 3. ^{[примечание 3]} Так, например, x ²  − 3 y ²  = −1 никогда не разрешимо, но x ²  − 5 y ²  = −1 может быть разрешимым. ^[27]

Первые несколько чисел n , для которых x ²  −  ny ²  = −1 разрешимы, это

1, 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, ... (последовательность A031396 в OEIS ).

Пусть . Доля свободных от квадратов n, делящихся на k простых чисел вида 4 m  + 1, для которых разрешимо отрицательное уравнение Пелля, составляет по крайней мере α . ^[28] Когда число простых делителей не фиксировано, пропорция определяется как 1 -  α. ^{[29] [30]} ${\displaystyle \alpha =\Pi _{j{\text{ is odd}}}(1-2^{j})}$

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

${\displaystyle (x^{2}-ny^{2})^{2}=(-1)^{2}}$

подразумевает

${\displaystyle (x^{2}+ny^{2})^{2}-n(2xy)^{2}=1.}$

Как указано выше, если отрицательное уравнение Пелля разрешимо, решение может быть найдено с помощью метода непрерывных дробей, как в положительном уравнении Пелля. Однако рекурсивное соотношение работает немного иначе. Поскольку , следующее решение определяется в терминах всякий раз, когда есть совпадение, то есть, когда нечетно. Результирующее рекурсивное соотношение равно (по модулю знака минус, который несуществен из-за квадратичной природы уравнения) ${\displaystyle (x+{\sqrt {n}}y)(x-{\sqrt {n}}y)=-1}$ ${\displaystyle i(x_{k}+{\sqrt {n}}y_{k})=(i(x+{\sqrt {n}}y))^{k}}$ ${\displaystyle k}$

${\displaystyle x_{k}=x_{k-2}x_{1}^{2}+nx_{k-2}y_{1}^{2}+2ny_{k-2}y_{1}x_{1},}$

${\displaystyle y_{k}=y_{k-2}x_{1}^{2}+ny_{k-2}y_{1}^{2}+2x_{k-2}y_{1}x_{1},}$

что дает бесконечную башню решений отрицательного уравнения Пелля.

Обобщенное уравнение Пелля

Уравнение

${\displaystyle x^{2}-dy^{2}=N}$

называется обобщенным ^{[31] [32]} (или общим ^[16] ) уравнением Пелля . Уравнение является соответствующей резольвентой Пелля . ^[16] Рекурсивный алгоритм был дан Лагранжем в 1768 году для решения уравнения, сводя задачу к случаю . ^{[33] [34]} Такие решения могут быть получены с помощью метода непрерывных дробей, как описано выше. ${\displaystyle u^{2}-dv^{2}=1}$ ${\displaystyle |N|<{\sqrt {d}}}$

Если является решением и является решением , то такое, что является решением , принцип, называемый мультипликативным принципом . ^[16] Решение называется кратным Пелля решения . ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle x^{2}-dy^{2}=N,}$ ${\displaystyle (u_{n},v_{n})}$ ${\displaystyle u^{2}-dv^{2}=1,}$ ${\displaystyle (x_{n},y_{n})}$ ${\displaystyle x_{n}+y_{n}{\sqrt {d}}={\big (}x_{0}+y_{0}{\sqrt {d}}{\big )}{\big (}u_{n}+v_{n}{\sqrt {d}}{\big )}}$ ${\displaystyle x^{2}-dy^{2}=N}$ ${\displaystyle (x_{n},y_{n})}$ ${\displaystyle (x_{0},y_{0})}$

Существует конечное множество решений для , такое, что каждое решение является кратным Пелля решения из этого множества. В частности, если является фундаментальным решением для , то каждое решение уравнения является кратным Пелля решения с и , где . ^[35] ${\displaystyle x^{2}-dy^{2}=N}$ ${\displaystyle (u,v)}$ ${\displaystyle u^{2}-dv^{2}=1}$ ${\displaystyle (x,y)}$ ${\displaystyle |x|\leq {\sqrt {|N|}}\left({\sqrt {|U|}}+1\right)/2}$ ${\displaystyle |y|\leq {\sqrt {|N|}}\left({\sqrt {|U|}}+1\right)/{\big (}2{\sqrt {d}}{\big )}}$ ${\displaystyle U=u+v{\sqrt {d}}}$

Если x и y — положительные целые решения уравнения Пелля с , то является сходящейся дробью к . ^[35] ${\displaystyle |N|<{\sqrt {d}}}$ ${\displaystyle x/y}$ ${\displaystyle {\sqrt {d}}}$

Решения обобщенного уравнения Пелля используются для решения некоторых диофантовых уравнений и единиц некоторых колец , ^{[36] [37]} и они возникают при изучении SIC-POVM в квантовой теории информации . ^[38]

Уравнение

${\displaystyle x^{2}-dy^{2}=4}$

похож на резольвенту в том, что если минимальное решение для может быть найдено, то все решения уравнения могут быть получены аналогичным образом в случае . Для некоторых , решения для могут быть получены из тех, у которых , в том, что если то каждое третье решение для имеет четное, генерируя решение для . ^[16] ${\displaystyle x^{2}-dy^{2}=1}$ ${\displaystyle x^{2}-dy^{2}=4}$ ${\displaystyle N=1}$ ${\displaystyle d}$ ${\displaystyle x^{2}-dy^{2}=1}$ ${\displaystyle x^{2}-dy^{2}=4}$ ${\displaystyle d\equiv 5{\pmod {8}},}$ ${\displaystyle x^{2}-dy^{2}=4}$ ${\displaystyle x,y}$ ${\displaystyle x^{2}-dy^{2}=1}$

Примечания

1. В работе Эйлера «Vollständige Anleitung zur Algebra» (стр. 227 и далее) он представляет решение уравнения Пелла, взятое из «Commercium epistolicum» Джона Уоллиса , в частности, из Письма 17 ( Epistola XVII ) и Письма 19 ( Epistola XIX ):
   • Уоллис, Джон, изд. (1658). Commercium epistolicum, de Quaestionibus quibusdam Mathematicis nuper Habitum [ Переписка о некоторых недавно предпринятых математических исследованиях ] (на английском, латинском и французском языках). Оксфорд, Англия: А. Личфилд.Буквы на латыни. Буква 17 появляется на стр. 56–72. Буква 19 появляется на стр. 81–91.
   • Французские переводы писем Уоллиса: Ферма, Пьер де (1896). Таннери, Пол; Генри, Чарльз (ред.). Oeuvres de Fermat (на французском и латыни). Том. 3. Париж, Франция: Готье-Виллар и др.Письмо 17 появляется на стр. 457–480. Письмо 19 появляется на стр. 490–503.
   Письма Уоллиса, показывающие решение уравнения Пелла, также появляются во втором томе «Opera mathematica» Уоллиса (1693), который включает статьи Джона Пелла:
   • Уоллис, Джон (1693). Opera mathematica: de Algebra Tractatus; Historicus & Practicus [ Математические работы: Трактат по алгебре; исторический и в современном виде ] (на латыни, английском и французском языках). Том 2. Оксфорд, Англия.Письмо 17 находится на стр. 789–798; письмо 19 находится на стр. 802–806. См. также статьи Пелла, где Уоллис упоминает (стр. 235, 236, 244), что методы Пелла применимы к решению диофантовых уравнений:

   • Де Алгебра Д. Йоханнис Пелли; & speciatim de Issueatis Perfecte Determinatis (Об алгебре доктора Джона Пелла и особенно о не полностью определенной проблеме), стр. 234–236.
   • Methodi Pellianae Specimen (Пример метода Пелла), стр. 238–244.
   • Образец aliud Methodi Pellianae (Еще один пример метода Пелла), стр. 244–246.

   Смотрите также:
   • Уитфорд, Эдвард Эверетт (1912) «Уравнение Пелля», докторская диссертация, Колумбийский университет (Нью-Йорк, США), стр. 52.
   • Хит, Томас Л. (1910). Диофант Александрийский: исследование истории греческой алгебры. Кембридж, Англия: Cambridge University Press. стр. 286.
2. Teutsch — устаревшая форма Deutsch , что означает «немецкий». Бесплатная электронная книга: Немецкая алгебра в Google Книгах.
3. Это связано с тем, что уравнение Пелля подразумевает, что −1 является квадратичным вычетом по модулю n .

Ссылки

1. O'Connor, JJ; Robertson, EF (февраль 2002 г.). «Уравнение Пелля». Школа математики и статистики, Университет Сент-Эндрюс, Шотландия . Получено 13 июля 2020 г.
2. Данэм, Уильям. «Теория чисел – Теория чисел на Востоке». Encyclopedia Britannica . Получено 4 января 2020 г.
3. Еще в 1732–1733 годах Эйлер считал, что Джон Пелл разработал метод решения уравнения Пелла, хотя Эйлер знал, что Уоллис разработал метод его решения (хотя на самом деле большую часть работы проделал Уильям Брункер):
   • Эйлер, Леонард (1732–1733). «О решении диофантовых задач целыми числами». Commentarii Academiae Scientiarum Imperialis Petropolitanae (Воспоминания об Императорской Академии наук в Санкт-Петербурге) (на латыни). 6 : 175–188. Из стр. 182: «At si a huiusmodi fuerit numerus, qui nullo modo ad illas Formulas potest reduci, uniqueis ad invenienda p et q adhibenda est Methodus, qua olim iam usi sunt Pellius et Fermatius ». (Но если такое a — число, которое никак не может быть сведено к этим формулам, то применяется особый метод нахождения p и q , который уже некоторое время используют Пелл и Ферма .) Из p. 183: «§. 19. Methodus haec extat descripta in operibus Wallisii , et hanc ob rem eam hic fusius non-expono». (§ 19. Этот метод существует, описанный в работах Уоллиса, и по этой причине я не привожу его здесь более подробно.)
   • Письмо IX. Эйлер а Гольдбах, от 10 августа 1750 г. в: Fuss, PH, ed. (1843). Correspondance Mathématique et Physique de Quelques Célèbres Géomètres du XVIIIeme Siècle ... [ Математическое и физическое соответствие некоторых известных геометров 18 века ... ] (на французском, латинском и немецком языках). Санкт-Петербург, Россия. п. 37. Со страницы 37: «Pro hujusmodi quaestionibussolvendis excogitavit D. Pell Anglus uniquemmethodum in Wallisiioperibus expositam». (Для решения таких вопросов англичанин доктор Пелл изобрел своеобразный метод, [который] показан в работах Уоллиса.)
   • Эйлер, Леонард (1771). Vollständige Anleitung zur Algebra, II. Тейл [ Полное введение в алгебру, часть 2 ] (на немецком языке). Kayserlichen Akademie der Wissenschaften (Императорская Академия наук): Санкт-Петербург, Россия. п. 227.Из стр. 227: «§98. Hierzu Hat vormals ein gelehrter Engländer, Namens Pell, eine ganz sinnreiche Methode erfunden, welche wir hier erklären wollen». (§ 98. По этому поводу ученый англичанин по имени Пелл ранее нашел весьма остроумный метод, который мы здесь объясним.)
   • Перевод на английский: Эйлер, Леонард (1810). Элементы алгебры... Т. 2 (2-е изд.). Лондон, Англия: Дж. Джонсон. С. 78.
   • Хит, Томас Л. (1910). Диофант Александрийский: исследование истории греческой алгебры. Кембридж, Англия: Cambridge University Press. стр. 286.См. особенно сноску 4.
4. Tattersall, James (2000). Элементарная теория чисел в девяти главах (PDF) . Кембридж. стр. 274. doi :10.1017/CBO9780511756344. ISBN 9780521850148. S2CID  118948378. Архивировано из оригинала (PDF) 15 февраля 2020 г.
5. Knorr, Wilbur R. (1976), «Архимед и измерение окружности: новая интерпретация», Архив истории точных наук , 15 (2): 115–140, doi :10.1007/bf00348496, MR  0497462, S2CID  120954547.
6. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Baudhayana», Архив истории математики Мактьютора , Университет Сент-Эндрюс
7. Варди, И. (1998). «Задача Архимеда о коровах». American Mathematical Monthly . 105 (4). Математическая ассоциация Америки: 305–319. CiteSeerX 10.1.1.33.4288 . doi :10.2307/2589706. JSTOR  2589706. 
8. Фрейзер, Питер М. (1972). Птолемеевская Александрия . Oxford University Press.
9. Вайль, Андре (1972). Теория чисел, подход через историю . Биркхойзер.
10. Изади, Фарзали (2015). «Конгруэнтные числа с помощью уравнения Пелля и его аналогичного аналога» (PDF) . Заметки по теории чисел и дискретной математике . 21 : 70–78.
11. Джон Стиллвелл (2002), Математика и ее история (2-е изд.), Springer, стр. 72–76, ISBN 978-0-387-95336-6.
12. В феврале 1657 года Пьер де Ферма написал два письма об уравнении Пелля. Одно письмо (на французском) было адресовано Бернару Френиклю де Бесси, а другое (на латыни) — Кенелму Дигби, до которого оно дошло через Томаса Уайта, а затем через Уильяма Браункера.
    • Ферма, Пьер де (1894). Таннери, Пол; Генри, Чарльз (ред.). Oeuvres de Fermat (на французском и латыни). Том. 2-й том. Париж, Франция: Готье-Виллар и др. стр. 333–335.Письмо к Френиклю опубликовано на стр. 333–334; письмо к Дигби — на стр. 334–335.
    Письмо на латыни к Дигби переведено на французский язык следующим образом:
    • Ферма, Пьер де (1896). Таннери, Пол; Генри, Чарльз (ред.). Oeuvres de Fermat (на французском и латыни). Том. 3-й том. Париж, Франция: Готье-Виллар и др. стр. 312–313.
    Оба письма переведены (частично) на английский язык в:
    • Struik, Dirk Jan, ред. (1986). A Source Book in Mathematics, 1200–1800. Принстон, Нью-Джерси, США: Princeton University Press. стр. 29–30. ISBN 9781400858002.
13. В январе 1658 года, в конце Epistola XIX (письмо 19), Уоллис восторженно поздравлял Брункера с победой в битве умов с Ферма относительно решения уравнения Пелля. Со стр. 807 из (Уоллис, 1693 г.): «Et quidem cum Vir Nobilissimus, utut hac sibi suisque tam uniqueia putaverit, & altis impervia, ( quippe non omnis Fert omnia Tellus ) ut ab Anglis haud speraverit Solutionem; Signieur ; erit cur & ipse tibi gratuletur. Me quod attinet, humillimas est quod rependam gratias, quod in Victoriae tuae partem advocare dignatus es, ...» (И действительно, благороднейший сэр [т. е. виконт Браункер], он [т. е. Ферма] мог бы подумать, что [имеет] все себе такое эзотерический [предмет, т. е. уравнение Пелла] с его непроницаемыми глубинами ( ибо не всякая земля несет все вещи [т. е. не каждая нация может преуспеть во всем]), так что он вряд ли мог ожидать решения от англичан; тем не менее, он признается , что он, однако, будет взволнован, если его разубедит этот изобретательный и ученый Лорд [т. е. Брункер]; именно по этой причине он [т. е. Ферма] сам поздравил бы вас. Что касается меня, я смиренно благодарен вам за то, что вы соизволили призвать меня принять участие в вашей Победе, ...) Примечание: дата в конце письма Уоллиса - "20 января 1657 г."; Однако эта дата соответствовала старому юлианскому календарю, от которого Британия окончательно отказалась в 1752 году : большая часть остальной Европы считала бы эту дату 31 января 1658 года. См. Даты по старому и новому стилю#Транспозиция дат исторических событий и возможные конфликты дат .
14. Ран, Иоганн Генрих (1668) [1659], Бранкер, Томас; Пелл (ред.), Введение в алгебру.
15. «Решение проблемы арифметики», в книге Джозефа Альфреда Серре (редактор), Œuvres de Lagrange, vol. 1, стр. 671–731, 1867.
16. Андрееску, Титу; Андрика, Дорин (2015). Квадратные диофантовые уравнения . Нью-Йорк : Спрингер. ISBN 978-0-387-35156-8.
17. Lenstra, HW Jr. (2002), «Решение уравнения Пелля» (PDF) , Notices of the American Mathematical Society , 49 (2): 182–192, MR  1875156.
18. Холлгрен, Шон (2007), «Квантовые алгоритмы полиномиального времени для уравнения Пелля и задачи главного идеала», Журнал ACM , 54 (1): 1–19, doi :10.1145/1206035.1206039, S2CID  948064.
19. Шмидт, А.; Фёльмер, У. (2005), «Квантовый алгоритм полиномиального времени для вычисления единичной группы числового поля» (PDF) , Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений – STOC '05 , Нью-Йорк: ACM, Симпозиум по теории вычислений, стр. 475–480, CiteSeerX 10.1.1.420.6344 , doi :10.1145/1060590.1060661, ISBN  1581139608, S2CID  6654142, заархивировано из оригинала (PDF) 26 октября 2017 г. , извлечено 25 октября 2017 г..
20. «Главные диковинки!: 313».
21. Кларк, Пит. "Уравнение Пелла" (PDF) . Университет Джорджии .
22. Конрад, Кит. "Единичная теорема Дирихле" (PDF) . Получено 14 июля 2020 г.
23. Демейер, Йерун (2007), Диофантовы множества над кольцами многочленов и десятая проблема Гильберта для функциональных полей (PDF) , докторская диссертация, Гентский университет , стр. 70, архивировано из оригинала (PDF) 2 июля 2007 г. , извлечено 27 февраля 2009 г..
24. Барбо, Эдвард Дж. (2003), "3. Квадратичные сурды", Уравнение Пелла , Сборник задач по математике, Springer-Verlag, ISBN 0-387-95529-1, г-н  1949691.
25. Стермер, Карл (1897). «Quelques theorèmes sur l'équation de Pell et leurs application». Скрифтер Виденскабс-сельскабет (Христиания), Мат.-Натурв. кл. (на французском языке). Я (2). ${\displaystyle x^{2}-Dy^{2}=\pm 1}$
26. Лемер, Д. Х. (1964). «О проблеме Штёрмера». Illinois Journal of Mathematics . 8 (1): 57–79. doi : 10.1215/ijm/1256067456 . MR  0158849.
27. Ван, Цзяци; Цай, Лиде (декабрь 2013 г.). «Разрешимость отрицательного уравнения Пелля» (PDF) . Колледж Цинхуа : 5–6.
28. Кремона, Джон Э.; Одони, РВК (1989), «Некоторые результаты плотности для отрицательных уравнений Пелля; применение теории графов», Журнал Лондонского математического общества , Вторая серия, 39 (1): 16–28, doi :10.1112/jlms/s2-39.1.16, ISSN  0024-6107.
29. «Древние уравнения предлагают новый взгляд на числовые группы». Журнал Quanta . 10 августа 2022 г. Получено 18 августа 2022 г.
30. Койманс, Питер; Пагано, Карло (31 января 2022 г.). «О гипотезе Стивенхагена». arXiv : 2201.13424 [math.NT].
31. Peker, Bilge (2021). Current Studies in Basic Sciences, Engineering and Technology 2021 (PDF) . ISRES Publishing. стр. 136 . Получено 25 февраля 2024 г. .
32. Таманг, Бал Бахадур (август 2022 г.). Разрешимость обобщенного уравнения Пелля и его применение в реальной жизни (PDF) (Отчет). Университет Трибхувана . Получено 25 февраля 2024 г.
33. Лагранж, Жозеф-Луи (1867–1892). Творения Лагранжа. Т. 2 / publiées par les soins de MJ-A. Серре [и Ж. Дарбу]; [предварительное уведомление о жизни и жизни Ж.-Л. Лагранж, пар М. Деламбр] (на французском языке).
34. Мэтьюз, Кит. "Диофантово уравнение x2 − Dy2 = N, D > 0" (PDF) . Архивировано (PDF) из оригинала 18 марта 2015 г. . Получено 20 июля 2020 г. .
35. Conrad, Keith. "PELL'S EQUATION, II" (PDF) . Получено 14 октября 2021 г. .
36. Бернштейн, Леон (1 октября 1975 г.). «Усеченные единицы в бесконечном числе алгебраических числовых полей степени n ≧4». Mathematische Annalen . 213 (3): 275–279. doi :10.1007/BF01350876. ISSN  1432-1807. S2CID  121165073.
37. Бернштейн, Леон (1 марта 1974 г.). «О диофантовом уравнении x(x + d)(x + 2d) + y(y + d)(y + 2d) = z(z + d)(z + 2d)». Канадский математический бюллетень . 17 (1): 27–34. doi : 10.4153/CMB-1974-005-5 . ISSN  0008-4395. S2CID  125002637.
38. Appleby, Marcus; Flammia, Steven; McConnell, Gary; Yard, Jon (август 2017 г.). «SICs and Algebraic Number Theory». Foundations of Physics . 47 (8): 1042–1059. arXiv : 1701.05200 . Bibcode : 2017FoPh...47.1042A. doi : 10.1007/s10701-017-0090-7. ISSN  0015-9018. S2CID  119334103.

Дальнейшее чтение

• Эдвардс, Гарольд М. (1996) [1977]. Великая теорема Ферма: Генетическое введение в алгебраическую теорию чисел . Graduate Texts in Mathematics . Vol. 50. Springer-Verlag . ISBN 0-387-90230-9. МР  0616635.
• Pinch, RGE (1988). «Одновременные уравнения Пеллиана». Math. Proc. Cambridge Philos. Soc . 103 (1): 35–46. Bibcode :1988MPCPS.103...35P. doi :10.1017/S0305004100064598. S2CID  123098216.
• Уитфорд, Эдвард Эверетт (1912). Уравнение Пелля (кандидатская диссертация) . Колумбийский университет.
• Williams, HC (2002). "Решение уравнения Пелля". В Bennett, MA; Berndt, BC ; Boston, N .; Diamond, HG; Hildebrand, AJ; Philipp, W. (ред.). Обзоры по теории чисел: доклады с конференции тысячелетия по теории чисел . Natick, MA: AK Peters . стр. 325–363. ISBN 1-56881-162-4. Збл  1043.11027.

Внешние ссылки

• Вайсштейн, Эрик В. "Уравнение Пелла". MathWorld .
• О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Уравнение Пелля», Архив истории математики Мактьютора , Университет Сент-Эндрюс
• Решатель уравнения Пелля ( n не имеет верхнего предела)
• Решатель уравнения Пелля ( n < 10 ¹⁰ , также может возвращать решение x ²  −  ny ² = ±1, ±2, ±3 и ±4)