Метод чакравалы

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

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

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

• 1 История
• 2 Метод
• 3 Примеры
  • 3,1 n = 61
  • 3,2 n = 67
• 4 Примечания
• 5 Ссылки
• 6 Внешние ссылки

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

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

$x\; 2\; =\; N\; y\; 2\; +\; 1,\; \{\backslash \; displaystyle\; \backslash ,\; x\; ^\; \{2\}\; =\; Ny\; ^\; \{2\}\; +1,\}$

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

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

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

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

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

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

" лучшим достижением теории чисел до Лагранжа ".

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

$(x\; 1\; x\; 2\; +\; N\; y\; 1\; y\; 2)\; 2\; -\; N\; (x\; 1\; y\; 2\; +\; x\; 2\; y\; 1)\; 2\; =\; (x\; 1\; 2\; -\; N\; y\; 1\; 2)\; (Икс\; 2\; 2\; -\; N\; Y\; 2\; 2)\; \{\backslash \; 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\})\}$

Для уравнения $x\; 2\; -\; N\; y\; 2\; =\; k\; \{\backslash \; displaystyle\; x\; ^\; \{2\}\; -Ny\; ^\; \{2\}\; =\; k\}$, это позволяет «составить» (самасу) двух троек решений $(x\; 1,\; y\; 1,\; k\; 1)\; \{\backslash \; displaystyle\; (x\_\; \{1\},\; y\_\; \{1\},\; k\_\; \{1)\; \})\}$и $(x\; 2,\; y\; 2,\; k\; 2)\; \{\backslash \; displaystyle\; (x\_\; \{2\},\; y\_\; \{2\},\; k\_\; \{2\})\}$в новая тройка

$(x\; 1\; x\; 2\; +\; N\; y\; 1\; y\; 2,\; x\; 1\; y\; 2\; +\; x\; 2\; y\; 1,\; k\; 1\; k\; 2).\; \{\backslash \; Displaystyle\; (x\_\; \{1\}\; x\_\; \{2\}\; +\; Ny\_\; \{1\}\; y\_\; \{2\}\; \backslash ,,\; \backslash ,\; x\_\; \{1\}\; y\_\; \{2\}\; +\; x\_\; \{2\}\; y\_\; \{1\}\; \backslash ,,\; \backslash ,\; k\_\; \{\; 1\}\; k\_\; \{2\}).\}$

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

$a\; 2\; -\; N\; b\; 2\; =\; k\; \Rightarrow \; (am\; +\; N\; bk)\; 2\; -\; N\; (a\; +\; bmk)\; 2\; =\; m\; 2\; -\; N\; k\; \{\backslash \; displaystyle\; a\; ^\; \{2\}\; -Nb\; ^\; \{2\}\; =\; k\; \backslash \; Rightarrow\; \backslash \; left\; (\{\backslash \; frac\; \{am\; +\; Nb\}\; \{k\}\}\; \backslash \; right)\; ^\; \{2\}\; -N\; \backslash \; left\; (\{\backslash \; frac\; \{a\; +\; bm\}\; \{k\}\}\; \backslash \; справа)\; ^\; \{2\}\; =\; \{\backslash \; frac\; \{m\; ^\; \{2\}\; -N\}\; \{k\}\}\}$

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

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

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

n = 61

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

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

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

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

n = 67

Предположим, мы должны решить $x\; 2\; -\; 67\; y\; 2\; =\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{2\}\; -67y\; ^\; \{2\}\; =\; 1\}$для x и y.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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