Euler's sixty-five convenient numbers

Fermat’s theorem on sums of two squares says that an odd prime is $x^2 + y^2$ exactly when it leaves remainder 1 on division by four, and two squares and a lattice showed why: a fact about circles is settled by a fact about remainders. Fermat and Euler found the same kind of rule for $x^2 + 2y^2$ (remainder 1 or 3 mod 8) and $x^2 + 3y^2$ (remainder 1 mod 3), and Euler went looking for more.

He found that the pattern holds for some $n$ and fails for others. For $x^2 + 5y^2$ a prime is represented exactly when it leaves remainder 1 or 9 on division by 20. For $x^2 + 14y^2$ no rule of that kind exists: primes with the same remainder mod 56 are sometimes represented and sometimes not, and a remainder can never settle the question. Euler called the good values of $n$ numeri idonei — suitable, or convenient numbers — because they were convenient for something he cared about more than the rule itself: proving that large numbers are prime.

He found sixty-five of them, the largest $1{,}848$, searched well beyond, and found no more. The question left open at the end of the essay that counted classes is whether there are others. This essay computes the list from the modern description of what makes a number convenient, shows what the convenience is and what Euler did with it, and explains why the list is almost certainly complete and why nobody can prove it.

Sixty-five points on the powers of two #

The modern description comes from Gauss. Counting the classes that break factorisation reduced every quadratic form $ax^2 + bxy + cy^2$ of a given discriminant to a unique smallest representative and counted the reduced ones: the class number. For $x^2 + ny^2$ the discriminant is $-4n$. The classes form a group under Dirichlet’s composition, and they are sorted into genera: two forms are in the same genus when they take the same values modulo every number, so that no remainder can tell them apart.

The number of genera is always a power of two, set by the prime factors of $n$. When each genus holds exactly one class, a prime’s remainders determine which genus represents it and therefore which form does — and that is Euler’s convenience. Gauss’s genus theory then shows it happens exactly when every element of the class group has order one or two. The idoneal numbers are the $n$ for which the class group of discriminant $-4n$ is a product of groups of order two.

The figure applies that test to every $n$ up to 2,000 and recovers Euler’s list exactly: sixty-five numbers, beginning 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16 and ending 1,320, 1,365, 1,848. Their class numbers are 1, 2, 4, 8 or 16 and nothing else. Every other $n$ has a class of order at least three somewhere, and above about 1,000 the class numbers of the non-idoneal $n$ fill the band far above the level the genera allow.

What a remainder can see #

The smallest example shows the mechanism. For $n = 5$ there are two reduced forms of discriminant $-20$, $x^2 + 5y^2$ and $2x^2 + 2xy + 3y^2$, and they are the reason six factors two ways among the numbers $a + b\sqrt{-5}$. Look at the values each can take modulo 20. Among primes, the first takes only those leaving remainder 1 or 9. The second takes primes leaving 3 or 7. No odd prime is taken by both, and a prime leaving 11, 13, 17 or 19 is taken by neither.

That separation is what a genus is. Gauss attached to each form a list of signs, its characters, computed from the remainders of the numbers it represents — here, whether those numbers are squares modulo 5 and whether they leave 1 or 3 on division by 4. Two forms with the same characters are in the same genus and take primes with the same remainders; forms with different characters take disjoint sets of remainders. The number of possible character lists is a power of two, one sign per prime factor of the discriminant, give or take one, and exactly half of them occur — which is where the number of genera comes from.

When a genus holds a single form, its characters pick it out, and a prime’s remainder picks out the form that takes it. When a genus holds several forms, they share their characters, they take primes with the same remainders, and the remainders stop there. The hidden structure that a factorisation that hides its primes found in the numbers one more than a multiple of four has the same origin: a system of values that remainders can see only in part.

What an ambiguous form looks like #

The test is easy to run on reduced forms. The inverse of a class is the class of the form with $b$ negated, so a class has order one or two exactly when its reduced form equals its own mirror image — which for reduced forms happens when $b = 0$, or when $b = a$ or $a = c$, the boundary cases where the mirror image reduces back to the form itself. A class group in which every element is its own inverse is exactly a class group whose reduced forms are all ambiguous.

