Factoring uniquely with no way to divide

The standard proof of unique factorisation runs through a chain of four links. A division algorithm gives Euclid’s algorithm; Euclid’s algorithm gives a greatest common divisor as a combination of the two numbers; that combination gives Euclid’s lemma; and the lemma gives uniqueness. In the whole numbers every link is ordinary. In the numbers of the form $4k + 1$ the chain was cut at the first link — no subtraction, no algorithm — and uniqueness failed.

That invites the obvious conclusion: a division algorithm is what unique factorisation needs. The conclusion is false, and the counterexample is a ring where division fails so thoroughly that no measure of size, however it is chosen, can repair it — and where every element nevertheless factors in exactly one way.

The ring lives among the imaginary quadratic fields, and the place to start is how division looks there.

Division is a question about discs #

The integers of $\mathbb{Q}(\sqrt{-d})$ form a lattice in the complex plane. For $d = 1$ it is the square grid of Gaussian integers $a + bi$; for $d = 2$ it is the rectangle grid $a + b\sqrt{-2}$; and when $d$ leaves remainder three on division by four, the integers include the half-points $\omega = (1 + \sqrt{-d})/2$, and the lattice is made of triangles — the extra points that the integers of a field turned out to need. Size is measured by the norm, the squared distance from the origin, and it is multiplicative.

To divide $\alpha$ by $\beta$ with a small remainder, compute the exact quotient $\alpha / \beta$, which is some point of the plane, not usually on the lattice. Pick a lattice point $q$ near it and set $r = \alpha - q\beta$. Then

$$N(r) = N(\beta) \cdot \left|\frac{\alpha}{\beta} - q\right|^2,$$

so the remainder is smaller than the divisor exactly when the exact quotient lies within distance one of the chosen lattice point. The division algorithm works for every pair exactly when discs of radius one around the lattice points cover the whole plane. Division with remainder, the thing Euclid’s algorithm is built from, has become a covering problem.

The covering problem has an exact answer. For $d$ leaving remainder one or two on division by four, the lattice is rectangular with sides $1$ and $\sqrt d$, the worst point is the centre of a cell, and its distance to the corners is $\sqrt{1 + d}/2$. That is below one only for $d = 1$ and $d = 2$. For $d$ leaving remainder three the cell is a triangle, the worst point is its circumcentre, and the distance is $(d + 1)/(4\sqrt d)$ — below one for $d = 3$, $7$ and $11$, where it is $0.58$, $0.76$ and $0.90$, and above one from $d = 15$ on. Those five values, $1, 2, 3, 7, 11$, are the norm-Euclidean imaginary quadratic fields, and there are no others.

Euclid’s algorithm where the discs cover #

Where the discs cover, the algorithm runs, and it runs faster than the covering bound promises. In the Gaussian integers the worst point is the centre of a unit square, at distance $\sqrt2/2$, so every remainder has at most half the norm of its divisor.

The two starting numbers have norms $533 = 13 \times 41$ and $481 = 13 \times 37$, which share a factor of thirteen, so a common divisor of norm $13$ is expected. The algorithm finds it in two divisions: $2 - 3i$, which is $3 + 2i$ multiplied by the unit $-i$. Running the steps backwards expresses it as a combination of the two starting numbers, exactly as in the algorithm on rectangles, and from there Euclid’s lemma follows word for word.

This is the whole reason the Gaussian integers factor uniquely, and it is why primes of the form $4k + 1$ split as a product of two conjugates in only one way. It is also why the two squares can actually be computed: an algorithm that proves uniqueness also produces the thing whose uniqueness it proves.

Where the discs leave holes #

The covering fails for most fields, and it fails the same way whether factorisation is unique or not.

The field of $\sqrt{-5}$ is the one where six factors twice, and its lattice is a rectangle too tall for the discs, with holes in the middle of every cell. That looks like an explanation of the failure, and the rectangle is often offered as one. But the lattice of $\mathbb{Q}(\sqrt{-19})$ also leaves holes, of about the same size, and in that ring factorisation is unique. So is it in $\mathbb{Q}(\sqrt{-43})$, whose holes are the largest in the figure.

The picture therefore says less than it seems to. Covering implies a division algorithm, and a division algorithm implies unique factorisation. Holes deny the first implication a starting point and say nothing about the conclusion. Nothing in the geometry of discs distinguishes a field whose factorisation merely has no easy proof from one whose factorisation is actually broken.

One division that cannot be done #

The holes can be made concrete. In the integers of $\mathbb{Q}(\sqrt{-19})$, with $\omega = (1 + \sqrt{-19})/2$, try to divide $\omega$ by $2$.

The quotient lies at the centre of a rhombus of four lattice points, all equidistant from it, and all slightly more than one away. Whatever quotient is chosen, the remainder $\omega - 2q$ has norm $4 \times \tfrac54 = 5$, and the divisor $2$ has norm $4$. The remainder is larger than the divisor. The norm cannot drive this division.

