One solution that makes all the others

Find whole numbers $x$ and $y$ with $x^2 - 2y^2 = 1$. There is the trivial answer $x = 1$, $y = 0$, and after a little searching there is $3^2 - 2\cdot 2^2 = 9 - 8 = 1$.

That second solution is worth more than it looks, because it manufactures the rest.

The multiplication #

Take two solutions $(x, y)$ and $(x', y')$ and combine them by

$$(x, y) \cdot (x', y') = (xx' + 2yy',\; xy' + x'y).$$

That looks arbitrary until it is read the right way. Consider $x + y\sqrt 2$ and $x' + y'\sqrt 2$, and multiply them:

$$(x + y\sqrt2)(x' + y'\sqrt2) = xx' + 2yy' + (xy' + x'y)\sqrt2.$$

The rule is ordinary multiplication of numbers of the form $a + b\sqrt 2$, with the $\sqrt2$ terms collected. And the equation $x^2 - 2y^2 = 1$ says exactly that $(x + y\sqrt2)(x - y\sqrt2) = 1$ — so a solution is a number of that form whose product with its conjugate is one.

Products of such numbers are again such numbers, and conjugation respects multiplication, so the product of two solutions is a solution. That is the whole verification, and it is why the multiplication is not arbitrary: it is the only multiplication there was.

Applying it repeatedly to $(3,2)$ gives $(17,12)$, then $(99,70)$, then $(577, 408)$, each one $3 + 2\sqrt2$ raised to a higher power. The solutions form a group, generated by one element together with the sign changes, and the theorem is that there are no others.

Why there are infinitely many #

The existence of one non-trivial solution is the hard part, and the standard proof is a pigeonhole argument that will already be familiar.

How close a fraction can get proves Dirichlet’s theorem: for any irrational $\alpha$ there are infinitely many fractions $p/q$ with $|\alpha - p/q| < 1/q^2$. Apply it to $\sqrt D$. Then $|p - q\sqrt D| < 1/q$, and multiplying by $|p + q\sqrt D| < 2q\sqrt D + 1$ gives

$$|p^2 - Dq^2| < 2\sqrt D + 1.$$

So infinitely many pairs $(p,q)$ give a value of $p^2 - Dq^2$ inside a fixed bounded range. Only finitely many whole numbers are in that range, so some value $k$ is hit infinitely often — pigeonhole again. Among those infinitely many pairs, two agree in both $p \bmod k$ and $q \bmod k$, and dividing one by the other in the $\sqrt D$ sense produces a solution with $k$ cancelled: a genuine solution of $x^2 - Dy^2 = 1$.

Every step is a counting argument and none of them exhibits anything. The proof establishes that a solution exists without giving the least hint of how large it is — which turns out to be the honest state of affairs, because the size is wild.

Finding the smallest one #

Searching for the fundamental solution by trying every $y$ works and stops working quickly. There is a better route, and it goes through the continued fraction of $\sqrt D$.

The connection is a theorem: every solution of $x^2 - Dy^2 = 1$ has $x/y$ a convergent of the continued fraction of $\sqrt D$. The reason is that a solution makes $x/y$ an extremely good rational approximation to $\sqrt D$ — from $x^2 - Dy^2 = 1$,

$$\left|\frac{x}{y} - \sqrt D\right| = \frac{1}{y^2\left(\frac{x}{y} + \sqrt D\right)} < \frac{1}{2y^2},$$

and a rational within $1/2y^2$ of a number is one of its convergents. So the search can run down the convergents instead of down the whole numbers, and there are far fewer of them.

Which convergent it is depends on the period of the expansion. The continued fraction of $\sqrt D$ is always eventually periodic — that is Lagrange’s theorem, and it holds for every quadratic irrational — and the fundamental solution appears at the end of the first or the second period, according as the period is even or odd.

How large the first solution can be #

For $D = 2$ the answer is $(3, 2)$. For $D = 3$ it is $(2,1)$. For $D = 13$ it is $(649, 180)$.

For $D = 61$ the fundamental solution is