For $n = 1{,}848$ there are sixteen reduced forms, from $x^2 + 1848y^2$ to $47x^2 + 38xy + 47y^2$, and every one is ambiguous: nine with $b = 0$, five with $b = a$, two with $a = c$. The group has sixteen elements of order at most two, and $1{,}848 = 2^3 \cdot 3 \cdot 7 \cdot 11$ has enough prime factors to make sixteen genera — one class each. For $n = 14$ there are four reduced forms and only two genera. The principal form $x^2 + 14y^2$ shares its genus with the mirror pair $3x^2 \pm 2xy + 5y^2$, whose classes have order four, and a remainder cannot say which of them takes a given prime.

Remainders that decide, and remainders that do not #

The convenience can be seen directly in the primes. For $n = 10$, an idoneal number, the primes up to 20,000 fall into sixteen groups by their remainder mod 40, and the form $x^2 + 10y^2$ takes either every prime in a group or none: exactly those leaving remainder 1, 9, 11 or 19. For $n = 11$, with class number three, the form $x^2 + 11y^2$ takes some of the primes with a given remainder and not others, in ten of the twenty groups. The other two forms of discriminant $-44$, $3x^2 \pm 2xy + 4y^2$, take the rest of those groups’ primes, and no congruence separates them.

What decides the split groups is a finer invariant than a remainder. For $x^2 + 27y^2$, for instance, Gauss proved that a prime $p$ is represented exactly when $p$ leaves remainder 1 on division by 3 and 2 is a cube modulo $p$ — a condition about cube roots in arithmetic modulo $p$, not about the remainder of $p$ itself. The general answer, for every $n$, is class field theory: a prime is represented by $x^2 + ny^2$ exactly when it splits completely in a certain field built from $n$, and for idoneal $n$ that field is small enough that splitting is a matter of remainders. The idoneal numbers are exactly where the question has a schoolroom answer.

What Euler did with 1,848 #

Euler’s use for the convenient numbers was a primality test. For an idoneal $n$ and an odd number $N$ sharing no factor with $n$: if $N$ can be written as $x^2 + ny^2$ in exactly one way with $x, y \ge 0$, and in that way $x$ and $ny$ share no factor, then $N$ is prime. Conversely a prime that the form takes at all, it takes exactly once. The test works because for an idoneal $n$ a composite number built from represented primes is represented in several ways — one for each way of combining its prime factors’ representations — and only a prime has a single one. The combining is an identity of the kind that multiplies sums of squares: $(a^2 + nb^2)(c^2 + nd^2) = (ac - nbd)^2 + n(ad + bc)^2 = (ac + nbd)^2 + n(ad - bc)^2$, two representations of the product from one of each factor, and they are genuinely different unless something degenerates.

Euler applied it with $n = 1{,}848$ to $18{,}518{,}809 = 197^2 + 1848 \cdot 100^2$. Checking every $y$ from 0 to 100 shows no other representation, so the number is prime. It was a large prime to certify by hand, and the certification needed only a hundred square-root tests rather than trial division by the thousand-odd primes below $\sqrt{18{,}518{,}809} \approx 4{,}303$. The larger the idoneal number, the fewer values of $y$ to check, which is why Euler wanted large ones.

The figure’s other lines show the test’s limits. A prime that the form does not take, like $18{,}518{,}813$, gets no verdict. A single representation in which the two terms share a factor, as $3703^2 + 1848 \cdot 51^2$ does through the prime 7, proves nothing, and that number is $7 \times 2{,}645{,}551$. Two representations prove the number composite, and $18{,}519{,}601$ has two.

A test that applies to few numbers #

The price of a large idoneal number is that the test applies to fewer numbers. Among all primes, the share that $x^2 + ny^2$ takes is $1/(2h)$, where $h$ is the class number: the primes that split are half of all primes, and they are shared equally among the $h$ classes. For $n = 5$ that is a quarter of the primes; for $n = 1{,}848$, with sixteen classes, it is one prime in thirty-two. A number chosen to be tested has to be one the form takes, and Euler chose $18{,}518{,}809$ by starting from the form — choosing $x$ and $y$ and checking whether the result was prime — rather than starting from the number.

That is still how the method is used, when it is used: to certify primes of a special shape, built from the representation, rather than to test arbitrary numbers. For arbitrary numbers, tests built on Fermat’s theorem — and certificates like an order that proves a prime — are faster by far. What the idoneal numbers offered in Euler’s century was a certificate: a single representation, which anyone could check with a table of squares, standing in for trial division by thousands of primes.

