You can mark you interesting snippets of text that will be available through a unique link in your browser.


Chakravala method

Chakravala method

The chakravala method (Hindi: चक्रवाल विधि) 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]

Contents

History

Brahmagupta in 628 CE studied indeterminate quadratic equations, including Pell's equation

\,x^2 = Ny^2 + 1,

for minimum integers x and y. Brahmagupta could solve it for several N, but not all.

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)

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

This case was first solved in Europe by Brouncker in 1657–58 in response to a challenge by Fermat, and a method first completely described by Lagrange in 1766.[6] 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."[7]

The method

The chakravala method for solving Pell's equation is based on the observation by Brahmagupta (see Brahmagupta's identity) that

(x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2) = (x_1x_2 + Ny_1y_2)^2 - N(x_1y_2 + x_2y_1)^2.

This defines a "composition" (samāsa) of two triples (x1,y1,k1) and (x2,y2,k2) that are solutions of x2 − Ny2 = k, to generate the new triple

(x_1x_2 + Ny_1y_2 \,,\, x_1y_2 + x_2y_1 \,,\, k_1k_2).


In the general method, the main idea is that any triple (a,b,k) (that is, one which satisfies a2 − Nb2 = k) can be composed with the trivial triple (m,1,m2 − N) to get the new triple (am + Nb,a + bm,k(m2 − N)) for any m. Assuming we started with a triple for which gcd(a,b) = 1, this can be scaled down by k (this is Bhaskara's lemma):

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

or, since the signs inside the squares do not matter,

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

When a positive integer m is chosen so that (a + bm)/k is an integer, so are the other two numbers in the triple. Among such m, the method chooses one that minimizes the absolute value of m2 − N and hence that of (m2 − N)/k. Then, (a, b, k) is replaced with the new triple given by the above equation, and the process is repeated. This method always terminates with a solution (proved by Lagrange in 1768).[8] Optionally, we can stop when k is ±1, ±2, or ±4, as Brahmagupta's approach gives a solution for those cases.

Examples

n = 61

The n = 61 case (determining an integer solution satisfying a2 − 61b2 = 1), issued as a challenge by Fermat many centuries later, was given by Bhaskara as an example.[8]

We start with a solution a2 − 61b2 = k for any k found by any means. In this case we can let b be 1, thus, since 8^2 - 61\cdot1^2 = 3, we have the triple (a,b,k) = (8,1,3). Composing it with (m,1,m2 − 61) gives the triple (8m + 61,8 + m,3(m2 − 61)), which is scaled down (or Bhaskara's lemma is directly used) to get:

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

For 3 to divide 8 + m and m2 − 61 to be minimal, we choose m=7, so that we have the triple (39,5, − 4). Now that k is −4, we can use Brahmagupta's idea: it can be scaled down to the rational solution (39/2, 5/2, -1)\,, which composed with itself twice gives (1523/2, 195/2, 1)\, and then (29718, 3805, -1)\,. Finally, this is composed with itself, giving the solution (1766319049,\, 226153980,\, 1). This is the minimal integer solution.

n = 67

Suppose we are to solve x2 − 67y2 = 1 for x and y.[9]

We start with a solution a2 − 67b2 = k for any k found by any means; in this case we can let b be 1, thus producing 8^2 - 67\cdot1^2 = -3. At each step, we find an m > 0 such that k divides a + bm, and \vert m^2-N\vert is minimal. We then update a, b, and k to \frac{am+Nb}{|k|}, \frac{a+bm}{|k|}, \text{ and }\frac{m^2-N}{k} respectively.

First iteration

We have a = 8, b = 1, k = −3. We want a positive integer m such that k divides a+mb, i.e. 3 divides 8+m, and \vert m^2-67 \vert is minimal. The first condition implies that m is of the form 3t+1 (i.e. 1, 4, 7, 10,… etc.), and among such m, the minimal value is attained for m=7. Replacing (a, b, k) with (am+Nb)/|k|, (a + bm)/|k|, and (m2 − N)/k, we get the new values a = (8\cdot7+67\cdot1)/3 = 41, b = (8 + 1\cdot7)/3 = 5, k = (7^2-67)/(-3) = 6. That is, we have the new solution:

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

At this point, one round of the cyclic algorithm is complete.

Second iteration

We now repeat the process. We have a = 41, b = 5, k = 6. We want an m > 0 such that k divides a + mb, i.e. 6 divides 41 + 5m, and |m2 − 67| is minimal. The first condition implies that m is of the form 6t + 5 (i.e. 5, 11, 17,…), and among such m, |m2 − 67| is minimal for m = 5. This leads to the new solution a = (41⋅5 + 67⋅5)/6, etc.:

90^2 - 67 \cdot 11^2 = -7 \,
Third iteration

For 7 to divide 90+11m, we must have m = 2 + 7t (2, 9, 16,…) and among such m, we pick m=9.

221^2 - 67\cdot 27^2 = -2 \,
Final solution

At this point, we could continue with the cyclic method (and it would end, after seven iterations), but since the right-hand side is among ±1, ±2, ±4, we can also use Brahmagupta's observation directly. Composing the triple (221, 27, −2) with itself, we get

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

that is, we have the integer solution:

48842^2 - 67 \cdot 5967^2 = 1

This equation approximates \sqrt{67} (as 48842/5967) to within a margin of about 2 \times 10^{-9}.

Notes

  1. ^ a b c Hoiberg & Ramchandani – Students' Britannica India: Bhaskaracharya II, page 200
  2. ^ Kumar, page 23
  3. ^ Plofker, page 474
  4. ^ a b c Goonatilake, page 127 – 128
  5. ^ Cajori (1918), p. 197

    "The process of reasoning called "Mathematical Induction" has had several independent origins. It has been traced back to the Swiss Jakob (James) Bernoulli, the Frenchman B. Pascal and P. Fermat, and the Italian F. Maurolycus. [...] By reading a little between the lines one can find traces of mathematical induction still earlier, in the writings of the Hindus and the Greeks, as, for instance, in the "cyclic method" of Bhaskara, and in Euclid's proof that the number of primes is infinite."

  6. ^ O'Connor, John J.; Robertson, Edmund F., "Pell's equation", MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/HistTopics/Pell.html .
  7. ^ Kaye (1919), p. 337.
  8. ^ a b John Stillwell (2002), Mathematics and its history (2 ed.), Springer, pp. 72–76, ISBN 9780387953366, http://books.google.com/books?id=WNjRrqTm62QC&pg=PA72 
  9. ^ The example in this section is given (with notation Qn for k, Pn for m, etc.) in: Michael J. Jacobson; Hugh C. Williams (2009), Solving the Pell equation, Springer, p. 31, ISBN 9780387849225, http://books.google.com/books?id=2INzqrEUGzAC&pg=PA31 

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
  • Edwards, Harold (1977). Fermat's Last Theorem. New York: Springer. ISBN 0-387-90230-9. 

External links

v · Number-theoretic algorithms
Primality tests
AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial division
Sieving algorithms
Integer factorization algorithms
Multiplication algorithms
Discrete logarithm algorithms
Baby-step giant-step · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieve
GCD algorithms
Modular square root algorithms
Cipolla · Pocklington's · Tonelli–Shanks
Other algorithms
Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).

Wikimedia Foundation. 2010.

  
Share  

Look at other dictionaries:

  • Bhāskara II — Bhaskara (1114 ndash; 1185), also known as Bhaskara II and Bhaskara Achārya ( Bhaskara the teacher ), was an Indian mathematician and astronomer. He was born near Bijjada Bida (in present day Bijapur district, Karnataka state, South India) into… …   Wikipedia

  • Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th …   Wikipedia

  • Cornacchia's algorithm — In computational number theory, Cornacchia s algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1]. Contents 1 The algorithm …   Wikipedia

  • A. A. Krishnaswami Ayyangar — (1892 ndash;1953) was a mathematician from India. He also wrote many papers on Vedic mathematics.A. A. Krishnaswami Ayyangar (AAK), was born on 1 December, 1892. He got his M.A. in Mathematics at the age of 18 and subsequently started teaching… …   Wikipedia

  • Proof of Bhaskara's lemma — Bhaskara s Lemma is an identity used as a lemma during the chakravala method. It states that::, Nx^2 + k = y^2implies ,Nleft(frac{mx + y}{k} ight)^2 + frac{m^2 N}{k} = left(frac{my + Nx}{k} ight)^2.ProofWith simple manipulations on both sides of… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Indian mathematics — mdash;which here is the mathematics that emerged in South Asia from ancient times until the end of the 18th century mdash;had its beginnings in the Bronze Age Indus Valley civilization (2600 1900 BCE) and the Iron Age Vedic culture (1500 500 BCE) …   Wikipedia

  • Pell's equation — is any Diophantine equation of the form:x^2 ny^2=1,where n is a nonsquare integer and x and y are integers. Trivially, x = 1 and y = 0 always solve this equation. Lagrange proved that for any natural number n that is not a perfect square there… …   Wikipedia

  • Jayadeva (mathematician) — Jayadeva (जयदेव) was a ninth century Indian mathematician, who knew the cyclic method (chakravala method) that was called by Hermann Hankel the finest thing achieved in the theory of numbers before Lagrange (18th century). Fact|date=February 2007 …   Wikipedia

  • Brahmagupta — (audio|Brahmagupta pronounced.ogg|listen) (598–668) was an Indian mathematician and astronomer. Life and work Brahmagupta was born in 598 CE in Bhinmal city in the state of Rajasthan of northwest India. He likely lived most of his life in… …   Wikipedia