A method that is allowed to miss

One solution that makes all the others showed that every whole-number solution of $x^2 - Dy^2 = 1$ is a power of the smallest, and found the smallest by walking the convergents of the continued fraction of $\sqrt D$. For $D = 61$ that walk ends at the pair 1,766,319,049 and 226,153,980, after 22 convergents. It also mentioned, in a sentence, that Indian mathematicians had a faster method six centuries before Europe had a slow one.

That method is worth running in full, because its central idea is counterintuitive. It does not try to solve the equation at each step. It keeps a pair that fails by a small amount and improves the failure, and it is exactly that permission to miss that lets it move quickly.

Starting from a near miss #

The method is the chakravala, the “cyclic” method, described by Jayadeva in the eleventh century and made famous by Bhāskara II’s Bījagaṇita of 1150, whose showpiece example was exactly $D = 61$. It begins with the obvious approximation: the square nearest to 61 is $8^2 = 64$, so $8^2 - 61 \cdot 1^2 = 3$. The pair $(a, b) = (8, 1)$ does not solve the equation. It misses by $k = 3$.

Every row of the table is such a near miss: a pair of whole numbers $a$ and $b$ and the amount $k = a^2 - 61b^2$ by which they fail. The figure checks each row in exact arithmetic. What changes from row to row is $k$ — 3, then $-4$, $-5$, 5, 4, $-3$, $-1$, and back through the same sizes in reverse — and the method stops the moment $k$ reaches 1.

The pairs themselves grow fast: 8, 39, 164, 453, and eventually the ten-digit answer. The misses never grow at all. After the first step, $|k|$ stays below $\sqrt{61}$ at every row, and that combination — numbers growing, errors staying small — is what a good approximation scheme looks like.

Combining two misses #

The step rests on an identity Brahmagupta stated in 628, which the Pell essay met as the multiplication of solutions. Any two near misses can be combined:

$$(a^2 - Db^2)(c^2 - Dd^2) = (ac + Dbd)^2 - D(ad + bc)^2.$$

The misses multiply. Composing two solutions of the equation gives a solution, because $1 \times 1 = 1$; composing near misses gives a near miss whose error is the product of theirs.

On its own, composing makes things worse: the errors multiply. The chakravala composes the current near miss $(a, b)$ with a very simple helper, $(m, 1)$, whose miss is $m^2 - D$, and then does something the identity does not suggest. It chooses $m$ so that the result can be divided by $k^2$, which divides the new miss $k(m^2 - D)$ by $k^2$ and leaves $(m^2 - D)/k$.

In the first step, $(8, 1)$ composed with $(7, 1)$ gives $(8 \cdot 7 + 61 \cdot 1,\ 8 + 7) = (117, 15)$, missing by $3 \times (-12) = -36$. All three numbers are divisible by 3, so $(117, 15)$ divided by 3 is $(39, 5)$, and $-36$ divided by 9 is $-4$. The new row misses by 4 instead of 3 — slightly worse in size, but on a pair five times larger, which makes it a far better approximation to $\sqrt{61}$ as a fraction: $39/5 = 7.8$ against $\sqrt{61} \approx 7.8102$.

The choice of m #

Two conditions pick the helper, and both are in the table’s second column. First, $m$ must make $a + bm$ divisible by $|k|$. That is a condition on $m$ modulo $|k|$ — the arithmetic of numbers that wrap — and it is enough for everything else to divide as well. The reason is a one-line identity: $a(a + bm) - b(am + Db) = a^2 - Db^2 = k$, so once $k$ divides $a + bm$, it divides $b(am + Db)$, and since $b$ shares no factor with $k$ it divides $am + Db$. The new miss is then automatically a whole number.

Second, among the admissible values of $m$, the method takes the one with $m^2$ closest to $D$. That makes $|m^2 - D|$ as small as the congruence allows, and since the new miss is $(m^2 - D)/k$, it keeps the new miss small. For $D = 61$ the admissible values run through 6, 7, 8 and 9 — always one of the whole numbers whose squares straddle 61 most closely.

The second step shows the rule at work. From the row $(39, 5)$, missing by $-4$, the helper must make $39 + 5m$ divisible by 4. Since 39 leaves a remainder of 3 on division by 4 and 5 leaves 1, $m$ must leave a remainder of 1: the candidates are 1, 5, 9, 13 and so on. Of these, 9 has its square closest to 61, since 81 − 61 = 20 while 25 − 61 = −36. So $m = 9$, and composing gives $(39 \cdot 9 + 61 \cdot 5,\ 39 + 5 \cdot 9) = (656, 84)$, missing by −4 × 20 = −80. Dividing the pair by 4 gives $(164, 21)$, and dividing the miss by 16 gives $-5$ — the third row of the table.

The two conditions pull in different directions, and the method needs both. Divisibility alone would allow huge helpers and huge misses; closeness alone would give misses that are not whole numbers. Together they give a sequence of small whole-number misses on rapidly growing pairs, and the cycle closes when the miss comes back to 1.