The failure is not exotic. Holes of this kind sit between every pair of rows in the lattice, and a positive fraction of all divisions land in them. What makes this one useful is that it is small enough to check by hand.

No measure of size will do #

The norm is only one way to measure size, and a Euclidean ring needs only some function to the whole numbers that its remainders decrease. Perhaps a cleverer function would work where the norm fails. In 1949 Theodore Motzkin showed that none does, and his argument turns on a property any such function would force.

Suppose some size function makes the ring Euclidean. Among the elements that are neither zero nor units, take one of smallest size and call it $u$. Divide anything at all by $u$. The remainder is either zero or smaller than $u$ — and everything smaller than $u$ is zero or a unit, since $u$ was the smallest of the rest. So every element of the ring leaves remainder zero or a unit on division by $u$. The only units in this ring are $1$ and $-1$, so there are at most three remainders, and the number of remainder classes modulo $u$ is exactly its norm. So $u$ would have norm $2$ or $3$.

No element has norm $2$ or $3$. The reason is the identity $4(x^2 + xy + 5y^2) = (2x + y)^2 + 19y^2$: for the norm to be below $5$, $y$ must be $0$, and then the norm is a square. So there is no candidate for $u$, and no size function whatever makes this ring Euclidean — not the norm, not any modification of it, not any function anyone could define.

A division allowed a second attempt #

Division fails in this ring, but it fails in a curiously repairable way. The failed division above was $\omega$ by $2$. Multiply $\omega$ by $1 - \omega$ first. Since $\omega$ satisfies $\omega^2 = \omega - 5$, the product is $\omega - \omega^2 = 5$, and $5$ divides by $2$ with remainder $1$. So the combination $(1 - \omega)\,\omega - 2 \times 2 = 1$ is non-zero and has norm $1$, smaller than the norm $4$ of the divisor.

That is not a division algorithm, since a multiple of $\omega$ has been divided rather than $\omega$ itself. But it is exactly what the proof of unique factorisation needs. Euclid’s lemma comes from a greatest common divisor written as a combination of the two numbers, and a combination with a multiplier in front is still a combination. The Dedekind–Hasse criterion turns this into a theorem: a ring factors uniquely, with every ideal principal, exactly when for any $\alpha$ and $\beta$ with $\beta$ not dividing $\alpha$ some combination $s\alpha - t\beta$ is non-zero and of smaller norm than $\beta$.

The criterion asks less than a division algorithm in one precise respect. A division algorithm insists on $s = 1$: the dividend must be taken as it is. Dedekind–Hasse lets the dividend be multiplied by anything in the ring before dividing, which moves the exact quotient $s\alpha/\beta$ around the plane until it lands inside a disc. In the covering picture, a hole is no longer fatal; it is only a place from which the quotient has to be moved.

In $\mathbb{Q}(\sqrt{-19})$ it can always be moved. Every quotient that falls in a hole can be shifted by a multiplier such as $2$, $\omega$ or $1 - \omega$ into some disc, and checking that this always succeeds is a finite calculation over one cell of the lattice, because the holes repeat with the lattice. The same calculation for $\mathbb{Q}(\sqrt{-5})$ fails on the centre of its rectangle, which is where the missing divisor of six would have been.

Why it factors uniquely anyway #

Unique factorisation in a ring of algebraic integers is the statement that every ideal is principal — generated by a single element — which is the class number being one. Euclid’s algorithm is one way to prove that, and there is another which never divides anything.

Minkowski’s theorem on lattice points in convex regions shows that every class of ideals contains an ideal whose norm is at most $\tfrac{2}{\pi}\sqrt{|D|}$, where $D$ is the discriminant. For $D = -19$ the bound is $2.77$. So every class contains an ideal of norm $1$ or $2$. An ideal of norm $1$ is the whole ring, which is principal. An ideal of norm $2$ would be a prime ideal lying over $2$, and that exists only if $x^2 + x + 5$ has a root modulo $2$ — but $x^2 + x + 5$ is odd for every whole $x$. So there is no such ideal, every ideal is principal, and factorisation is unique.

The proof replaces a covering of the whole plane with a bound on where one ideal in each class must sit. The first needs every point of the plane within reach of the lattice; the second needs only that a region of a certain area contain a lattice point, and it asks that of the ideals rather than of the ring. That is a much weaker demand, which is why it survives when the discs leave holes.

Four fields pass the second test and fail the first: $d = 19, 43, 67$ and $163$. Together with the five that pass both, they make the nine imaginary quadratic fields with unique factorisation, a list Gauss conjectured and that was proved complete in the 1950s and 1960s. So of the nine, five factor uniquely because they can divide and four factor uniquely for a subtler reason, and which primes a form takes is decided by exactly this distinction when it can be decided by a congruence at all.

