Chakravala method

Contents 1 Example 1.1 First iteration 1.2 Subsequent iterations 2 Notes 3 References 4 External links

The chakravala method is a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation. It is commonly attributed to Bhāskara II, (c. 1114 – 1185 CE)^[1][2] although some attribute it to Jayadeva (c. 950 ~ 1000 CE).^[3] Jayadeva pointed out that Brahmagupta's approach to solving equations of this type could be generalized, and he then described this general method, which was later refined by Bhāskara II in his Bijaganita treatise. He called it the Chakravala method: chakra meaning "wheel" in Sanskrit, a reference to the cyclic nature of the algorithm.^[4] E. O. Selenius held that no European performances at the time of Bhāskara, nor much later, exceeded its marvellous height of mathematical complexity.^[1][4]

This method is also known as the cyclic method and contains traces of mathematical induction.^[5]

The problems which were solved by Brahmagupta in 628 using the chakravala method were indeterminate quadratic equations, including Pell's equation

for minimum integers x and y. Brahmagupta however could not solve for all N.

Jayadeva (9th century) and Bhaskara (12th century) offered the first complete solution to the equation using the chakravala method to find (for the notorious N=61 case)

and

This case was not solved in Europe until the time of Lagrange in 1767.^{[citation needed]} 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, in 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."^[1][4]

Hermann Hankel calls the chakravala method

"the finest thing achieved in the theory of numbers before Lagrange."^[6]

Example

Suppose we are to solve 67x² + 1 = y² for x and y. The first step is to find any solution to 67x² + k = y² by some other means; in this case, we can let x equal 1, thus producing .

First iteration

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

if , then

By Bhaskara's lemma, we now have

Now, make (1m + 8) / − 3 an integer, by letting m = − 3t + 1, and take t so that the absolute value of m² − 67 is minimized, and m > 0. The result is t = − 2, m = 7, m² − 67 = − 18. (We can't use t = 3 because then (1m + 8) / − 3 is zero, which results in the useless equation with x = 0.)

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

, or

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.

Subsequent iterations

We now repeat the process again, applying Bhaskara's lemma:

Now, make (5m + 41) / 6 an integer, by letting m = 6t + 5, and take t so that the absolute value of m² − 67 is minimized. The result is t = 0, m = 5, m² − 67 = − 42. (We can't use t = − 2, m = − 7 because we require m to be positive.)

Third iteration:

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

Fourth iteration:

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

Fifth iteration:

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

Sixth iteration:

Make (437m + 3577) / 6 an integer, by letting m = 6t + 1, and take t so that the absolute value of m² − 67 is minimized. The result is t = 1, m = 7, m² − 67 = − 18.

Seventh iteration:

Make (1106m + 9053) / − 3 an integer, by letting m = − 3t + 2, and take t so that the absolute value of m² − 67 is minimized. The result is t = − 2, m = 8, m² − 67 = − 3.

This yields the solution:

This equation approximates to within a margin of about .

Notes

References

• Florian Cajori (1918), Origin of the Name "Mathematical Induction", The American Mathematical Monthly 25 (5), p. 197-201.
• George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics (1975).
• G. R. Kaye, "Indian Mathematics", Isis 2:2 (1919), p. 326–356.
• C. O. Selenius, "Rationale of the chakravala process of Jayadeva and Bhaskara II", Historia Mathematica 2 (1975), pp. 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).
• Hoiberg, Dale & Ramchandani, Indu (2000). Students' Britannica India. Mumbai: Popular Prakashan. ISBN 0852297602
• Goonatilake, Susantha (1998). Toward a Global Science: Mining Civilizational Knowledge. Indiana: Indiana University Press. ISBN 0253333881.
• Kumar, Narendra (2004). Science in Ancient India. Delhi: Anmol Publications Pvt Ltd. ISBN 8126120568
• Ploker, Kim (2007) "Mathematics in India". The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook New Jersey: Princeton University Press. ISBN 0691114854

External links

• Introduction to chakravala

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie–PSW · ECPP · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · p − 1 · p + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's Multiplication algorithms Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithm Discrete logarithm algorithms Baby-step giant-step · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieve GCD algorithms Binary GCD · Euclidean · Extended Euclidean Other algorithms Aryabhata · Chakravala · integer relation algorithm · integer square root · Modular exponentiation · Schoof's · Shanks–Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.