A shortcut from −1 #

Six steps into the table for $D = 61$, the miss is $-1$: $29{,}718^2 - 61 \cdot 3{,}805^2 = -1$. That row is not a solution, but composing it with itself squares its error, and $(-1)^2 = 1$.

$$(29{,}718^2 + 61 \cdot 3{,}805^2,\ 2 \cdot 29{,}718 \cdot 3{,}805) = (1{,}766{,}319{,}049,\ 226{,}153{,}980).$$

That is the fundamental solution, reached from the halfway row without the last seven steps. Brahmagupta already had rules of this kind: from a miss of $-1$ square once; from a miss of $\pm 2$ square and halve; from $\pm 4$ a slightly longer formula finishes the job. The second half of the table for $D = 61$ runs the misses back in reverse order — $-3$, 4, 5, $-5$, $-4$, 3, 1 — which is the cycle closing on itself, and the shortcut simply jumps across it.

The same halfway shortcut explains a pattern from the Pell essay. An equation whose miss reaches $-1$ along the way is one for which $x^2 - Dy^2 = -1$ has a solution — the row itself is one — and that happens exactly for the equations whose continued fraction has an odd period.

A second equation #

For $D = 94$ the miss never reaches $-1$, and the continued fraction of $\sqrt{94}$ has an even period of 16, so $x^2 - 94y^2 = -1$ has no solution. The chakravala still reaches the fundamental solution, $(2{,}143{,}295,\ 221{,}064)$, in 9 steps. Its misses run 6, $-5$, 9, 3, 2 and back, symmetric about the middle row just as for 61.

The middle row has a miss of 2, and Brahmagupta’s second rule applies there. The row is $1{,}464^2 - 94 \cdot 151^2 = 2$. Composing it with itself gives $(1{,}464^2 + 94 \cdot 151^2,\ 2 \cdot 1{,}464 \cdot 151) = (4{,}286{,}590,\ 442{,}128)$, missing by 4, and halving both numbers — which divides the miss by 4 — gives $(2{,}143{,}295,\ 221{,}064)$ with a miss of 1. The fundamental solution is again reached from the middle of the cycle.

The symmetry of the misses is no accident. It is the same palindrome that appears in the period of the continued fraction of $\sqrt D$, which reads the same forwards and backwards before its last term, and the halfway row sits where the sequence turns round.

Keeping the miss small #

Dividing each miss by $\sqrt D$ puts four equations on one scale, and all four runs stay strictly between $-1$ and $1$ after the first step. The same bound held in every equation from $D = 2$ to $D = 1000$ when the method was run on all of them. The new miss is $(m^2 - D)/k$, and an admissible $m$ can always be found within about $|k|/2$ of $\sqrt D$, because the admissible values are spaced $|k|$ apart. That makes $|m^2 - D|$ at most about $|k| \sqrt D$, and dividing by $|k|$ leaves a new miss of roughly $\sqrt D$ at most. That is a sketch of why the bound holds, not a proof of the strict inequality the runs display.

Small misses matter because a near miss $a^2 - Db^2 = k$ makes $a/b$ an excellent approximation to $\sqrt D$: dividing by $b^2$ gives $|a/b - \sqrt D| \cdot |a/b + \sqrt D| = |k|/b^2$, and since $a/b + \sqrt D$ is close to $2\sqrt D$, the error in $a/b$ is about $|k|/(2\sqrt D\, b^2)$. A classical theorem makes the conclusion exact: whenever $|a^2 - Db^2| < \sqrt D$, the fraction $a/b$ is one of the convergents of $\sqrt D$. Every row the chakravala produces after the first is a convergent, so it walks the same road as the continued fraction — it just does not stop at every milestone.

Read as fractions, the rows for $D = 61$ close in fast. $39/5 = 7.8$ is off from $\sqrt{61} \approx 7.81025$ by about a hundredth; $164/21 \approx 7.80952$ by about seven ten-thousandths; $453/58 \approx 7.81034$ by about one ten-thousandth. How close a fraction can get shows that every irrational number has infinitely many fractions within $1/q^2$ of it, and the chakravala’s rows land inside half of that allowance, which is what being a convergent guarantees.

Fewer steps, every time #

Run both methods on every equation with $D$ up to 100 that is not a square. They find the same fundamental solution every time, and the chakravala takes fewer steps on all 90 of them: 240 steps in total against 476 convergents, roughly half. The saving is largest exactly where the continued fraction’s period is long, which is where the fundamental solution is large and the problem is hard.

The reason became clear only in the twentieth century. The ordinary continued fraction always rounds down, taking the whole part of each complete quotient. The chakravala’s choice of $m$ nearest to $\sqrt D$ corresponds to rounding to the nearest whole number, sometimes up, and a continued fraction that rounds to the nearest integer reaches the same convergents while skipping some of the intermediate ones. Rounding to the nearest is never worse and usually better, and Bhāskara’s method had been rounding to the nearest all along.

