Narayana, Pell's Equation and the Chakravala Method

Find whole numbers $x$ and $y$ such that ${61x^2+1=y^2}$. The smallest answer is ${x=226{,}153{,}980}$, ${y=1{,}766{,}319{,}049}$, so guessing is hopeless. Indian mathematicians found a method that produces such answers in a few steps: Brahmagupta's composition and the chakravala (cyclic) method. On this page we follow the method as it was explained by Narayana Pandita in his Ganita Kaumudi and compare it with the modern method of continued fractions.

On this page: Narayana and his books · The equation ${Nx^2+1=y^2}$ · Brahmagupta's composition · The chakravala method · Example: ${N=13}$ · Example: ${N=61}$ · Continued fractions

Narayana and His Books

Narayana Pandita lived in the 14th century; his arithmetic, the Ganita Kaumudi ("Moonlight of Calculation"), is dated 1356. He also wrote an algebra, the Bijaganita Vatamsa.

The Ganita Kaumudi covers a wide range of topics: arithmetic, combinatorics, magic squares, and the problem of a herd of cows in which every cow has a calf each year from its fourth year on. That problem leads to the sequence 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, …, in which each term is the sum of the previous one and the one three places back.

One chapter, on "square natures" (varga-prakriti), deals with the equation of this page. Narayana did not invent the methods: they go back to Brahmagupta (628) and to the chakravala method described by Bhaskara II (1150). His contribution is a clear and systematic statement of the rules with many examples.

The Equation ${Nx^2+1=y^2}$

Let $N$ be a positive whole number that is not a perfect square. We look for whole numbers $x$ and $y$ with

${Nx^2+1=y^2}$,   or equivalently   ${y^2-Nx^2=1}$.

In Europe it is called Pell's equation, after an English mathematician who in fact had little to do with it. Fermat posed it as a challenge in 1657, and Lagrange proved in 1768 that it always has a solution. Indian mathematicians had worked with it for about a thousand years before.

The Indian names are useful: $N$ is the prakriti ("nature", the multiplier), $x$ is the lesser root, $y$ is the greater root, and the number added, here 1, is the kshepa ("interpolator"). More generally they studied ${Nx^2+k=y^2}$ for any interpolator $k$, positive or negative.

The simplest case, ${N=2}$. ${2\cdot 2^2+1=9=3^2}$, so ${x=2}$, ${y=3}$. For ${N=7}$, a short search gives ${7\cdot 3^2+1=64=8^2}$. Such small solutions are easy to find; the difficulty starts with numbers like 61 or 92.

Brahmagupta's Composition

Brahmagupta discovered a way to combine two known equations into a new one. Narayana calls it bhavana ("composition"). Suppose

