When minus one can be reached

Pell’s equation $x^2 - Dy^2 = 1$ has a solution for every $D$ that is not a square, and one solution that makes all the others showed that every solution is a power of the smallest. Change the $1$ on the right to $-1$ and the certainty goes. $x^2 - 2y^2 = -1$ is solved by $(1, 1)$, $x^2 - 13y^2 = -1$ by $(18, 5)$, and $x^2 - 61y^2 = -1$ by $(29718, 3805)$. But $x^2 - 3y^2 = -1$ has no solution at all, and neither has $x^2 - 34y^2 = -1$.

The essay that set up the equation closed on this difference and said that deciding which $D$ reach $-1$ “is not elementary and is still not fully understood”. This essay follows that remark to its end. The answer comes in layers. The first layer is a remainder, and it rules out most $D$ outright. The second is a theorem of Legendre’s, and it settles every prime. The third needs the symbols of quadratic reciprocity and then their fourth-power cousins. And under all of them sits a question about how often, which was open for thirty years and was answered by a proof announced in 2022.

A solution of the negative equation is worth having when it exists, because it is half of a solution of the positive one. If $x^2 - Dy^2 = -1$ then squaring $x + y\sqrt D$ gives a number whose norm is $(-1)^2 = 1$: from $(29718, 3805)$ comes $x = 2 \cdot 29718^2 + 1 = 1{,}766{,}319{,}049$, which is Fermat’s famous answer for 61 that sixty needs two digits and sixty-one needs ten measured. So the question is also a question about whether the smallest solution of Pell’s equation is a perfect square in disguise.

Two reasons it can fail, both visible from a remainder #

Two obstructions are local: each can be seen by reducing the equation modulo a single number.

The first is modulo 4. A square leaves remainder 0 or 1 on division by 4, so $x^2 + 1$ leaves 1 or 2. If $4$ divides $D$ then $Dy^2$ leaves 0, and $x^2 + 1 = Dy^2$ cannot hold. No search is needed.

The second is modulo a prime. If $p$ divides $D$, the equation says $x^2 \equiv -1 \pmod p$, so $-1$ must be a square modulo $p$. For an odd prime that happens exactly when $p$ leaves remainder 1 on division by 4 — the same condition that decides which primes a form takes when the form is $x^2 + y^2$ — and it is the first of the two supplements to quadratic reciprocity, and it follows from Euler’s criterion: $-1$ is a square modulo $p$ when $(-1)^{(p-1)/2} = 1$. So any prime of the form $4k + 3$ dividing $D$ blocks the equation. $3$, $6$, $7$, $11$, $12$, $14$, $15$, $19$, $21$ and $22$ all fall to one of these two tests.

The grid sorts all 399 values of $D$ from 2 to 400. Nineteen are squares. Of the rest, 302 are blocked by one of the two remainders, 69 are solvable, and 9 are neither: nothing modulo any single number forbids a solution, and still there is none. Those nine are $34$, $146$, $178$, $194$, $205$, $221$, $305$, $377$ and $386$.

The picture is lopsided in a way that matters later. The obstructions are common: most numbers have some prime factor of the form $4k + 3$, and a quarter are divisible by 4. What is left is thin — a set of $D$ whose density among all numbers tends to zero, since having no prime factor of the form $4k + 3$ is a condition that becomes rarer the more factors a number has. The whole interesting question lives inside that thin set. Up to 400, 78 values of $D$ escape both obstructions, and 69 of them are solvable.

The test used to decide solvability is the one from the equation’s first essay: $x^2 - Dy^2 = -1$ has a solution exactly when the continued fraction of $\sqrt D$ has an odd period. Why the expansion has to repeat explained the period; its parity is the switch. After one full period the convergent $p/q$ satisfies $p^2 - Dq^2 = (-1)^\ell$, where $\ell$ is the period’s length, so an odd period hands over a solution of the negative equation on the spot and an even one never does. That turns a search with no bound into a finite computation, and the grid is the output of 399 such computations.

