Chakravala method

Last updated • 8 min readFrom Wikipedia, The Free Encyclopedia

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

Contents

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

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. [6]

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

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

Jayadeva and Bhaskara offered the first complete solution to the equation, using the chakravala method to find for the solution

This case was notorious for its difficulty, and was first solved in Europe 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 in 1766. [7] Lagrange's method, however, requires the calculation of 21 successive convergents of the simple 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." [8]

The method

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

For the equation , this allows the "composition" (samāsa) of two solution triples and into a new triple

In the general method, the main idea is that any triple (that is, one which satisfies ) can be composed with the trivial triple to get the new triple for any m. Assuming we started with a triple for which , this can be scaled down by k (this is Bhaskara's lemma):

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

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 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 is found. This method always terminates with a solution (proved by Lagrange in 1768). [9] 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 and of when given , when k is ±1, ±2, or ±4. [10]

k = ±1

Using Brahmagupta's identity to compose the triple with itself:

The new triple can be expressed as .

Substituting gives a solution:

For , the original was already a solution. Substituting yields a second:

k = ±2

Again using the equation,

Substituting ,

Substituting ,

k = 4

Substituting into the equation creates the triple .

Which is a solution if is even:

If a is odd, start with the equations and .

Leading to the triples and . Composing the triples gives

When is odd,

k = -4

When , then . Composing with itself yields .

Again composing itself yields

Finally, from the earlier equations, compose the triples and , to get

.

This give us the solutions

[11]

(Note, is useful to find a solution to Pell's Equation, but it is not always the smallest integer pair. e.g. . The equation will give you , which when put into Pell's Equation yields , which works, but so does for .

Examples

n = 61

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

We start with a solution for any k found by any means. In this case we can let b be 1, thus, since , we have the triple . Composing it with gives the triple , which is scaled down (or Bhaskara's lemma is directly used) to get:

For 3 to divide and to be minimal, we choose , so that we have the triple . Now that k is 4, we can use Brahmagupta's idea: it can be scaled down to the rational solution , which composed with itself three times, with respectively, when k becomes square and scaling can be applied, this gives . Finally, such procedure can be repeated until the solution is found (requiring 9 additional self-compositions and 4 additional square-scalings): . This is the minimal integer solution.

n = 67

Suppose we are to solve for x and y. [12]

We start with a solution for any k found by any means; in this case we can let b be 1, thus producing . At each step, we find an m > 0 such that k divides a + bm, and |m2  67| is minimal. We then update a, b, and k to and respectively.

First iteration

We have . We want a positive integer m such that k divides a + bm, i.e. 3 divides 8 + m, and |m2  67| 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 , we get the new values . That is, we have the new solution:

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

Second iteration

We now repeat the process. We have . We want an m > 0 such that k divides a + bm, 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,… etc.), and among such m, |m2  67| is minimal for m = 5. This leads to the new solution a = (41⋅5 + 67⋅5)/6, etc.:

Third iteration

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

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

that is, we have the integer solution:

This equation approximates as to within a margin of about .

Notes

  1. 1 2 3 Hoiberg & Ramchandani – Students' Britannica India: Bhaskaracharya II, page 200
  2. Kumar, page 23
  3. Plofker, page 474
  4. 1 2 3 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. Gopal, Madan (1990). K.S. Gautam (ed.). India through the ages. Publication Division, Ministry of Information and Broadcasting, Government of India. p.  79.
  7. O'Connor, John J.; Robertson, Edmund F., "Pell's equation", MacTutor History of Mathematics Archive , University of St Andrews
  8. Kaye (1919), p. 337.
  9. 1 2 John Stillwell (2002), Mathematics and its history (2 ed.), Springer, pp. 72–76, ISBN   978-0-387-95336-6
  10. "Pell's equation". Maths History. Retrieved 2021-06-14.
  11. Datta and Singh (1962). History of Hindu Mathematics : A Source Book Parts I and II. Asia Publishing House. pp. 157–160. ISBN   8180903907.
  12. The example in this section is given (with notation for k, for m, etc.) in: Michael J. Jacobson; Hugh C. Williams (2009), Solving the Pell equation, Springer, p. 31, ISBN   978-0-387-84922-5

Related Research Articles

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

<span class="mw-page-title-main">Pythagorean triple</span> Integer side lengths of a right triangle

A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. Such a triple is commonly written (a, b, c), a well-known example is (3, 4, 5). If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer k. A triangle whose side lengths are a Pythagorean triple is a right triangle and called a Pythagorean triangle.

<span class="mw-page-title-main">Pell's equation</span> Type of Diophantine equation

Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form where n is a given positive nonsquare integer, and integer solutions are sought for x and y. In Cartesian coordinates, the equation is represented by a hyperbola; solutions occur wherever the curve passes through a point whose x and y coordinates are both integers, such as the trivial solution with x = 1 and y = 0. Joseph Louis Lagrange proved that, as long as n is not a perfect square, Pell's equation has infinitely many distinct integer solutions. These solutions may be used to accurately approximate the square root of n by rational numbers of the form x/y.

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, 3 × 5 is an integer factorization of 15, and (x – 2)(x + 2) is a polynomial factorization of x2 – 4.

<span class="mw-page-title-main">System of linear equations</span> Several equations of degree 1 to be solved simultaneously

In mathematics, a system of linear equations is a collection of two or more linear equations involving the same variables. For example,

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form, by some expression involving operations on the formal series.

Brahmagupta was an Indian mathematician and astronomer. He is the author of two early works on mathematics and astronomy: the Brāhmasphuṭasiddhānta, a theoretical treatise, and the Khandakhadyaka, a more practical text.

In algebra, the Brahmagupta–Fibonacci identity expresses the product of two sums of two squares as a sum of two squares in two different ways. Hence the set of all sums of two squares is closed under multiplication. Specifically, the identity says

In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form where a0(x), ..., an(x) and b(x) are arbitrary differentiable functions that do not need to be linear, and y′, ..., y(n) are the successive derivatives of an unknown function y of the variable x.

<span class="mw-page-title-main">Bhāskara II</span> Indian mathematician and astronomer (1114–1185)

Bhāskara II, also known as Bhāskarāchārya, was an Indian polymath, mathematician, astronomer and engineer. From verses in his main work, Siddhāṁta Śiromaṇī, it can be inferred that he was born in 1114 in Vijjadavida (Vijjalavida) and living in the Satpuda mountain ranges of Western Ghats, believed to be the town of Patana in Chalisgaon, located in present-day Khandesh region of Maharashtra by scholars. In a temple in Maharashtra, an inscription supposedly created by his grandson Changadeva, lists Bhaskaracharya's ancestral lineage for several generations before him as well as two generations after him. Henry Colebrooke who was the first European to translate (1817) Bhaskaracharya II's mathematical classics refers to the family as Maharashtrian Brahmins residing on the banks of the Godavari.

In mathematics, an Euler–Cauchy equation, or Cauchy–Euler equation, or simply Euler's equation, is a linear homogeneous ordinary differential equation with variable coefficients. It is sometimes referred to as an equidimensional equation. Because of its particularly simple equidimensional structure, the differential equation can be solved explicitly.

Indian mathematics emerged in the Indian subcontinent from 1200 BCE until the end of the 18th century. In the classical period of Indian mathematics, important contributions were made by scholars like Aryabhata, Brahmagupta, Bhaskara II, Varāhamihira, and Madhava. The decimal number system in use today was first recorded in Indian mathematics. Indian mathematicians made early contributions to the study of the concept of zero as a number, negative numbers, arithmetic, and algebra. In addition, trigonometry was further advanced in India, and, in particular, the modern definitions of sine and cosine were developed there. These mathematical concepts were transmitted to the Middle East, China, and Europe and led to further developments that now form the foundations of many areas of mathematics.

The Adomian decomposition method (ADM) is a semi-analytical method for solving ordinary and partial nonlinear differential equations. The method was developed from the 1970s to the 1990s by George Adomian, chair of the Center for Applied Mathematics at the University of Georgia. It is further extensible to stochastic systems by using the Ito integral. The aim of this method is towards a unified theory for the solution of partial differential equations (PDE); an aim which has been superseded by the more general theory of the homotopy analysis method. The crucial aspect of the method is employment of the "Adomian polynomials" which allow for solution convergence of the nonlinear portion of the equation, without simply linearizing the system. These polynomials mathematically generalize to a Maclaurin series about an arbitrary external parameter; which gives the solution method more flexibility than direct Taylor series expansion.

In algebra, Brahmagupta's identity says that, for given , the product of two numbers of the form is itself a number of that form. In other words, the set of such numbers is closed under multiplication. Specifically:

Algebra can essentially be considered as doing computations similar to those of arithmetic but with non-numerical mathematical objects. However, until the 19th century, algebra consisted essentially of the theory of equations. For example, the fundamental theorem of algebra belongs to the theory of equations and is not, nowadays, considered as belonging to algebra.

Bhaskara's Lemma is an identity used as a lemma during the chakravala method. It states that:

<span class="mw-page-title-main">Interval finite element</span>

In numerical analysis, the interval finite element method is a finite element method that uses interval parameters. Interval FEM can be applied in situations where it is not possible to get reliable probabilistic characteristics of the structure. This is important in concrete structures, wood structures, geomechanics, composite structures, biomechanics and in many other areas. The goal of the Interval Finite Element is to find upper and lower bounds of different characteristics of the model and use these results in the design process. This is so called worst case design, which is closely related to the limit state design.

<span class="mw-page-title-main">Pythagorean theorem</span> Relation between sides of a right triangle

In mathematics, the Pythagorean theorem or Pythagoras' theorem is a fundamental relation in Euclidean geometry between the three sides of a right triangle. It states that the area of the square whose side is the hypotenuse is equal to the sum of the areas of the squares on the other two sides.

In mathematics, Bhāskara I's sine approximation formula is a rational expression in one variable for the computation of the approximate values of the trigonometric sines discovered by Bhāskara I, a seventh-century Indian mathematician. This formula is given in his treatise titled Mahabhaskariya. It is not known how Bhāskara I arrived at his approximation formula. However, several historians of mathematics have put forward different hypotheses as to the method Bhāskara might have used to arrive at his formula. The formula is elegant and simple, and it enables the computation of reasonably accurate values of trigonometric sines without the use of geometry.

In mathematics, a linear recurrence with constant coefficients sets equal to 0 a polynomial that is linear in the various iterates of a variable—that is, in the values of the elements of a sequence. The polynomial's linearity means that each of its terms has degree 0 or 1. A linear recurrence denotes the evolution of some variable over time, with the current time period or discrete moment in time denoted as t, one period earlier denoted as t − 1, one period later as t + 1, etc.

References