${N\alpha^2+k=\beta^2}$   and   ${N\alpha'^2+k'=\beta'^2}$.

Write the two triples (lesser root, greater root, interpolator) one under the other. Then a new triple is

${x=\alpha\beta'+\alpha'\beta}$,   ${y=\beta\beta'+N\alpha\alpha'}$,   interpolator ${kk'}$.

In words: the sum of the cross products is the new lesser root; the product of the greater roots plus $N$ times the product of the lesser roots is the new greater root; the interpolators are multiplied. The rule also works with minus signs: ${x=\alpha\beta'-\alpha'\beta}$, ${y=\beta\beta'-N\alpha\alpha'}$.

The reason is the identity

${\left(\beta^2-N\alpha^2\right)\left(\beta'^2-N\alpha'^2\right)}={\left(\beta\beta'+N\alpha\alpha'\right)^2-N\left(\alpha\beta'+\alpha'\beta\right)^2}$,

which you can check by multiplying out both sides.

Example 1. Compose the solution ${x=3}$, ${y=8}$ of ${7x^2+1=y^2}$ with itself (${\alpha=\alpha'=3}$, ${\beta=\beta'=8}$, ${k=k'=1}$):

${x}={3\cdot 8+3\cdot 8}={48}$,   ${y}={8\cdot 8+7\cdot 3\cdot 3}={127}$,   interpolator ${1\cdot 1=1}$.

Check: ${7\cdot 48^2+1}={7\cdot 2304+1}={16{,}129}={127^2}$. Composing again and again gives infinitely many solutions, as Narayana remarks.

When both triples are the same, the rule becomes

${x=2\alpha\beta}$,   ${y=\beta^2+N\alpha^2}$,   interpolator $k^2$.

This is very useful when ${k=-1}$: then ${k^2=1}$. If $k$ is ${\pm 2}$ or ${\pm 4}$, composing and then dividing by $k$ also leads to an interpolator 1. So the whole problem reduces to finding some triple with interpolator ${\pm 1}$, ${\pm 2}$ or ${\pm 4}$.

The Chakravala Method

The chakravala ("wheel") method produces such a triple. It is described by Bhaskara II and set out again by Narayana; it may be older, since a fragment attributed to the 11th-century author Jayadeva already contains it.

Start with ${x=1}$ and $y$ equal to the whole number whose square is nearest to $N$. Then ${N\cdot 1^2+k=y^2}$ with ${k=y^2-N}$. Now repeat the following step.

The step is just a composition of $(x,\ y,\ k)$ with the easy triple ${(1,\ m,\ m^2-N)}$, followed by division by $k$. The choice of $m$ makes the division exact and keeps the new interpolator small. Narayana finds $m$ with the kuttaka ("pulveriser"), the Indian method for linear equations ${ax+b=cy}$ in whole numbers. Repeating the step, one always reaches the interpolator 1 (Lagrange's theorem guarantees it), usually after reaching ${\pm 1}$, ${\pm 2}$ or ${\pm 4}$, where composition can finish the work.

Example 2. ${N=7}$. The square nearest to 7 is ${9=3^2}$, so we start with ${(x,\ y,\ k)=(1,\ 3,\ 2)}$: ${7\cdot 1^2+2=9}$.

We need ${1\cdot m+3}$ divisible by 2, so $m$ is odd. Among odd numbers, ${m=3}$ gives ${m^2=9}$, the closest to 7. Then

${x}={\frac{1\cdot 3+3}{2}}={3}$,   ${y}={\frac{3\cdot 3+7\cdot 1}{2}}={8}$,   ${k}={\frac{9-7}{2}}={1}$.

One step gives the solution ${7\cdot 3^2+1=8^2}$.

Example: ${N=13}$

Solve ${13x^2+1=y^2}$. The square nearest to 13 is ${16=4^2}$, so we start with ${(1,\ 4,\ 3)}$: ${13\cdot 1^2+3=16}$.

Step 1. ${m+4}$ must be divisible by 3, so ${m=2,\ 5,\ 8,\ \dots}$ Among these, ${2^2=4}$ is closest to 13 (it differs by 9; ${5^2=25}$ differs by 12). With ${m=2}$:

${x}={\frac{1\cdot 2+4}{3}}={2}$,   ${y}={\frac{4\cdot 2+13\cdot 1}{3}}={7}$,   ${k}={\frac{4-13}{3}}={-3}$.

Check: ${13\cdot 2^2-3}={52-3}={49}={7^2}$.

Step 2. ${2m+7}$ must be divisible by 3, so ${m=1,\ 4,\ 7,\ \dots}$ The best is ${m=4}$ (${16-13=3}$):

${x}={\frac{2\cdot 4+7}{3}}={5}$,   ${y}={\frac{7\cdot 4+13\cdot 2}{3}}={18}$,   ${k}={\frac{16-13}{-3}}={-1}$.

Check: ${13\cdot 5^2-1}={325-1}={324}={18^2}$.

Composition. The interpolator is ${-1}$, so we compose ${(5,\ 18,\ -1)}$ with itself:

${x}={2\cdot 5\cdot 18}={180}$,   ${y}={18^2+13\cdot 5^2}={324+325}={649}$,   ${k}={(-1)^2}={1}$.

Check: ${13\cdot 180^2+1}={13\cdot 32{,}400+1}={421{,}201}={649^2}$. This is the smallest solution.

If we continue the chakravala steps instead of composing, we get ${(38,\ 137,\ -3)}$, ${(71,\ 256,\ 3)}$ and then ${(180,\ 649,\ 1)}$: the same answer, after three more steps instead of one composition.

Example: ${N=61}$

This is the famous example solved by Bhaskara II. Five centuries later Fermat sent the same equation as a challenge to other mathematicians.

Start. ${8^2=64}$ is the square nearest to 61, so the first triple is ${(1,\ 8,\ 3)}$: ${61\cdot 1^2+3=64}$.

Chakravala step. ${m+8}$ must be divisible by 3, so ${m=1,\ 4,\ 7,\ 10,\ \dots}$ Among these, ${7^2=49}$ is closest to 61 (it differs by 12; ${10^2=100}$ differs by 39). With ${m=7}$:

${x}={\frac{1\cdot 7+8}{3}}={5}$,   ${y}={\frac{8\cdot 7+61\cdot 1}{3}}={\frac{117}{3}}={39}$,   ${k}={\frac{49-61}{3}}={-4}$.

Check: ${61\cdot 5^2-4}={1525-4}={1521}={39^2}$.

Composition. Now Bhaskara uses Brahmagupta's rules for the interpolator ${-4}$. Dividing ${61\cdot 5^2-4=39^2}$ by 4 gives a solution in fractions with interpolator ${-1}$:

${61\left(\frac{5}{2}\right)^2-1}={\left(\frac{39}{2}\right)^2}$.

Composing ${\left(\frac{5}{2},\ \frac{39}{2},\ -1\right)}$ with itself gives interpolator 1:

${x}={2\cdot\frac{5}{2}\cdot\frac{39}{2}}={\frac{195}{2}}$,   ${y}={\left(\frac{39}{2}\right)^2+61\left(\frac{5}{2}\right)^2}={\frac{1521+1525}{4}}={\frac{1523}{2}}$.

Composing ${\left(\frac{195}{2},\ \frac{1523}{2},\ 1\right)}$ with ${\left(\frac{5}{2},\ \frac{39}{2},\ -1\right)}$ once more gives whole numbers with interpolator ${-1}$:

${x}={\frac{195\cdot 39+5\cdot 1523}{4}}={\frac{7605+7615}{4}}={3805}$,

${y}={\frac{1523\cdot 39+61\cdot 195\cdot 5}{4}}={\frac{59{,}397+59{,}475}{4}}={29{,}718}$.

Check: ${61\cdot 3805^2-1}={61\cdot 14{,}478{,}025-1}={883{,}159{,}524}={29{,}718^2}$.

Last composition. Composing ${(3805,\ 29{,}718,\ -1)}$ with itself:

${x}={2\cdot 3805\cdot 29{,}718}={226{,}153{,}980}$,

${y}={29{,}718^2+61\cdot 3805^2}={883{,}159{,}524+883{,}159{,}525}={1{,}766{,}319{,}049}$.

So ${61\cdot 226{,}153{,}980^2+1}={1{,}766{,}319{,}049^2}$, the smallest solution. Without the composition shortcut the chakravala reaches the same answer after 13 steps.

Continued Fractions

In Europe the equation was solved with continued fractions, worked out by Euler and Lagrange in the 18th century. The square root of $N$ is written as

${\sqrt{N}}={a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\dots}}}}$,   briefly ${\sqrt{N}=[a_0;\ a_1,\ a_2,\ a_3,\ \dots]}$,

where at every stage we take the whole part and invert what is left. Cutting the fraction off after a few terms gives the convergents ${\frac{p}{q}}$, fractions that approximate $\sqrt{N}$ very well.

Example 3. ${\sqrt{7}\approx 2.64575}$. The whole part is 2. Then ${\frac{1}{0.64575}\approx 1.5486}$ (whole part 1), ${\frac{1}{0.5486}\approx 1.8229}$ (whole part 1), ${\frac{1}{0.8229}\approx 1.2153}$ (whole part 1), ${\frac{1}{0.2153}\approx 4.6458}$ (whole part 4), and from here the pattern repeats: ${\sqrt{7}=[2;\ 1,\ 1,\ 1,\ 4,\ 1,\ 1,\ 1,\ 4,\ \dots]}$. The convergents are

${2}$,   ${2+\frac{1}{1}=3}$,   ${2+\cfrac{1}{1+\frac{1}{1}}=\frac{5}{2}}$,   ${2+\cfrac{1}{1+\cfrac{1}{1+\frac{1}{1}}}=\frac{8}{3}}$.

The last one, at the end of the first period, gives ${p=8}$, ${q=3}$: exactly the solution ${7\cdot 3^2+1=8^2}$.

For ${\sqrt{13}=[3;\ 1,\ 1,\ 1,\ 1,\ 6,\ \dots]}$ the convergents and the values of ${p^2-13q^2}$ are:

Compare with the chakravala for ${N=13}$: the pairs it produced, ${(1,\ 4)}$, ${(2,\ 7)}$, ${(5,\ 18)}$, ${(38,\ 137)}$, ${(71,\ 256)}$, ${(180,\ 649)}$, are all in the table, and so are its interpolators 3, ${-3}$, ${-1}$, ${-3}$, 3, 1. The chakravala simply skips some convergents, which is why it is fast. The same is true for ${N=61}$: every triple of the cyclic method is a convergent of ${\sqrt{61}}={[7;\ 1,\ 4,\ 3,}\allowbreak{1,\ 2,\ 2,\ 1,}\allowbreak{3,\ 4,\ 1,\ 14,\ \dots]}$.

The doubling rule of composition also has a meaning here. If ${\frac{p}{q}}$ is the convergent at the end of the first period, then

${\frac{p^2+Nq^2}{2pq}}$

is the convergent at the end of the second period. For ${N=13}$: ${\frac{18^2+13\cdot 5^2}{2\cdot 18\cdot 5}}={\frac{649}{180}}$. For ${N=61}$ the convergent ${\frac{29{,}718}{3805}}$ gives ${\frac{1{,}766{,}319{,}049}{226{,}153{,}980}}$.

Did Narayana think in terms of continued fractions? There is no sign of it in his text: he works with triples and compositions. Modern historians have shown that his rules are equivalent to properties of continued fractions, so the Indian cyclic method and the European method are two views of the same mathematics. The Indian one was found several centuries earlier and, as the examples show, often needs fewer steps.

See also: A rationale of Bhaskara · Madhava's sine and cosine series · Calculus in Indian mathematics · Divisibility