Sixty-five, and then none #

Running the test further shows nothing new: no idoneal number between 1,849 and 40,000, and far larger searches have found nothing either. The reason more are not expected is visible in the first figure. The number of genera of discriminant $-4n$ is $2^{t}$ or $2^{t-1}$, where $t$ counts the prime factors of $n$ with a small correction at 2, and $t$ grows extremely slowly — a number below a million has at most seven distinct prime factors. The class number grows like $\sqrt n$. For the classes to fit one to a genus, $\sqrt n$ must not outgrow $2^t$, and past a certain point it always does.

Sarvadaman Chowla proved in 1934 that there are only finitely many idoneal numbers, by making that argument rigorous. But his proof rests on Siegel’s theorem that the class number grows at least like $n^{1/2 - \varepsilon}$, and Siegel’s theorem has a notorious defect: it proves the growth without saying from where it starts. The constant involved cannot be computed, because the proof works by contradiction from a hypothetical zero of a certain function near 1, a zero that may or may not exist.

Peter Weinberger pushed the argument as far as it goes in 1973. At most one idoneal number exists beyond Euler’s list, and none if the generalised Riemann hypothesis holds. The single possible exception is the trace of that hypothetical zero: if it exists, it could produce one more convenient number, far beyond every search, and the search can never rule it out because no computable bound says where it would lie.

Why the class group must be so small #

The idoneal numbers are also a statement about class groups in general, and the figure’s picture of it is worth stating. Class groups of imaginary quadratic discriminants are, for large discriminants, big and varied: their size grows like $\sqrt{|D|}$, and their structure includes elements of order three, five, and every other size. A class group in which every element has order two is a very special group — as special as class number one, which the nine fields of unique factorisation have and which stops at discriminant $-163$.

Idoneal numbers are the natural next case of the same finiteness. Class number one means the group is trivial; idoneal means the group is as small as its genus structure allows. Both lists are finite for the same reason, both were found by hand long before they could be proved finite, and for class number one the last exception was ruled out by Kurt Heegner, Harold Stark and Alan Baker around 1967, with methods specific to that problem. No comparable method has closed the idoneal list.

What the search cannot show #

The figures compute the idoneal numbers from their definition — every reduced form of discriminant $-4n$ ambiguous — for every $n$ up to 40,000, and compare the result with Euler’s list as he published it. That the two agree is a confirmation of Gauss’s theory as much as of Euler’s search.

The search says nothing about $n$ beyond its bound. Weinberger’s theorem is what limits the possible exceptions to one, and the generalised Riemann hypothesis is what would remove it. The number 40,000 in the last figure is an illustration of the flatness, not a contribution to the evidence: searches that matter have gone many orders of magnitude further.

And the remainder figures cover primes up to 20,000 only. That a split group stays split and an all-or-nothing group stays so for every prime is Gauss’s theorem, not a consequence of the data; the figure shows what the theorem says, over a range where it can be checked.

Still open: whether sixty-five is all #

The question is Euler’s and it has not moved since Weinberger: is 1,848 the largest idoneal number? A proof would need either the generalised Riemann hypothesis for the relevant functions, or an effective lower bound on class numbers of the kind Siegel’s theorem refuses to give. Goldfeld, Gross and Zagier gave an effective lower bound in the 1980s, but it grows like the logarithm of the discriminant, far too slowly to force classes of order three into every large case.

There are related lists with a similar status. Class groups with other small, special structures — every element of order dividing three, say — can be listed far out by computation and are believed to be completely known, but the proofs that the lists are complete depend on hypotheses of the same kind. Whether every finite abelian group occurs as a class group at all, the question factoring without division left open, sits beside these as the question of which groups are small enough to be rare.

Remainders as a measure of simplicity #

Fermat’s two squares were the first case of a pattern that turned out to have exactly sixty-five instances, or perhaps sixty-six. For those $n$ the question “which primes are $x^2 + ny^2$” has an answer a child can check, because the arithmetic of the forms is as simple as the arithmetic of remainders. For every other $n$ the answer exists and is completely known, but it is written in the language of field extensions, and no remainder will do.

Euler found the boundary by computation and used it to certify primes. Gauss explained it by the structure of the class group. And the reason it cannot be proved to end where it seems to is the same reason the class number problem was hard for a century: the growth of class numbers is certain, and where it begins is not.