Метод Чакравала

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

Метод чакравала ( санскрит : चक्रवाल विधि ) — циклический алгоритм для решения неопределённых квадратных уравнений , включая уравнение Пелля . Его обычно приписывают Бхаскаре II (ок. 1114 – 1185 гг. н. э.) [ ^{1] [2],} хотя некоторые приписывают его Джаядеве (ок. 950 ~ 1000 гг. н. э.). ^[3] Джаядева указал, что подход Брахмагупты к решению уравнений этого типа можно обобщить, и затем он описал этот общий метод, который позже был уточнён Бхаскарой II в его трактате «Биджаганита» . Он назвал его методом Чакравала: чакра означает «колесо» на санскрите , что указывает на циклическую природу алгоритма. ^[4] C.-O. Селениус считал, что ни одно европейское произведение во времена Бхаскары, ни намного позже, не превосходило его изумительную высоту математической сложности. ^{[1] [4]}

Этот метод также известен как циклический метод и содержит следы математической индукции . ^[5]

История

Чакра на санскрите означает цикл. Согласно популярной легенде, Чакравала обозначает мифическую горную цепь, которая вращается вокруг Земли подобно стене и не ограничена светом и тьмой. ^[6]

Брахмагупта в 628 году н.э. изучал неопределенные квадратные уравнения, включая уравнение Пелля.

${\displaystyle \,x^{2}=Ny^{2}+1,}$

для минимальных целых чисел x и y . Брахмагупта мог решить ее для нескольких N , но не для всех.

Джаядева и Бхаскара предложили первое полное решение уравнения, используя метод чакравалы для поиска решения. ${\displaystyle \,x^{2}=61y^{2}+1,}$

${\displaystyle \,x=1766319049,y=226153980.}$

Этот случай был печально известен своей сложностью и был впервые решен в Европе Браункером в 1657–58 годах в ответ на вызов Ферма , используя непрерывные дроби. Метод для общей задачи был впервые полностью и строго описан Лагранжем в 1766 году. [ ^7] Метод Лагранжа, однако, требует вычисления 21 последовательной подходящей дроби непрерывной дроби для квадратного корня из 61, в то время как метод чакравала намного проще. Селениус, в своей оценке метода чакравала , утверждает

«Метод представляет собой наилучший алгоритм приближения минимальной длины, который благодаря нескольким свойствам минимизации, с минимальными усилиями и избегая больших чисел автоматически выдает наилучшие решения уравнения. Метод чакравала предвосхитил европейские методы более чем на тысячу лет. Но никакие европейские достижения во всей области алгебры, достигнутые в гораздо более позднее время, чем у Бхаскары, и даже почти в наши дни, не сравнятся с изумительной сложностью и изобретательностью чакравала ». ^{[1] [4]}

Герман Ханкель называет метод чакравалы

«лучшее, что было достигнуто в теории чисел до Лагранжа». ^[8]

Метод

Из тождества Брахмагупты мы видим, что для данного N ,

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

Для уравнения это допускает «композицию» ( самаса ) двух троек решений и в новую тройку ${\displaystyle x^{2}-Ny^{2}=k}$ ${\displaystyle (x_{1},y_{1},k_{1})}$ ${\displaystyle (x_{2},y_{2},k_{2})}$

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

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

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

Поскольку знаки внутри квадратов не имеют значения, возможны следующие замены:

${\displaystyle a\leftarrow {\frac {am+Nb}{|k|}},b\leftarrow {\frac {a+bm}{|k|}},k\leftarrow {\frac {m^{2}-N}{k}}}$

Когда положительное целое число m выбрано так, что ( a  +  bm )/ k является целым числом, то и два других числа в тройке являются целыми числами. Среди таких m метод выбирает то, которое минимизирует абсолютное значение m ²  −  N и, следовательно, ( m ²  −  N )/ k . Затем применяются соотношения подстановки для m, равного выбранному значению. Это приводит к новой тройке ( a , b , k ). Процесс повторяется до тех пор, пока не будет найдена тройка с . Этот метод всегда заканчивается решением (доказано Лагранжем в 1768 году). ^[9] При желании мы можем остановиться, когда k равно ±1, ±2 или ±4, поскольку подход Брахмагупты дает решение для этих случаев. ${\displaystyle k=1}$

