Why the expansion has to repeat

One solution that makes all the others solved Pell’s equation by walking the continued fraction of $\sqrt D$ to the end of its period, and a method that is allowed to miss solved it faster by a cycle of near misses. Both leaned on the same unproved promise: that the expansion of $\sqrt D$ repeats, so that the walk has an end and the cycle closes.

The promise is Lagrange’s theorem of 1770, and the proof is a counting argument of the plainest kind. The interesting part is what the counting leaves behind — a finite set of states, arranged in cycles, with the expansion of $\sqrt D$ running round exactly one of them.

The expansion as a machine with a state #

To expand $\sqrt{61}$, take its whole part, 7, and invert what is left: $1/(\sqrt{61} - 7)$. Rationalising gives $(\sqrt{61} + 7)/12$, a number of the same kind. Its whole part is 1; subtract, invert, rationalise, and the result is again of the form $(P + \sqrt{61})/Q$ with whole numbers $P$ and $Q$. Every complete quotient of $\sqrt D$ has this shape, and the whole expansion can be run in whole numbers:

$$P' = aQ - P, \qquad Q' = \frac{D - P'^2}{Q}, \qquad a' = \left\lfloor \frac{\lfloor\sqrt D\rfloor + P'}{Q'} \right\rfloor.$$

The division in the middle always comes out exact, because $Q$ always divides $D - P'^2$, and only the very first whole part needs a square root. The pair $(P, Q)$ is the whole state of the computation. Knowing it determines the next term and the next pair, and nothing else about the history matters.

The first state after the whole part, $(7, 12)$, is the number $(7 + \sqrt{61})/12 \approx 1.2342$, whose whole part 1 is the next term; its conjugate $(7 - \sqrt{61})/12 \approx -0.0675$ will matter shortly. For $\sqrt{61}$ the states run $(7, 12)$, $(5, 3)$, $(7, 4)$, $(5, 9)$, $(4, 5)$, $(6, 5)$, $(4, 9)$, $(5, 4)$, $(7, 3)$, $(5, 12)$, $(7, 1)$, and then $(7, 12)$ again. From that point the terms must repeat, because the machine is in the state it was in before.

Why only finitely many states #

The pairs are not merely whole numbers; after the first step they are confined. Each complete quotient $(P + \sqrt D)/Q$ is greater than 1, since it is the tail of a continued fraction, and its conjugate $(P - \sqrt D)/Q$ — the same expression with $\sqrt D$ replaced by $-\sqrt D$ — lies between $-1$ and 0. Those two facts together force

$$0 < P < \sqrt D, \qquad \sqrt D - P < Q < \sqrt D + P.$$

The band comes straight from the two facts. Write $x = (P + \sqrt D)/Q$ and $x' = (P - \sqrt D)/Q$. Their difference is $2\sqrt D/Q$, which exceeds 1 because $x > 1$ and $x' < 0$, so $Q < 2\sqrt D$. Their sum is $2P/Q$, which is positive because $x > 1$ outweighs $x' > -1$, so $P > 0$. The conjugate being negative forces $P < \sqrt D$; being above $-1$ forces $Q > \sqrt D - P$; and $x > 1$ forces $Q < \sqrt D + P$.

Why every complete quotient after the first has those two properties is a short induction. The first, $(\lfloor\sqrt D\rfloor + \sqrt D)/(D - \lfloor\sqrt D\rfloor^2)$, can be checked directly; and if a state is greater than 1 with its conjugate between $-1$ and 0, then subtracting its whole part and inverting produces a number greater than 1 whose conjugate, the inverse of something below $-1$, lies between $-1$ and 0 again. The property is inherited at every step, so the band holds the whole expansion after its first term.

That is the shaded band in the figure. For $D = 61$, $P$ can only be 1 to 7 and $Q$ only 1 to 14, and the requirement that $Q$ divide $61 - P^2$ cuts the band’s cells down to 14 qualifying pairs. A machine with 14 possible states, run for 15 steps, must revisit one of them — the pigeonhole principle of more things than boxes — and from the first revisit on, everything repeats.

The same argument, with the band replaced by a finite set, is the reason the orbit that must come back comes back: any deterministic process on finitely many states is eventually periodic. The work is all in showing that the states are finite. Lagrange’s theorem extends the conclusion from $\sqrt D$ to every quadratic irrational, $(a + b\sqrt D)/c$, whose complete quotients have the same shape.

The same reason decimals repeat #

The argument is the continued-fraction version of a fact met much earlier. Divide 1 by 7 by long division and the digits run $0.142857142857\ldots$, repeating with period 6. The state of long division is the remainder, and the remainders after each step are 1, 3, 2, 6, 4, 5 and then 1 again: a remainder on division by 7 can only be one of six nonzero values, so it must recur, and the digits repeat from there. That is arithmetic in numbers that wrap: each new remainder is ten times the last, reduced modulo 7.

The two facts are parallel, and so are their converses. A decimal expansion eventually repeats exactly when the number is a fraction, and a continued fraction eventually repeats exactly when the number is a quadratic irrational. For fractions the continued fraction does not repeat at all — it stops, because the Euclidean algorithm that computes it strictly decreases a pair of whole numbers until one of them reaches zero, as a fraction that never closes shows. Stopping, cycling and wandering are three different fates, and they sort numbers into rational, quadratic and everything else.

“Everything else” is not uniform. The continued fraction of $e$ runs $[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots]$, a pattern Euler found, with no repetition but a perfectly regular rule; the number of the curve that is its own slope is not quadratic, yet its expansion is anything but random. The continued fraction of $\pi$ shows no pattern at all that anyone has found. Periodicity picks out the quadratic irrationals exactly, and says nothing about the rest.

A palindrome in every period #

The periods have more structure than repetition. For $\sqrt{61}$ the period is 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14. Leave off the last term and the rest reads the same backwards; the last term, 14, is twice the first whole part, 7. The same holds for $\sqrt{29}$, whose period 2, 1, 1, 2, 10 is a palindrome followed by twice 5, and for every $D$ up to 1,000, where the figure checked all 969 that are not squares.

The last term is explained by the state it returns to. The final state $(7, 1)$ has $Q = 1$, and its complete quotient is $7 + \sqrt{61}$, whose whole part is 14 and whose fractional part is $\sqrt{61} - 7$ — exactly where the expansion began after taking off its first 7. Twice the first term marks the moment the machine is back at its start.

The palindrome is explained by reversal. Running the expansion of $\sqrt D$ backwards corresponds to expanding $-1$ over the conjugate of each state, and for $\sqrt D$ the conjugates reproduce the same numbers in reverse order. So reading the period backwards is reading the same expansion from the other end, and the two readings must agree.

The states that repeat from the start #

Some quadratic irrationals repeat from their very first term, and the golden ratio, $[1; 1, 1, 1, \ldots]$, is the familiar case that the rectangle that eats itself builds. Évariste Galois proved in 1829, in his first published paper, exactly which ones: a quadratic irrational has a purely periodic expansion if and only if it is reduced — greater than 1, with its conjugate between $-1$ and 0.

The figure plots all 14 reduced states of discriminant 61 by their value and their conjugate, and all of them fall in that strip. The golden ratio is reduced too: it is about 1.618, and its conjugate is about $-0.618$. $\sqrt{61}$ is not, since its conjugate is $-\sqrt{61}$, far below the strip; that is why its expansion has a first term, 7, standing outside the period, and why every expansion of $\sqrt D$ has the shape $[a_0; \overline{a_1, \ldots, a_r}]$.

Reducedness does a second job in the proof of periodicity. A reduced state has only one possible predecessor that is also reduced, because the conjugate’s position in $(-1, 0)$ pins down the term that was taken. So the step is reversible on reduced states, and a reversible process on a finite set cannot have a tail leading into a cycle — every state lies on a cycle. That is why the expansion of $\sqrt D$ does not merely become periodic eventually, but repeats from its second term.

States the root never visits #

Because the step is reversible, the reduced states split into disjoint cycles, and the expansion of $\sqrt D$ is only one of them. For $D = 61$ the other three states — $(5, 6)$, $(7, 6)$ and $(7, 2)$ in the grid — form a cycle of their own: they are the complete quotients of numbers like $(7 + \sqrt{61})/6$, whose expansion never passes through $\sqrt{61}$'s states. For $D = 79$ there are three cycles, of 4, 6 and 6, and $\sqrt{79}$ uses only the cycle of 4. For $D = 46$ and $D = 94$ a single cycle holds every reduced state.

These cycles were not invented for continued fractions. Gauss organised the reduced indefinite quadratic forms — expressions $ax^2 + bxy + cy^2$ taking both positive and negative values, built from the same kind of whole-number data as the states here — into cycles of exactly this sort in 1801, and used them to sort forms into classes: two forms represent the same numbers under a change of variables when their reduced forms lie on the same cycle. The number of cycles is therefore closely tied to the number of classes of forms, and it is one of the routes by which the continued fraction of $\sqrt D$ is connected to the class numbers that the chakravala essay ended on.

The count matters for Pell’s equation directly. When $\sqrt D$’s cycle holds every state, a single cycle carries all the arithmetic of the discriminant; when it does not, the other cycles describe numbers of the form $a^2 - Db^2$ that $\sqrt D$’s own convergents never produce.

How long the period can be #

The counting argument gives a bound immediately: the period is at most the number of reduced states, and the band has room for no more than about $2D$ of them. That bound is honest and nearly useless. The actual periods up to 1,000 are much shorter, scattered below a ceiling that grows roughly like $\sqrt D$: the longest is 60, at $D = 919$, and none exceeds 1.98 times $\sqrt D$ in this range.

The scatter is wide. Next to $D = 919$ with its period of 60 sit values with periods of 1 or 2, such as $D = 920 = 30^2 + 20$ and $D = 960 = 31^2 - 1$, because $D$ one less than a square always has period 2: $\sqrt{n^2 - 1} = [n - 1; \overline{1, 2n - 2}]$. Nothing about the size of $D$ alone predicts the period. It is known that the period can never be much longer than $\sqrt D \log D$, a bound that comes from the same class number formula mentioned above, but which $D$ come close to it is irregular.

The odd periods, 152 of the 969, are the ones the Pell essay singled out: an odd period is exactly the condition for $x^2 - Dy^2 = -1$ to have a solution, and for the chakravala to pass through a miss of $-1$ on its way.

Where Pell’s equation sits on the cycle #

The cycle also shows where the solutions of Pell’s equation come from. At each state, the convergent reached so far, $p/q$, satisfies $p^2 - Dq^2 = \pm Q$ for the $Q$ of the next state, with the sign alternating. So the value of $p^2 - Dq^2$ along the convergents is the sequence of $Q$’s read off the cycle, with signs: for $\sqrt{61}$ the $Q$’s run 12, 3, 4, 9, 5, 5, 9, 4, 3, 12, 1, and the convergents’ values run $-12$, 3, $-4$, 9, $-5$, 5, $-9$, 4, $-3$, 12, $-1$.

A value of $\pm 1$ appears exactly where $Q = 1$, and within a period that happens only at the last state, $(7, 1)$. The solution of Pell’s equation is the state on the cycle whose $Q$ is 1, reached once per period. Whether it gives $+1$ or $-1$ depends on whether the period is even or odd: for $\sqrt{61}$, with period 11, the first return gives $-1$, and the second, 22 convergents in, gives $+1$ — the 22 that the chakravala essay compared its 13 steps against.

That also explains the palindrome’s use to anyone computing by hand. The $Q$’s along the cycle read the same backwards, just as the terms do, so the middle of the period already determines the whole; it is the same symmetry the chakravala’s sequence of misses displayed, seen here in the states rather than in the misses.

What periodicity buys #

A guarantee that searching ends. Both the continued-fraction walk and the chakravala are searches that stop when something returns to 1. Periodicity is what promises the return: the state that means “solved” is on the cycle, and the cycle is finite.

A certificate that a number is quadratic. Euler proved the converse of Lagrange’s theorem: any eventually periodic continued fraction is a quadratic irrational. So periodicity characterises exactly one class of numbers, and a long enough computed expansion that has visibly not repeated is evidence — though never proof — that a number is not quadratic.

And a finite description of an infinite object. The expansion of $\sqrt{61}$ is infinite, but eleven terms and a promise describe all of it, in the same way that the orbit written as a word describes a periodic orbit of a map by one repeating block. Continued fractions are themselves the orbits of a map — take the reciprocal of the fractional part — and the quadratic irrationals are exactly its eventually periodic points.

Every state listed, and Gauss’s forms only quoted #

Every state was enumerated, not argued about. The grid, the cycles and the reduced strip were computed by listing every pair in the band and following the step; the palindrome and the final term were checked for all 969 non-square $D$ up to 1,000. The reasons given — reversal for the palindrome, reversibility for pure periodicity — are the standard proofs, stated in words rather than drawn.

The correspondence with quadratic forms is described, not computed. That the cycles of reduced states match Gauss’s cycles of reduced forms, and count classes of forms, is quoted from the theory; no figure checks it against an independent count of classes.

And the period bound is observed up to 1,000. The ratio 1.98 is the largest in the range drawn; the theoretical bound of order $\sqrt D \log D$ is stated and not shown.

Still open: whether a cube root’s expansion stays small #

Quadratic irrationals are the numbers whose continued fractions repeat. For the next simplest numbers — roots of cubic equations, such as $\sqrt[3]{2}$, which begins $[1; 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, \ldots]$ — nothing comparable is known. It is not known whether the terms of the continued fraction of $\sqrt[3]{2}$ are bounded, or whether they grow without limit, although computations of millions of terms find the occasional very large one and suggest they behave like the terms of a randomly chosen number. For no algebraic number of degree three or more has anyone determined whether its terms are bounded.

Finite states, forced repetition #

The continued fraction of $\sqrt D$ repeats for the same reason a clock does: its state is a small amount of whole-number information, and there are only so many states it can be in. The states form cycles because the step can be run backwards, the period is a palindrome because running it backwards gives the same numbers, and the cycles that $\sqrt D$ does not visit are the other classes of forms of the same discriminant.

To prove that a process repeats, find what it remembers and show that it can only remember finitely much. The repetition then comes for free, and the structure of the finite set says far more than the repetition alone.