The tree of every fraction exactly once makes the saving visible. The path down that tree towards $\sqrt{61}$ turns right seven times, then left once, then right four times, then left three times, and so on: the lengths of the runs are the terms of the continued fraction, $7, 1, 4, 3, \ldots$, and the convergents are the fractions where the path changes direction. The ordinary expansion reports every change of direction — 7/1, 8/1, 39/5, 125/16, 164/21. The chakravala’s rows are 8/1, 39/5, 164/21: it passes 7/1 and 125/16 without stopping, and on longer periods it skips more.

The same idea recurs across number theory. The composition identity is a law for combining numbers of the form $a^2 - Db^2$, and two squares and a lattice uses its cousin, $(a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2$, to build sums of two squares from smaller ones — the same trade of a hard target for a product of easy ones.

Why it has to stop #

The Indian texts give the method and a great many worked examples, but no proof that the cycle always returns to a miss of 1. That proof came much later, and it rests on the same fact that makes the continued fraction periodic: the state of the computation is a small amount of whole-number data confined to a finite range, so it must repeat, and when it repeats the miss has come back to where it started. Why the expansion has to repeat makes that argument for the continued fraction and draws the finite set of states it moves through.

The chakravala’s structure also has a shape that a fraction that never closes would recognise: at every step it takes the best available whole-number approximation and carries the remainder forward. What distinguishes it is only which approximation counts as best.

It is also the mirror image of a proof by descent. The square that cannot shrink assumes an exact solution of $a^2 = 2b^2$ and produces a smaller one, and a smaller one, until whole numbers run out — so no exact solution exists. The chakravala starts from an inexact solution and produces larger ones whose errors stay bounded, until one of them is exact — so an exact solution is found. One method shrinks a solution into a contradiction; the other grows a near miss into an answer, and both depend on a quantity that can only take finitely many values along the way.

A method from the other side of the world #

Fermat posed the case $D = 61$ to English mathematicians in 1657 as a challenge, apparently because he knew the answer was large, and Brouncker and Wallis solved it with methods related to continued fractions. Bhāskara had published the same answer, by the cyclic method, five centuries earlier, and Jayadeva’s description of the method is older still. The equation carries the name of John Pell because of a misattribution by Euler, as the Pell essay recounts; the method that solves it most efficiently by hand carries no European name at all.

The chakravala was not a lucky trick. It encodes three ideas that European mathematics reached separately and later: a composition law for near misses, a rounding rule that picks the nearest approximation, and the periodicity that guarantees termination. Brahmagupta’s identity is the first; the choice of $m$ is the second; and the symmetric cycle of misses is the visible trace of the third.

Generating an infinite family of solutions from one by a fixed rule is a pattern that recurs well beyond Pell’s equation. A tree that holds every triple produces every Pythagorean triple from $(3, 4, 5)$ by three matrices, just as powers of the fundamental solution produce every solution here. The chakravala sits one level earlier: it is the rule that finds the seed.

A bound on the miss that was observed, not proved #

Every table was computed, not quoted. Each row is a near miss checked in exact whole-number arithmetic, each division was checked to leave no remainder, and each final answer was checked against the continued fraction’s; but the tables stop at the first solution, and the infinite family of later solutions is the Pell essay’s, not these figures’.

The bound on the miss is observed. That $|k|$ stays below $\sqrt D$ after the first step held for every $D$ up to 1,000; the figure shows four of them. The argument above says why the choice of $m$ keeps $k$ small, but it is a sketch, not a proof of the exact bound.

And the count stops at 100. The comparison of steps against convergents is shown for 90 equations and was run to 1,000 with the same result; beyond that it is the theory of nearest-integer continued fractions, not the figure, that says it continues.

Still open: how large the first solution can be #

The chakravala finds the fundamental solution faster than the continued fraction, but both take a number of steps that grows with the period of $\sqrt D$, and both must write down the solution, which can have enormously many digits. The logarithm of the fundamental solution, the regulator, is linked to the class number by Dirichlet’s class number formula, and the product of the two grows, on a logarithmic scale, like $\sqrt D$. How that product divides between the two factors is not understood: it is conjectured that for most prime $D$ the class number is 1 and the regulator is as large as it can be, but it is not even known whether infinitely many real quadratic fields have class number 1.

Aim beside the target #

The cyclic method solves an equation by never trying to solve it until the last step. It keeps an approximation that misses by a small amount, combines it with a helper chosen so that the miss can be divided out, and lets the misses cycle until one of them is exactly 1. The approximations grow exponentially while the misses stay small, which is what makes the method fast.

When a direct search for an exact solution is slow, look for an approximate object that can be improved by an exact operation. Near misses compose; exact solutions are just the near misses whose miss happens to be 1.