Метод сочинения Брахмагупты

В 628 году нашей эры Брахмагупта открыл общий способ нахождения и для , когда задано , когда k равно ±1, ±2 или ±4. ^[10] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x^{2}=Ny^{2}+1,}$ ${\displaystyle a^{2}=Nb^{2}+k}$

к = ±1

Используя тождество Брахмагупты , чтобы составить тройку с самим собой: ${\displaystyle (a,b,k)}$

${\displaystyle (a^{2}+Nb^{2})^{2}-N(2ab)^{2}=k^{2}}$ ${\displaystyle \Rightarrow }$ ${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$

Новая тройка может быть выражена как . ${\displaystyle (2a^{2}-k,2ab,k^{2})}$

Подстановка дает решение: ${\displaystyle k=-1}$

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

Для , оригинал уже был решением. Подстановка дает второе: ${\displaystyle k=1}$ ${\displaystyle (a,b)}$ ${\displaystyle k=1}$

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

к = ±2

Снова используя уравнение, ${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$ ${\displaystyle \Rightarrow }$ ${\displaystyle \left({\frac {2a^{2}-k}{k}}\right)^{2}-N\left({\frac {2ab}{k}}\right)^{2}=1}$

Подставляя , ${\displaystyle k=2}$

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

Подставляя , ${\displaystyle k=-2}$

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

к = 4

Подстановка в уравнение создает тройку . ${\displaystyle k=4}$ ${\displaystyle ({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1}$ ${\displaystyle ({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)}$

Что является решением, если четно: ${\displaystyle a}$

${\displaystyle x={\frac {a^{2}-2}{2}},y={\frac {ab}{2}}}$

Если a нечетное, начните с уравнений и . ${\displaystyle ({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=1}$ ${\displaystyle ({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1}$

Приводя к тройкам и . Составление тройки дает ${\displaystyle ({\frac {a}{2}},{\frac {b}{2}},1)}$ ${\displaystyle ({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)}$ ${\displaystyle ({\frac {a}{2}}(a^{2}-3))^{2}-N({\frac {b}{2}}(a^{2}-1))^{2}=1}$

Когда нечетное, ${\displaystyle a}$

${\displaystyle x={\frac {a}{2}}(a^{2}-3),y={\frac {b}{2}}(a^{2}-1)}$

к = -4

Когда , то . Составление с самим собой дает . ${\displaystyle k=-4}$ ${\displaystyle ({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=-1}$ ${\displaystyle ({\frac {a^{2}+Nb^{2}}{4}})^{2}-N({\frac {ab}{2}})^{2}=1}$ ${\displaystyle \Rightarrow }$ ${\displaystyle ({\frac {a^{2}+2}{2}})^{2}-N({\frac {ab}{2}})^{2}=1}$

Снова сочинение себя приносит ${\displaystyle ({\frac {(a^{2}+2)^{2}+Na^{2}b^{2})}{4}})^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1}$ ${\displaystyle \Rightarrow }$ ${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}})^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1}$

Наконец, из предыдущих уравнений составляем тройки и , чтобы получить ${\displaystyle ({\frac {a^{2}+2}{2}},{\frac {ab}{2}},1)}$ ${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}},{\frac {ab(a^{2}+2)}{2}},1)}$

${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+2)+Na^{2}b^{2}(a^{2}+2)}{4}})^{2}-N({\frac {ab(a^{4}+4a^{2}+3)}{2}})^{2}=1}$ ${\displaystyle \Rightarrow }$ ${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+1)}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1}$ ${\displaystyle \Rightarrow }$ ${\displaystyle ({\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2}})^{2}=1}$.

Это дает нам решения

${\displaystyle x={\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}}y={\frac {ab(a^{2}+3)(a^{2}+1)}{2}}}$^[11]

