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

 Метод «чакравала» — это итерационный алгоритм решенияквадратных уравнений, включая Уравнение Пелля. Обычно метод приписываютБхаскаре II, (1114 – 1185), хотя некоторые указывают автором (950\textasciitilde 1000 н.э.). Джаядева указал на то, что подходБрахмагупты для решения уравнений такого типа можно обобщить и описалэтот метод обобщения. Метод позднее доработал Бхаскара II в своёмтрактате (Алгебра). Он назвал этот метод «чакравала» —чакра на санскрите означает «колесо», что указывает нациклическую натуру алгоритма. Селениус придерживается мнения, что никтоиз европейцев не достигал во времена Бхаскара и в более поздние временастоль изумительной высоты математической сложности.
 Метод известен также как циклический метод и содержит следыматематической индукции.

История


Чакра на санскрите означает цикл. В буддийской космографиивселенная состоит из бесчисленных сфер (чакравал), каждая изкоторых имеет свою землю, своё солнце, свою луну, небеса и ады и делитсяна три области, или авачара
 Брахмагупта в 628 н.э. изучал неопределённые квадратные уравнения,включая уравнение Пелля
x2=Ny2+1,

 для минимальных целых x и y. Брахмагупта смог решитьуравнение для некоторых N, но не для всех.
 Джаядева (9-й век) и Бхаскара (12-й век) предложили полное решениеуравнения, используя метод чакравала, чтобы найти дляx2=61y2+1 решение
x=1766319049,y=226153980.

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

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

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

Метод


 Из тождества Брахмагупты мы видим, что для заданного N,
(x12Ny12)(x22Ny22)=(x1x2+Ny1y2)2N(x1y2+x2y1)2

 Для уравнения x2Ny2=k это позволяет «скомбинировать» две тройкирешения (x1,y1,k1) и (x2,y2,k2) в новую тройку
(x1x2+Ny1y2,x1y2+x2y1,k1k2).

 Главная идея метода состоит в том, что любая тройка (a,b,k)(удовлетворяющая уравнению a2Nb2=k) может быть скомбинирована стривиальной тройкой (m,1,m2N) (для любого m), что дастновую тройку (am+Nb,a+bm,k(m2N)). Если принять, что мы начинаемс тройки, для которой НОД(a, b)=1, последнюю тройку можнопонизить на k (это ):
a2Nb2=k(am+Nbk)2N(a+bmk)2=m2Nk

 Поскольку знаки внутри скобок значения не имеют, возможны следующиеподстановки:
 $$a\leftarrow\frac{am+Nb}{|
 Когда положительное число ''m'' выбрано так, что (''a'' + ''bm'')/''k'' является целым, то целыми будут и другие два числа в тройке. Среди возможных значений ''m'' метод выбирает то, которое минимизирует абсолютное значение ''m''2 − ''N'', а потому значение (''m''2 − ''N'')/''k''. Затем осуществляем подстановку с выбранным значением ''m'', что приводит к тройке (''a'', ''b'', ''k''). Процесс повторяется, пока тройка с k=1$$не будет найдена. Этот метод всегда заканчивается решением (доказаноЛагранжем в 1768). Мы можем завершить процесс, когда k равно ±1,±2 или ±4, где даёт решение подход Брахмагупты.

Примеры


 === n = 61 === Случай n = 61 (поиск решения уравненияa261b2=1), которое было вызовом Ферма много веков позже,Бхаскара дал как пример.
 Мы начинаем с решения a261b2=k для любого k, найденногопроизвольным способом. Мы можем взять b равным 1 и, поскольку826112=3, мы получим тройку (a,b,k)=(8,1,3).Скомбинируем её с тройкой (m,1,m261), что даст(8m+61,8+m,3(m261)), а после понижения (по )

(8m+613,8+m3,m2613).
 Чтобы 3 делило 8+m, а |m261| было минимальным, выбираем m=7, такчто получим тройку (39,5,4). Теперь имеем k = −4 и мы можемвоспользоваться идеей Брахмагупты — тройка может быть сведена крациональному решению (39/2,5/2,1), которое затем комбинируется ссобой три раза с m=7,11,9 соответственно, пока k не станет квадратоми мы не сможем произвести понижение. Это даёт (1523/2,195/2,1).Такая процедура может быть повторена, пока не получим решение (требуется9 дополнительных комбинаций и 4 дополнительных квадратичных понижений)(1766319049,226153980,1). Это минимальное целое решение.
 === n = 67 === Пусть нужно решить уравнение x267y2=1
 Начинаем с решения уравнения a267b2=k для k, найденноголюбым способом. Мы можем взять b равным 1, что даёт826712=3. На каждой итерации ми находимm \textgreater 0, такое, что k делитa + bm и\textbarm\textsuperscript2 − 67\textbar минимально. Затеммы обновляем a, b и k на $\frac{am+Nb}{|
 ;Первая итерацияМы имеем (a,b,k) = (8,1,-3)$. Нам нужно положительное целоеm, такое что k делит a + bm, то есть 3 делит8 + m. Нам нужно также, чтобы при этом значение\textbarm\textsuperscript2 − 67\textbar было минимальным.Из первого условия следует, что m имеет вид 3t + 1 (тоесть m = 1, 4, 7, 10,\ldots и т.д.), а среди таких значенийm, минимальное значение получается при m = 7. Заменяя(abk) на $\left(\frac{am+Nb}{|: 41^2 - 67\cdot(5)^2 = 6.$


Вторая итерация 
 Повторяем процесс. Мы имеем (a,b,k)=(41,5,6). Нам нужноm \textgreater 0, такое, что k делитa + bm, то есть 6 делит 41 + 5m. Нам при этомнужно, чтобы \textbarm\textsuperscript2 − 67\textbar быломинимальным. Из первого условия следует, что m имеет вид6t + 5 (то есть m = 5, 11, 17,\ldots и т.д.), а средитаких чисел m минимум\textbarm\textsuperscript2 − 67\textbar достигается наm = 5. Это приводит нас к новому решениюa = (41⋅5 + 67⋅5)/6, и т.д.:
90267112=7.



Третья итерация 
 Для того, чтобы 7 делило 90 + 11m, m должно иметь видm = 2 + 7t (то есть, 2, 9, 16,\ldots и т.д.). Средитаких m выбираем m = 9.
221267272=2.



Конечное решение 
 Мы можем продолжать итерации (и закончим после семи итераций), нопоскольку правая часть находится среди чисел ±1, ±2, ±4, мы можемиспользовать напрямую наблюдение Брахмагупты. Скомбинируем тройку (221,27, −2) с собой, мы получим
(2212+672722)267(22127)2=1,

 То есть мы имеем целое решение:
4884226759672=1.

 Это решение является приближением 67 в виде488425967, в котором ошибка находится в пределах 109.