$$1\,766\,319\,049^2 - 61 \cdot 226\,153\,980^2 = 1,$$

which is why the equation is not a small thing to solve by search. There is no formula for the size, it does not grow with $D$ in any regular way — $D = 60$ has the solution $(31, 4)$ — and the record-holders for size are related to the class numbers of quadratic fields, which are themselves famously irregular.

Fermat posed the $D = 61$ case as a challenge to English mathematicians in 1657, and it is generally agreed that he chose 61 precisely because the answer is large. Brouncker and Wallis found it; whether they had a general method or a great deal of persistence was disputed at the time.

The same picture, as a motion of the plane #

There is a geometric reading of the multiplication that explains why the solutions thin out the way they do.

The map $(x,y) \mapsto (3x + 4y,\; 2x + 3y)$ — which is multiplication by $(3,2)$ written out — is a linear map of the plane. It has determinant $9 - 8 = 1$, so it preserves area, and it carries the hyperbola $x^2 - 2y^2 = 1$ to itself, because it carries solutions to solutions and the same algebra works for non-whole $x$ and $y$.

A linear map preserving a hyperbola and area is a shear along the hyperbola: it slides every point along the curve, by a fixed amount of hyperbolic angle. So the solutions are the orbit of $(1,0)$ under a rigid sliding, equally spaced in the hyperbola’s own natural parameter — and unequally spaced, exponentially, in ordinary coordinates.

That is why the picture looks the way it does. The points are evenly distributed by the curve’s own measure, and the curve’s own measure runs off to infinity logarithmically, so a drawing in $x$ and $y$ crushes the early points together and pushes the later ones off the page.

The same reading gives the group structure for nothing. The solutions are the orbit of one point under a map, and the maps form a group under composition isomorphic to the whole numbers, so the solutions are indexed by the whole numbers — which is the theorem that every solution is a power of the fundamental one, stated as a fact about a group action.

Asking for a different constant #

Replace 1 on the right by another whole number $N$ and the question changes character. $x^2 - 2y^2 = 7$ has solutions $(3,1)$ and $(5,3)$; $x^2 - 2y^2 = 5$ has none; $x^2 - 2y^2 = -1$ has $(1,1)$.

Two things happen at once. First, solutions may not exist, and the obstruction is often a congruence: modulo 8, $x^2 - 2y^2$ can be 0, 1, 2, 4, 6 or 7 but never 5, so $N = 5$ is impossible without any search. Second, when solutions do exist they come in several families rather than one, each family being the orbit of one solution under multiplication by the fundamental unit.

So the general problem has two halves: decide whether any solution exists, and find one representative of each family. The first is a finite check modulo a suitable number together with a bound; the second is a finite search, because every family has a representative with $y$ below a bound depending on $N$ and the fundamental solution.

That the expansion of $\sqrt2$ repeats immediately is the reason its fundamental solution is small. The period is the number of convergents that must be walked before the value $p^2 - Dq^2$ returns to $\pm1$, and a long period means a long walk and correspondingly enormous numerators. $\sqrt{61}$ has period 11, and its fundamental solution has ten digits.

What the solutions are, in another language #

The set $\{a + b\sqrt D : a, b \text{ whole}\}$ is closed under addition and multiplication, and a solution of Pell’s equation is an element of it whose product with its conjugate is 1 — a unit, in the language of rings: an element with a multiplicative inverse inside the set.

Read that way, the theorem that all solutions are powers of one becomes a statement about the structure of the unit group: it is infinite cyclic, together with $\pm 1$. Dirichlet proved a far more general version — for the integers of any number field, the units form a finitely generated group whose rank is determined by how many real and complex embeddings the field has — and Pell’s equation is the simplest non-trivial case of it.

That is the reason the equation survived being solved. It is not interesting because hyperbolas have lattice points on them; it is interesting because it is the visible face of a structure that appears throughout algebraic number theory, and the fundamental solution is a fundamental unit, a quantity that shows up in class number formulas and regulators.