(Примечание: полезно для поиска решения уравнения Пелля , но это не всегда наименьшая целочисленная пара. Например , . Уравнение даст вам , что при подстановке в уравнение Пелля дает , что работает, но то же самое справедливо и для . ${\displaystyle k=-4}$ ${\displaystyle 36^{2}-52*5^{2}=-4}$ ${\displaystyle x=1093436498,y=151632270}$ ${\displaystyle 1195601955878350801-1195601955878350800=1}$ ${\displaystyle x=649,y=90}$ ${\displaystyle N=52}$

Примеры

н= 61

Случай n  = 61 (определение целочисленного решения, удовлетворяющего ), предложенный Ферма много столетий спустя как вызов, был приведен Бхаскарой в качестве примера. ^[9] ${\displaystyle a^{2}-61b^{2}=1}$

Начнем с решения для любого k, найденного любым способом. В этом случае мы можем позволить b быть 1, таким образом, поскольку , у нас есть тройка . Составление ее с дает тройку , которая масштабируется (или лемма Бхаскары используется напрямую), чтобы получить: ${\displaystyle a^{2}-61b^{2}=k}$ ${\displaystyle 8^{2}-61\cdot 1^{2}=3}$ ${\displaystyle (a,b,k)=(8,1,3)}$ ${\displaystyle (m,1,m^{2}-61)}$ ${\displaystyle (8m+61,8+m,3(m^{2}-61))}$

${\displaystyle \left({\frac {8m+61}{3}},{\frac {8+m}{3}},{\frac {m^{2}-61}{3}}\right).}$

Для того, чтобы 3 делилось и было минимальным, мы выбираем , так что у нас есть тройка . Теперь, когда k равно −4, мы можем использовать идею Брахмагупты: ее можно уменьшить до рационального решения , которое складывается само с собой три раза, причем соответственно, когда k становится квадратным и можно применить масштабирование, это дает . Наконец, такую ​​процедуру можно повторять до тех пор, пока не будет найдено решение (требующее 9 дополнительных самосоставлений и 4 дополнительных масштабирования квадратов): . Это минимальное целочисленное решение. ${\displaystyle 8+m}$ ${\displaystyle |m^{2}-61|}$ ${\displaystyle m=7}$ ${\displaystyle (39,5,-4)}$ ${\displaystyle (39/2,5/2,-1)\,}$ ${\displaystyle m={7,11,9}}$ ${\displaystyle (1523/2,195/2,1)\,}$ ${\displaystyle (1766319049,\,226153980,\,1)}$

н= 67

Предположим, что нам нужно найти x и y . [ ^12] ${\displaystyle x^{2}-67y^{2}=1}$

Начнем с решения для любого k, найденного любым способом; в этом случае мы можем позволить b быть 1, таким образом получая . На каждом шаге мы находим m  > 0, такое что k делит a  +  bm , а | m ²  − 67| является минимальным. Затем мы обновляем a , b , и k до и соответственно. ${\displaystyle a^{2}-67b^{2}=k}$ ${\displaystyle 8^{2}-67\cdot 1^{2}=-3}$ ${\displaystyle {\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}}}$ ${\displaystyle {\frac {m^{2}-N}{k}}}$

Первая итерация

У нас есть . Мы хотим положительное целое число m, такое, что k делит a  +  bm , т. е. 3 делит 8 + m, и | m ²  − 67| является минимальным. Первое условие подразумевает, что m имеет вид 3 t + 1 (т. е. 1, 4, 7, 10,… и т. д.), и среди таких m минимальное значение достигается при m = 7. Заменяя ( a ,  b ,  k ) на , мы получаем новые значения . То есть, у нас есть новое решение: ${\displaystyle (a,b,k)=(8,1,-3)}$ ${\displaystyle \left({\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}\right)}$ ${\displaystyle a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(-3)=6}$

${\displaystyle 41^{2}-67\cdot (5)^{2}=6.}$

На этом один раунд циклического алгоритма завершается.

Вторая итерация

Теперь повторим процесс. Имеем . Нам нужно m  > 0 такое, что k делит a  +  bm , т. е. 6 делит 41 + 5 m , и | m ²  − 67| минимально. Первое условие подразумевает, что m имеет вид 6 t  + 5 (т. е. 5, 11, 17,… и т. д.), и среди таких m , | m ²  − 67| минимально для m  = 5. Это приводит к новому решению a  = (41⋅5 + 67⋅5)/6 и т. д.: ${\displaystyle (a,b,k)=(41,5,6)}$

${\displaystyle 90^{2}-67\cdot 11^{2}=-7.}$

Третья итерация

Чтобы 7 делило 90 + 11 m , мы должны иметь m = 2 + 7 t (т. е. 2, 9, 16,… и т. д.), и среди таких m мы выбираем m = 9.

