The ''chakravala'' method ( sa, चक्रवाल विधि) is a cyclic

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...

to solve

indeterminate Indeterminate may refer to: In mathematics * Indeterminate (variable), a symbol that is treated as a variable * Indeterminate system, a system of simultaneous equations that has more than one solution * Indeterminate equation, an equation that ha ...

quadratic equations, including

Pell's equation Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinate ...

. It is commonly attributed to Bhāskara II, (c. 1114 – 1185 CE)Hoiberg & Ramchandani – Students' Britannica India: Bhaskaracharya II, page 200Kumar, page 23 although some attribute it to Jayadeva (c. 950 ~ 1000 CE).Plofker, page 474 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 Sanskrit (; attributively , ; nominalization, nominally , , ) is a classical language belonging to the Indo-Aryan languages, Indo-Aryan branch of the Indo-European languages. It arose in South Asia after its predecessor languages had Trans-cul ...

, a reference to the cyclic nature of the algorithm.Goonatilake, page 127 – 128 C.-O. Selenius held that no European performances at the time of Bhāskara, nor much later, exceeded its marvellous height of mathematical complexity. This method is also known as the cyclic method and contains traces of

mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ... all hold. Informal metaphors help ...

History

''Chakra'' in Sanskrit means cycle. As per popular legend, Chakravala indicates a mythical range of mountains which orbits around the earth like a wall and not limited by light and darkness. Brahmagupta in 628 CE studied indeterminate quadratic equations, including

\,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

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

the solution :

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

This case was notorious for its difficulty, and was first solved in

Europe Europe is a large peninsula conventionally considered a continent in its own right because of its great physical size and the weight of its history and traditions. Europe is also considered a subcontinent of Eurasia and it is located enti ...

by Brouncker in 1657–58 in response to a challenge by Fermat, using continued fractions. A method for the general problem was first completely described rigorously by

Lagrange Joseph-Louis Lagrange (born Giuseppe Luigi Lagrangiacontinued fraction for the

square root In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or  ⋅ ) is . For example, 4 and −4 are square roots of 16, because . ...

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 Algebra () is one of the areas of mathematics, broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathem ...

at a time much later than Bhaskara's, nay nearly equal up to our times, equalled the marvellous complexity and ingenuity of ''chakravala''." Hermann Hankel calls the ''chakravala'' method :"the finest thing achieved in the theory of numbers before Lagrange."

The method

From Brahmagupta's identity, we observe that for given ''N'', :

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

For the equation

x^2 - Ny^2 = k

, this allows the "composition" (''samāsa'') of two solution triples

(x_1, y_1, k_1)

and

(x_2, y_2, k_2)

into a 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

a^2 - Nb^2 = k

) can be composed with the trivial triple

(m, 1, m^2 - N)

to get the new triple