Every prime of the form 4k + 1 gets there #

For a prime $D = p$, the two obstructions leave only the primes that are 1 more than a multiple of 4, and Legendre proved in 1785 that all of them are solvable. The argument uses nothing but the positive equation and the fact that its smallest solution is the smallest.

Let $(x, y)$ be the smallest solution of $x^2 - py^2 = 1$. Then $x$ is odd: if it were even, $x^2 - 1$ would leave remainder 3 on division by 4, while $py^2$ with $p \equiv 1$ leaves 0 or 1. So $x - 1$ and $x + 1$ are consecutive even numbers, and writing $x - 1 = 2u$ and $x + 1 = 2v$ gives two consecutive whole numbers $u$ and $v = u + 1$, with no common factor, whose product $uv$ is $p$ times a square. Two coprime numbers whose product is $p$ times a square must be a square and $p$ times a square, in one order or the other.

If $u = pb^2$ and $v = a^2$, then $a^2 - pb^2 = v - u = 1$, and $a$ is far smaller than $x$ — contradicting the choice of the smallest solution. So the other order holds: $u = a^2$ and $v = pb^2$, and then $a^2 - pb^2 = u - v = -1$. The negative equation is solved, and its solution was hidden inside the positive one’s.

The figure checks the theorem on every prime up to 3,000, and it shows what the theorem does not say. The period’s parity is fixed by the residue of $p$ modulo 4, but the period’s length is not fixed by anything visible: primes of similar size have periods of 1 and of 80. The length is what sixty needs two digits and sixty-one needs ten tied to the size of the solution, and it is wild. The parity is tame. One quantity can be controlled completely while another quantity computed from the same expansion cannot be controlled at all.

The primes of the form $4k + 3$ are the other half of the same picture, and every one of them has an even period, as the modulo-4 argument says it must. Between them the two families account for every prime, which is why primes are the easy case.

Thirty-four, which passes every test and still fails #

The first $D$ in the grid that is neither blocked nor solvable is 34. Its prime factors are 2 and 17, and 17 is 1 more than a multiple of 4, so $-1$ is a square modulo 17 ($4^2 = 16 \equiv -1$) and modulo 2. No remainder rules it out.

Something stronger is true: the equation has a solution in fractions. $34 = 3^2 + 5^2$, and dividing by $25$ gives $(3/5)^2 - 34 \cdot (1/5)^2 = -1$. In general $x^2 - Dy^2 = -1$ can be solved in rational numbers exactly when $D$ is a sum of two squares, which is the same as saying that no prime of the form $4k + 3$ divides it to an odd power — the fact two squares, and a lattice proves for primes. So on the thin set every $D$ has a rational solution, and the question is purely whether a whole-number one exists. For 34 it does not.

The convergents show it directly. The period of $\sqrt{34}$ is $1, 4, 1, 10$, four terms, and the values $p^2 - 34q^2$ at the convergents cycle through $-9, 2, -9, 1$. The equation comes within $-9$ of the target and then turns back. Every solution of $x^2 - 34y^2 = -1$ would have to appear among these convergents, because any fraction $x/y$ that close to $\sqrt{34}$ is one, and they never produce it.

The rational solution explains the near miss: $3^2 - 34 \cdot 1^2 = -25$, a square times $-1$, and $5^2 - 34 = -9$, again a square times $-1$. The equation keeps reaching $-1$ multiplied by a square and cannot shed the square. The reason lives in the ring $\mathbb{Z}[\sqrt{34}]$. The ideal generated by $3 + \sqrt{34}$ is the square of an ideal of norm 5, and that ideal is not generated by any single number: if it were generated by some $\alpha$, then $(3 + \sqrt{34})/\alpha^2$ would be a whole-number solution of the negative equation. That is a fact about the class group, the object two families of solutions, and a box met when it counted families, and no remainder modulo a single number sees it.

