Chakravala method

From Wikipedia, the free encyclopedia

The chakravala method is a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation. This method was developed in India and its roots can be traced back to the 5th century, summarized by Aryabhata, which was later developed further by Brahmagupta, Jayadeva, and Bhaskara.

The problems Brahmagupta, in 628, used the chakravala method to solve indeterminate quadratic equations, including the Pell equation

$\,61x^2 + 1 = y^2$ ,

for minimum integers $x$ and $y$ .

Jayadeva (9th century) and Bhaskara (12th century) offered the first complete solution to this equation using the chakravala method to find

$\,x = 226 153 980$ and $\,y = 1 766 319 049$ .

This was not solved in Europe until the time of Lagrange in 1767. Lagrange's method however, requires the calculation of 21 successive convergents of the continued fraction for the square root of 61, while the chakravala method is much simpler. Selenius, on his assessment of the chakravala method, states

"The method represents a best approximation algorithm of minimal length that, owing to several minimization properties, with minimal effort and avoiding large numbers automatically produces the best solutions to the equation. The chakravala method anticipated the European methods by more than a thousand years. But no European performances in the whole field of algebra at a time much later than Bhaskara's, nay nearly equal up to our times, equalled the marvellous complexity and ingenuity of chakravala."^{[citation needed]}

Hermann Hankel, while relating the method to number theory, states that the chakravala method is

"the finest thing achieved in the theory of numbers before Lagrange (18th century)."^{[citation needed]}

[edit] Example

Suppose we are to solve $67 x 2 + 1 = y 2$ for $x$ and $y$ . The first step is to find any solution to $67 x 2 + k = y 2$ by some other means; in this case, we can let $x$ equal 1, thus producing $67\cdot 1^2 + (-3) = 8^2$ .

Now, we apply Bhaskara's lemma, which states that

if $\, Nx^2 + k = y^2$ , then

$\,N\left(\frac{mx + y}{k}\right)^2 + \frac{m^2 - N}{k} = \left(\frac{my + Nx}{k}\right)^2$

By Bhaskara's lemma, we now have

$67\left(\frac{1m + 8}{-3}\right)^2 + \frac{m^2 - 67}{-3} = \left(\frac{8m + 67\cdot 1}{-3}\right)^2$

Now, make $(1 m + 8) / - 3$ an integer, by letting $m = 3 t + 1$ , and take $t$ so that the absolute value of $m 2 - 67$ is minimized. The result is $t = 2$ , $m = 7$ , $m 2 - 67 = - 18$ .

Substituting the computed value $m = 7$ , the equation now reduces to:

$67\left(\frac{7 + 8}{-3}\right)^2 + \frac{49 - 67}{-3} = \left(\frac{56 + 67\cdot 1}{-3}\right)^2$ , or

$67\cdot (-5)^2 + 6 = (-41)^2$

We can ignore the signs of $x$ and $y$ , since they're being squared, and treat them as if they were 5 and 41, respectively.

At this point, one round of the cyclic algorithm is complete. We now repeat the process again, applying Bhaskara's lemma:

$67\left(\frac{5m + 41}{6}\right)^2 + \frac{m^2 - 67}{6} = \left(\frac{41m + 67\cdot 5}{6}\right)^2$

Now, make $(5 m + 41) / 6$ an integer, by letting $m = 6 t + 5$ , and take $t$ so that the absolute value of $m 2 - 67$ is minimized. The result is $t = 0$ , $m = 5$ , $m 2 - 67 = - 42$ .

$67\cdot 11^2 + (-7) = 90^2$

Third iteration:

$67\left(\frac{11m + 90}{-7}\right)^2 + \frac{m^2 - 67}{-7} = \left(\frac{90m + 67\cdot 11}{-7}\right)^2$

Make $(11 m + 90) / - 7$ an integer, by letting $m = - 7 t + 2$ , and take $t$ so that the absolute value of $m 2 - 67$ is minimized. The result is $t = - 1$ , $m = 9$ , $m 2 - 67 = 14$ .

$67\cdot 27^2 + (-2) = 221^2$

Fourth iteration:

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

Make $(27 m + 221) / - 2$ an integer, by letting $m = - 2 t + 1$ , and take $t$ so that the absolute value of $m 2 - 67$ is minimized. The result is $t = - 4$ , $m = 9$ , $m 2 - 67 = 14$ .

$67\cdot(-232)^2 + (-7) = (-1899)^2$

Fifth iteration:

$67\left(\frac{232m + 1899}{-7}\right)^2 + \frac{m^2 - 67}{-7} = \left(\frac{1899m + 67\cdot 232}{-7}\right)^2$

Make $(232 m + 1899) / - 7$ an integer, by letting $m = - 7 t + 5$ , and take $t$ so that the absolute value of $m 2 - 67$ is minimized. The result is $t = 0$ , $m = 5$ , $m 2 - 67 = - 42$ .

$67\cdot 437^2 + 6 = (-3577)^2$

...Eventually this must get down to the solution, which is

$67\cdot 5967^2 + 1 = 48842^2$ .

Cleanup and proof needed.

[edit] References

C. O. Selenius, "Rationale of the chakravala process of Jayadeva and Bhaskara II", Historia Mathematica, 2 (1975), 167-184.
C. O. Selenius, Kettenbruch theoretische Erklarung der zyklischen Methode zur Losung der Bhaskara-Pell-Gleichung, Acta Acad. Abo. Math. Phys. 23 (10) (1963).
George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics (1975).