Forty primes in a row #

The largest of the four has a visible consequence, and it was noticed long before its cause.

Euler noticed in 1772 that $n^2 + n + 41$ is prime for every $n$ from $0$ to $39$, and the spiral of primes shows it as a dark diagonal. The failure at $n = 40$ is forced by the polynomial’s own form: $40^2 + 40 + 41 = 40 \times 41 + 41 = 41^2$. So forty is the longest run this polynomial could possibly have. The question is why it has the longest possible run instead of failing at $n = 2$ like most quadratics.

The discriminant of $x^2 + x + 41$ is $1 - 164 = -163$, and the norm on the integers of $\mathbb{Q}(\sqrt{-163})$ is $x^2 + xy + 41y^2$. Suppose some value $n^2 + n + 41$ with $n \le 39$ had a prime factor $q$. The value is below $41^2$, so $q < 41$. Since $q$ divides $n^2 + n + 41$, the polynomial has a root modulo $q$, so $q$ splits in the field, into prime ideals of norm $q$. With unique factorisation those ideals are principal, so some element has norm exactly $q$. But $x^2 + xy + 41y^2 = (x + y/2)^2 + \tfrac{163}{4}y^2$, which is at least $40.75$ unless $y = 0$ — and then it is a square, not a prime. So no element has norm $q$, and the value must have been prime.

The argument works for any $p$ whose field has class number one, and it reverses: if every value $n^2 + n + p$ with $n \le p - 2$ is prime, the field of discriminant $1 - 4p$ factors uniquely. That equivalence is Rabinowitsch’s criterion, published in 1913. So Euler’s polynomial is the last of six. The table finds exactly those six, with runs of $1, 2, 4, 10, 16$ and $40$, and no seventh prime below four hundred comes close. The completeness of the nine-field list says there is no seventh at all.

The smaller members of the family show the mechanism with less at stake. For $p = 17$ the field has discriminant $-67$, the norm form is $x^2 + xy + 17y^2$, and its smallest value with $y \ne 0$ is $16.75$ — just above every prime below seventeen, which is what lets $n^2 + n + 17$ run through sixteen primes. For $p = 13$ the discriminant is $-51$, the field does not factor uniquely, and the run stops at the first step: $1^2 + 1 + 13 = 15$. The prime $3$ divides it and also divides the discriminant, so in that field $3$ is the square of a prime ideal of norm $3$ — and since $x^2 + xy + 13y^2$ never equals $3$, that ideal is not principal, and nothing stops a value from being a multiple of three. The length of the run is a report on whether the small primes’ ideals are principal, read off one value at a time.

What the discs cannot decide #

Whether a ring factors uniquely. The covering figures decide exactly whether the norm gives a division algorithm, and they decide it completely. Unique factorisation is a different question, and the second covering figure shows two rings that fail to factor and two that succeed, with holes of comparable size in all four.

That no other function would work. The norm table shows that nothing has norm $2$ or $3$ over a finite window, and the identity with $19y^2$ extends it to the whole ring. The step from there to every conceivable size function is Motzkin’s argument, which is a proof about all functions at once and cannot be drawn.

The completeness of the list. The Rabinowitsch table checks primes below four hundred. That no larger prime has the full run is the theorem that there are exactly nine fields, proved by Kurt Heegner in 1952 in a paper that was not accepted for more than a decade, and again by Alan Baker and Harold Stark in the late 1960s. A finite search cannot establish it, and before those proofs the possibility of a tenth field was genuinely open.

Still open: which class groups occur #

The class number counts ideal classes, and the classes themselves form a finite abelian group, the class group. For the nine fields it is trivial. For $\mathbb{Q}(\sqrt{-5})$ it has two elements, which is the one missing divisor that made six factor twice.

Every finite abelian group is known to be the class group of some ring that behaves like a ring of integers — Luther Claborn proved that in 1966 for the broad class of Dedekind domains. Whether every finite abelian group is the class group of the integers of some number field is not known. No group has been ruled out, and no construction reaches them all. Even for imaginary quadratic fields, where the class groups are computed by the thousand, which groups appear is known only in pieces.

A theorem proved two ways #

Unique factorisation has two proofs in the imaginary quadratic fields, and they reach different distances. Division with remainder is local and constructive: it needs every point of the plane near the lattice, it produces greatest common divisors by an algorithm, and it works in exactly five fields. The ideal-theoretic proof is global and silent: it needs only that each ideal class have a small representative, it computes nothing, and it works in nine.

The four fields between them are where the chain of implications from the start of this essay is broken at its first link and the conclusion holds anyway. They are why “Euclidean” and “unique factorisation” are different words, and the largest of them is why a quadratic Euler wrote down in 1772 produces forty primes before it stops.