${\displaystyle 221^{2}-67\cdot 27^{2}=-2.}$

Окончательное решение

На этом этапе мы могли бы продолжить циклический метод (и он бы закончился после семи итераций), но поскольку правая часть находится среди ±1, ±2, ±4, мы также можем напрямую использовать наблюдение Брахмагупты. Составляя тройку (221, 27, −2) с самой собой, мы получаем

${\displaystyle \left({\frac {221^{2}+67\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,}$

то есть, у нас есть целочисленное решение:

${\displaystyle 48842^{2}-67\cdot 5967^{2}=1.}$

Это уравнение аппроксимирует с точностью до . ${\displaystyle {\sqrt {67}}}$ ${\displaystyle {\frac {48842}{5967}}}$ ${\displaystyle 2\times 10^{-9}}$

Примечания

1. Hoiberg & Ramchandani - Студенты Britannica India: Bhaskaracharya II, стр. 200
2. Кумар, стр. 23
3. Плофкер, стр. 474
4. Goonatilake, стр. 127 – 128
5. Каджори (1918), стр. 197

   «Процесс рассуждения, называемый «математической индукцией», имел несколько независимых истоков. Его прослеживают до швейцарца Якоба (Джеймса) Бернулли, французов Б. Паскаля и П. Ферма и итальянца Ф. Мавроликус. [...] Читая немного между строк, можно найти следы математической индукции еще раньше, в трудах индусов и греков, как, например, в «циклическом методе» Бхаскары и в доказательстве Евклида того, что число простых чисел бесконечно».

6. Гопал, Мадан (1990). К. С. Гаутам (ред.). Индия сквозь века. Отдел публикаций, Министерство информации и радиовещания, Правительство Индии. С. 79.
7. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. , «Уравнение Пелля», Архив истории математики Мактьютора , Университет Сент-Эндрюс
8. Кей (1919), стр. 337.
9. Джон Стиллвелл (2002), Математика и ее история (2-е изд.), Springer, стр. 72–76, ISBN 978-0-387-95336-6
10. "Уравнение Пелля". История математики . Получено 2021-06-14 .
11. Датта и Сингх (1962). История индийской математики: Книга-источник, части I и II . Asia Publishing House. стр. 157–160. ISBN 8180903907.
12. Пример в этом разделе приведен (с обозначениями для k , для m и т.д.) в: Michael J. Jacobson; Hugh C. Williams (2009), Solving the Pell equation, Springer, стр. 31, ISBN ${\displaystyle Q_{n}}$ ${\displaystyle P_{n}}$ 978-0-387-84922-5

Ссылки

• Флориан Каджори (1918), Происхождение названия «Математическая индукция», The American Mathematical Monthly 25 (5), стр. 197-201.
• Джордж Гевергезе Джозеф, «Хребет павлина: неевропейские корни математики» (1975).
• GR Kaye, «Индийская математика», Isis 2 :2 (1919), стр. 326–356.
• Клас-Олаф Селениус, «Обоснование процесса чакравала Джаядевы и Бхаскары II». Архивировано 30 ноября 2021 г. в Wayback Machine , Historia Mathematica 2 (1975), стр. 167–184.
• Клас-Олаф Селениус, "Kettenbruchtheoretische Erklärung der zyklischen Methode zur Lösung der Bhaskara-Pell-Gleichung", Acta Acad. Або. Математика. Физ. 23 (10) (1963), стр. 1–44.
• Хойберг, Дейл и Рамчандани, Инду (2000). Студенческая Британика Индия . Мумбаи: Популярный Пракашан. ISBN 0-85229-760-2 
• Goonatilake, Susantha (1998). На пути к глобальной науке: добыча цивилизационных знаний . Индиана: Indiana University Press. ISBN 0-253-33388-1 . 
• Кумар, Нарендра (2004). Наука в Древней Индии . Дели: Anmol Publications Pvt Ltd. ISBN 81-261-2056-8 
• Ploker, Kim (2007) «Математика в Индии». Математика Египта, Месопотамии, Китая, Индии и ислама: Справочник Нью-Джерси: Princeton University Press. ISBN 0-691-11485-4 
• Эдвардс, Гарольд (1977). Великая теорема Ферма . Нью-Йорк: Springer . ISBN 0-387-90230-9.

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

• Введение в чакравалу