Two primes, and a rule that looks one level deeper #

Legendre’s argument for primes almost works for a product of two. Take $D = pq$ with $p$ and $q$ both of the form $4k + 1$, and the smallest solution $(x, y)$ of the positive equation. As before $x$ is odd and $u = (x-1)/2$, $v = (x+1)/2$ are coprime with product $pq$ times a square. Now there are four ways to split: $\{a^2, pqb^2\}$ in either order, or $\{pa^2, qb^2\}$ in either order.

Two of the four are the prime case again: one gives a smaller solution of the positive equation, which is impossible, and the other gives $a^2 - pqb^2 = -1$. The two new cases give $pa^2 - qb^2 = \pm 1$. Reduce either modulo $q$: it says $pa^2 \equiv \pm 1$, so $p$ is a square modulo $q$, since $-1$ is one. If $p$ is not a square modulo $q$, both new cases are impossible, and the negative equation has a solution. That is the result the Legendre symbol $\left(\frac{p}{q}\right) = -1$ decides, and because both primes are of the form $4k + 1$, reciprocity — which counting one rectangle, twice proves by counting lattice points — makes the condition symmetric: $p$ is a square modulo $q$ exactly when $q$ is a square modulo $p$.

When $p$ is a square modulo $q$, the argument stops, and the answer really does depend on more. Arnold Scholz found in 1934 what it depends on: whether each prime is a fourth power modulo the other. When one is and the other is not, the equation has no solution. When neither is, it always does. And when both are, the fourth powers do not decide it.

The figure sorts all 714 such products up to 20,000, and the four groups behave exactly as the two rules predict. Three of them are uniform — 370 of 370, 0 of 183, 88 of 88 — and the fourth is mixed, 25 of 73. Below that fourth group the arithmetic goes on: eighth powers, and then a tower of finer symbols that László Rédei began to study in the 1930s. Each layer decides some cases and hands the rest to the next.

The same shape appears when 2 is one of the primes. For $D = 2p$, the question is whether 2 is a square modulo $p$, and the second supplement says that happens exactly when $p$ leaves 1 or 7 on division by 8. Among primes $p$ of the form $4k + 1$ below 5,000, every one that leaves 5 on division by 8 gives a solvable $2p$ — 168 of 168 — while among those that leave 1, only 54 of 161 do. 34 is $2 \cdot 17$, and 17 leaves 1.

Most numbers with no obstruction have few prime factors #

The prime case is certain, the two-prime case is decided by a coin that lands two ways out of three, and more factors mean more layers. That is why the answer to “how often” depends so heavily on how many prime factors a typical $D$ has.

Up to a million there are 124,490 squarefree $D$ in the thin set. Almost a third of them — 39,176 — are primes or $2$, and every one of those is solvable. Of the 55,163 with two prime factors, 66.7% are solvable. Three factors give 71.7%, four give 67.4%, five give 66.3%, and there are only 172 numbers with five. Six is not reached at all before a million.

The shares do not fall in a straight line: three factors do better than two. But the drift away from certainty is clear, and it is driven by the composition of the set. A typical number up to $X$ has about $\ln \ln X$ prime factors, and in the thin set about half that, because each prime has to be of the form $4k + 1$. At a million, $\ln \ln X$ is about 2.6 — so the thin set is dominated by numbers with one or two prime factors, exactly the cases in which a solution is most likely.

A limit reached at the pace of log log #

In 1993 Peter Stevenhagen proposed a model of the part of the class group made from elements whose order is a power of 2, and from it a precise prediction: among $D$ in the thin set, the share for which $x^2 - Dy^2 = -1$ is solvable tends to

$$1 - \prod_{j \text{ odd}} \left(1 - 2^{-j}\right) \approx 0.5806.$$