Every fraction exactly once builds the tree that the convergents walk down, and One way to factor, and no other sets out unique factorisation for whole numbers. In rings like $\mathbb{Z}[\sqrt D]$ that property often fails, and the units are one of the two things that have to be understood before anything can be said about factorisation at all — the other being the class group.

The negative equation, which sometimes has no solutions #

Ask instead for $x^2 - Dy^2 = -1$. For $D = 2$ there is $(1,1)$; for $D = 13$ there is $(18, 5)$; for $D = 3$ there is nothing at all.

The obstruction is visible modulo 4. If $x^2 - 3y^2 = -1$ then $x^2 + 1 \equiv 3y^2$, and squares are 0 or 1 mod 4, so the left side is 1 or 2 and the right is 0 or 3. No solution, and none needs to be searched for.

More generally the negative equation is solvable exactly when the continued fraction of $\sqrt D$ has odd period — which is the pattern visible in the two tables above: $\sqrt 2$ has period 1 and its convergents hit $-1$; $\sqrt 7$ has period 4 and they never do. Deciding which $D$ have odd period is not elementary and is still not fully understood; the density of such $D$ among those with no obvious obstruction was conjectured by Stevenhagen and proved only in 2022.

So the positive equation always has solutions and the negative one sometimes does, and the difference between “always” and “sometimes” is one of the places where this corner of number theory stops being tidy.

Where the name came from, and why it is wrong #

The equation is not Pell’s. John Pell had nothing to do with it; Euler attributed it to him in 1730 through a misreading of a book by Wallis, where Pell’s name appears in connection with a different method, and the misattribution stuck.

The genuine history runs the other way round the world. Brahmagupta solved cases in 628 and stated the composition identity — the multiplication above — in general, calling it samasa. Bhāskara II gave a complete method, the chakravala, in 1150, which finds the fundamental solution for $D = 61$ in a handful of steps and is more efficient than the continued-fraction method Europeans arrived at six centuries later. Lagrange gave the first proof that a solution always exists, in 1768.

The chakravala’s key idea is worth stating because it is not the obvious one: rather than working only with solutions of $x^2 - Dy^2 = 1$, it works with solutions of $x^2 - Dy^2 = k$ for small $k$ and composes them, dividing out $k$ when it can. Allowing the intermediate steps to miss the target is what makes the method fast, and it is exactly the move the pigeonhole proof makes as well.

What the pictures cannot show #

The hyperbola figures draw three or four solutions and the fourth is already off the useful part of the page — the points thin out exponentially, since each is about $(3+2\sqrt2) \approx 5.83$ times the last for $D = 2$. Any drawing showing five solutions at once shows the first four crushed against the origin.

The exhaustive check that no solution has been missed runs up to the largest $y$ drawn, so it is a genuine check over a finite range and not a proof. The theorem that every solution is a power of the fundamental one is quoted rather than established here.

And the convergent tables stop after eight or eleven terms. The continued fraction of $\sqrt D$ is infinite and periodic; a table shows one or two periods and asserts that the state has repeated, which is what the periodicity claim rests on — the recurrence’s state is a pair of whole numbers, and a repeated state means everything after repeats too.

The ladder from here #

Below: a fraction that never closes, which builds continued fractions and their convergents, and the square that cannot shrink, which is why $\sqrt 2$ is irrational and the expansion never terminates. Sideways: how close a fraction can get, the approximation theorem the existence proof runs on; two squares and a lattice, a different equation whose solutions are read off a lattice; and a tree that holds every triple, where the solutions of another equation are generated from one by a rule. Above: the chakravala method, Lagrange’s theorem on periodic continued fractions, Dirichlet’s unit theorem, and the connection between fundamental units and class numbers.

What is worth carrying away #

An equation with infinitely many solutions is usually described by a parametrisation. This one is described by a generator: one solution, and a rule for combining solutions, and everything follows.

The rule was not invented for the purpose. It is multiplication in $\mathbb{Z}[\sqrt D]$, which was already there, and the equation is the condition for an element to be invertible. When a set of solutions turns out to be closed under an operation, the operation was almost never designed for them — it was already present in whatever the solutions really are, and finding it is the same as finding out what they really are.