(am + Nb, a+bm, k(m^2-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 \Rightarrow \left(\frac\right)^2 - N\left(\frac\right)^2 = \frac

Since the signs inside the squares do not matter, the following substitutions are possible: :

a\leftarrow\frac, b\leftarrow\frac, k\leftarrow\frac

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 ''m''² − ''N'' and hence that of (''m''² − ''N'')/''k''. Then the substitution relations are applied for ''m'' equal to the chosen value. This results in a new triple (''a'', ''b'', ''k''). The process is repeated until a triple with

k=1

is found. This method always terminates with a solution (proved by Lagrange in 1768). Optionally, we can stop when ''k'' is ±1, ±2, or ±4, as Brahmagupta's approach gives a solution for those cases.

Brahmagupta's composition method

In AD 628, Brahmagupta discovered a general way to find

x

and

y

x^2 = Ny^2 + 1,

when given

a^2 = Nb^2 + k

, when k is ±1, ±2, or ±4.

k = -1

Using Brahmagupta's identity, to compose the triple

(a,b,k)

with itself:

(a^2+Nb^2)^2-N(2ab)^2=k^2

\Rightarrow

(2a^2-k)^2-N(2ab)^2=k^2

The new triple can be expressed as

(2a^2-k,2ab,k^2)

. Substituting

k=-1

to get the solution:

x=2a^2+1, 
y=2ab

k = ±2

Again using the equation,

(2a^2-k)^2-N(2ab)^2=k^2

\Rightarrow

\left( \frac \right)^2-N \left (\frac \right)^2=1

Substituting

k=2

x=a^2-1, 
y=ab

Substituting

k=-2

x=a^2+1, 
y=ab

k = 4

Substituting

k=4

into the equation

(\frac)^2-N(\frac)^2=1

creates the triple

(\frac,\frac,1)

. Which is a solution if

a

is even:

x=\frac,
y=\frac

If a is odd, start with the equations

(\frac)^2-N(\frac)^2=1

and

(\frac)^2-N(\frac)^2=1

. Leading to the triples

(\frac,\frac,1)

and

(\frac,\frac,1)

. Composing the triples gives

(\frac(a^2-3))^2-N(\frac(a^2-1))^2=1

When

a

is odd,

x=\frac(a^2-3))^2,
y=(\frac(a^2-1))^2

k = -4

When

k=-4

, then

(\frac)^2-N(\frac)^2=-1

. Composing with itself yields

(\frac)^2-N(\frac)^2=1

\Rightarrow

(\frac)^2-N(\frac)^2=1

. Again composing itself yields

(\frac)^2-N(\frac)^2=1

\Rightarrow

(\frac)^2-N(\frac)^2=1

Finally, from the earlier equations, compose the triples

(\frac,\frac,1)

and

(\frac,\frac,1)

, to get

(\frac)^2-N(\frac)^2=1

\Rightarrow

(\frac)^2-N(\frac)^2=1

\Rightarrow

(\frac)^2-N(\frac)^2=1

. This give us the solutions

x=\frac
y=\frac

(Note,

k=-4

is useful to find a solution to

Pell's Equation Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form x^2 - ny^2 = 1, where ''n'' is a given positive nonsquare integer, and integer solutions are sought for ''x'' and ''y''. In Cartesian coordinate ...

, but it is not always the smallest integer pair. e.g.

36^2-52*5^2=-4

. The equation will give you

x=1093436498,y=151632270

, which when put into Pell's Equation yields

1195601955878350801-1195601955878350800 = 1

, which works, but so does

x = 649,y=90

for

N=52

Examples

''n'' = 61

The ''n'' = 61 case (determining an integer solution satisfying

a^2 - 61b^2 = 1

), issued as a challenge by Fermat many centuries later, was given by Bhaskara as an example. We start with a solution

a^2 - 61b^2 = 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, m^2-61)

gives the triple

(8m+61, 8+m, 3(m^2-61))

, which is scaled down (or Bhaskara's lemma is directly used) to get: :

\left( \frac, \frac, \frac \right).

For 3 to divide

8+m

and

, m^2-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 three times, with

m=

respectively, when k becomes square and scaling can be applied, this gives

(1523/2, 195/2, 1)\,

. Finally, such procedure can be repeated until the solution is found (requiring 9 additional self-compositions and 4 additional square-scalings):

(1766319049,\, 226153980,\, 1)

. This is the minimal integer solution.

''n'' = 67

Suppose we are to solve

x^2 - 67y^2 = 1

for ''x'' and ''y''.The example in this section is given (with notation

Q_n

for ''k'',

P_n

for ''m'', etc.) in: We start with a solution

a^2 - 67b^2 = 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 , ''m''² − 67, is minimal. We then update ''a'', ''b'', and ''k'' to

\frac, \frac

and

\frac

respectively. ;First iteration We have

(a,b,k) = (8,1,-3)

. We want a positive integer ''m'' such that ''k'' divides ''a'' + ''bm'', i.e. 3 divides 8 + m, and , ''m''² − 67, is minimal. The first condition implies that ''m'' is of the form 3''t'' + 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

\left(\frac, \frac, \frac\right)

, 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,b,k) = (41,5,6)

. We want an ''m'' > 0 such that ''k'' divides ''a'' + ''bm'', i.e. 6 divides 41 + 5''m'', and , ''m''² − 67, is minimal. The first condition implies that ''m'' is of the form 6''t'' + 5 (i.e. 5, 11, 17,… etc.), and among such ''m'', , ''m''² − 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 + 11''m'', we must have ''m'' = 2 + 7''t'' (i.e. 2, 9, 16,… etc.) 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\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

\frac

to within a margin of about

2 \times 10^

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. *Clas-Olaf Selenius
"Rationale of the chakravala process of Jayadeva and Bhaskara II"
''Historia Mathematica'' 2 (1975), pp. 167–184. *Clas-Olaf Selenius, "Kettenbruchtheoretische Erklärung der zyklischen Methode zur Lösung der Bhaskara-Pell-Gleichung", ''Acta Acad. Abo. Math. Phys.'' 23 (10) (1963), pp. 1–44. *Hoiberg, Dale & Ramchandani, Indu (2000). ''Students' Britannica India''. Mumbai: Popular Prakashan. *Goonatilake, Susantha (1998). ''Toward a Global Science: Mining Civilizational Knowledge''. Indiana: Indiana University Press. . *Kumar, Narendra (2004). ''Science in Ancient India''. Delhi: Anmol Publications Pvt Ltd. *Ploker, Kim (2007) "Mathematics in India". ''The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook'' New Jersey: Princeton University Press. *

External links

{{number theoretic algorithms Brahmagupta Diophantine equations Number theoretic algorithms Indian mathematics