The product runs over $j = 1, 3, 5, \ldots$ and converges quickly: the first factor alone is $\tfrac12$, the first two give $0.4375$, and a few more settle it at $0.4194$. Étienne Fouvry and Jürgen Klüners proved in 2010 that the true share, whatever it is, eventually lies between about 52.4% and 66.7%. In 2022 Peter Koymans and Carlo Pagano proved that the limit exists and is exactly Stevenhagen’s number.

The computed share is nowhere near it. At a thousand it is 84.7%, at ten thousand 82.4%, at a hundred thousand 79.8%, and at a million 78.2%. The curve is falling, and it is falling towards the dashed line, but on a scale where every step to the right multiplies $X$ by ten it has covered about a quarter of the distance.

The previous section is the reason. The share is a weighted average of the per-factor shares, weighted by how many $D$ have each number of factors, and those weights shift only as fast as $\ln \ln X$ grows. To get a typical member of the thin set up to five or six prime factors, $\ln \ln X$ would need to reach ten or so, which puts $X$ beyond $e^{e^{10}}$, a number with nearly ten thousand digits. No computation will ever show this curve arriving. The limit is a theorem about numbers no one will write down, and the data at every size anyone can reach says something else.

That is not a flaw in the theorem or in the data. It is a warning about what data from small cases can say when the quantity that governs the behaviour grows like $\ln \ln X$. A reader who plotted this curve and extrapolated would guess a limit near 70%, and would be wrong by twelve points about a question that was, for thirty years, open.

Still open: whether p ever divides the answer #

For a prime $p$ of the form $4k + 1$, Legendre’s theorem guarantees the negative equation a solution $(x, y)$, and the smallest one can be enormous: below 100,000, one needs an $x$ with 362 digits. In 1952 Nesmith Ankeny, Emil Artin and Sarvadaman Chowla conjectured something small about it — that $p$ never divides $y$. Put another way, the solution is never secretly $p$ times something simpler.

There is a reason to care beyond the curiosity. The three proved a congruence tying the smallest solution to the class number of $\mathbb{Q}(\sqrt p)$ and to the Bernoulli number $B_{(p-1)/2}$, and through it the conjecture is equivalent to $p$ not dividing the numerator of that Bernoulli number — a statement about a sequence defined with no reference to Pell’s equation at all. For every prime of the form $4k + 1$ below 100,000 — 4,783 of them — the solution computed from the continued fraction of $\sqrt p$ has $y$ not divisible by $p$. The conjecture has been checked by others far beyond that, past $10^{11}$.

No proof is known, and the heuristic points the other way. If $y$ behaved like a random number, it would be divisible by $p$ with probability about $1/p$, and the sum of $1/p$ over primes diverges. So a random model predicts infinitely many exceptions, spaced so sparsely that the first might lie far beyond any computation. Whether the conjecture is true, and the model is missing some structure, or false, with its counterexamples out of reach, is unknown. It is the same situation as the density curve above: an answer that the numbers anyone can compute do not decide.

What the pictures do not settle #

Each figure is a finite check. The grid tests the parity of 399 periods, the primes figure 429, the two-prime figure 714 products, and the density curve 124,490 values of $D$. Legendre’s theorem and the two-prime argument are proved above, not just tested; Scholz’s rule, the rational-solution criterion and the limit theorem are quoted, and the figures are consistent with them on every case drawn.

The period-parity test itself rests on another theorem of Legendre’s: every fraction close enough to $\sqrt D$ to satisfy $x^2 - Dy^2 = \pm 1$ is a convergent, so a search through one period sees every candidate. The convergents shown for 34 therefore settle 34; they do not illustrate a pattern, they exhaust the possibilities.

Which $D$ in the thin set fail is decided by structure that no finite list of remainders captures. The first layer uses squares, the next fourth powers, the next eighth powers, and every layer leaves a remainder of cases for the next. What the 2022 proof shows is that averaged over all $D$ this infinite tower has a well-defined result, and that the result is Stevenhagen’s 58%. A single $D$ can still need an arbitrary number of layers to decide, and the continued fraction, which decides it in a few steps, gives no hint of which layer did the work.