One way to factor, and no other

Break a number into factors, then break the factors, until nothing breaks any further. The choices along the way are arbitrary — $360$ can be split as $4 \times 90$ or $8 \times 45$ or $36 \times 10$ — and the answer is always the same.

That is the fundamental theorem of arithmetic, and its name is not an exaggeration. Almost every statement in this field either uses it or is a statement about when it fails.

It is also the hardest thing in elementary number theory to see as a claim. It is learned at an age when nothing about it seems to need justifying, it is used constantly without being cited, and the experience of doing arithmetic gives no hint that it might have been otherwise. The best way to recover the sense that something is being asserted is to find an arithmetic where the assertion is false — which this essay does, near the end, with a number system barely more complicated than the whole numbers.

Two claims, not one #

The theorem is usually stated as one sentence and is really two, with quite different difficulties.

Existence. Every whole number above one is a product of primes. This is easy, and the proof is the argument every schoolchild reconstructs: either the number is prime, or it factors as $a \times b$ with both smaller, and the same applies to each of them. The process cannot continue forever because the factors strictly decrease and are all above one, so it ends in primes. That is strong induction and nothing else.

Uniqueness. No number is a product of primes in two different ways. This is not easy, and it is the half that fails elsewhere.

A figure can show that two particular trees agree. No figure can show that every pair of trees for every number agrees, and the gap between those is precisely the theorem.

What uniqueness actually needs #

The proof turns on a lemma that sounds like a restatement and is not.

Euclid’s lemma. If a prime $p$ divides a product $ab$, then $p$ divides $a$ or $p$ divides $b$.

Assume the lemma and uniqueness follows quickly. Suppose some number has two prime factorisations. Take the smallest such number $n$, with $n = p_1 p_2 \cdots = q_1 q_2 \cdots$. The prime $p_1$ divides the right-hand product, so by the lemma it divides one of the $q_i$; since $q_i$ is prime, $p_1 = q_i$. Cancel it from both sides. What remains is a smaller number with two factorisations, contradicting the choice of $n$ as the smallest.

So the whole weight sits on the lemma, and the lemma is where the work is. It is not true for composite divisors: $6$ divides $4 \times 9 = 36$ and divides neither $4$ nor $9$. Whatever makes it true for primes has to be something that distinguishes them from other numbers beyond their definition.

There is an older-looking proof of uniqueness that avoids the lemma, due to Zermelo, and it is worth a paragraph because it shows what the difficulty is made of. Take the smallest number $n$ with two factorisations, and note first that the two lists share no prime — anything common could be cancelled to give something smaller. Let $p$ be the smallest prime in the first list and $q$ the smallest in the second, with $p < q$. Then $pq \le n$, and the number $n - pq$ is smaller than $n$, positive, and divisible by both $p$ and $q$. Factoring it and putting the pieces back gives $p$ appearing in the second factorisation of $n$ after all, which is the contradiction.

That proof uses no lemma and no algorithm, only the ordering of the whole numbers and the ability to subtract. What it makes clear is that uniqueness is genuinely a fact about the ordering of the integers as much as about their multiplication — which is why an arithmetic without a sensible ordering, like the lattice further down this page, has no reason to inherit it.

Euclid’s own proof goes through the algorithm rather than through factorisation, which is what keeps it from being circular. If $p$ does not divide $a$, then $\gcd(p, a) = 1$, since the only divisors of $p$ are $1$ and $p$. Euclid’s algorithm run on $p$ and $a$ produces whole numbers $x$ and $y$ with $px + ay = 1$. Multiplying through by $b$ gives $pbx + aby = b$; the prime divides the first term and divides $ab$ and hence the second, so it divides $b$. No factorisation was used anywhere, which is the point.

The distinction the whole thing rests on #

The lemma exposes a distinction that the whole numbers hide.

A number is irreducible if it cannot be written as a product of two smaller factors. A number is prime, in the sense the lemma uses, if whenever it divides a product it divides one of the factors.

In the whole numbers these are the same set, and nobody ordinarily needs the second word. That coincidence is the fundamental theorem in a different costume — and in an arithmetic where irreducible and prime come apart, unique factorisation goes with them.

Almost every convenience of ordinary arithmetic descends from the coincidence. Greatest common divisors can be read off exponents. Fractions have a canonical lowest form. A square is a number whose exponents are all even. The divisor count is a product of exponents plus one, as the shape of a number’s divisors sets out. Each of those is a statement that becomes meaningless if a number has more than one factorisation.

Six, factored twice #

Here is the arithmetic where it fails. Take the numbers of the form $a + b\sqrt{-5}$ with $a$ and $b$ whole. They add and multiply exactly as expected — $\sqrt{-5}$ squares to $-5$ — and they form a perfectly respectable ring.

In this arithmetic

$$6 = 2 \times 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}),$$

and all four factors are irreducible. The argument is the norm. Define $N(a + b\sqrt{-5}) = a^2 + 5b^2$; a short calculation shows the norm is multiplicative, so a factorisation of a number splits its norm. If $2$ factored as a product of two non-units, their norms would multiply to $4$, so one of them would have norm $2$ — and $a^2 + 5b^2 = 2$ has no whole-number solution, since $b$ must be zero and $2$ is not a square. The same argument disposes of $3$, and of both conjugate factors, whose norm $6$ would have to split as $2 \times 3$.

So four irreducibles, two products, one number. The elements $2$ and $3$ are irreducible and are not prime in the lemma’s sense: $2$ divides $(1+\sqrt{-5})(1-\sqrt{-5}) = 6$ and divides neither factor.

What went wrong, and what fixed it #

The failure was discovered the hard way. In 1847 Lamé announced a proof of Fermat’s last theorem to the Paris Academy, factoring $x^n + y^n$ into linear terms over the complex roots of unity and arguing from unique factorisation. Liouville, in the same session, asked whether unique factorisation was known to hold there. It is not, in general, and the proof collapsed.

Kummer had already found the failure three years earlier, and had already found what to do about it. His repair is one of the great moves in the subject: if the numbers do not factor uniquely, factor something else. He introduced ideal numbers — collections of numbers behaving like a common divisor that is not present — and showed that unique factorisation is restored at the level of those.

In modern language the objects are ideals, and in the ring above the two factorisations of $6$ become the same factorisation of ideals, $(6) = \mathfrak{p}_2^2 \mathfrak{p}_3 \mathfrak{p}_3'$, with each ideal appearing once no matter which route was taken. The number of ways factorisation can fail is measured by a finite number called the class number, which is $1$ exactly when the ring does factor uniquely. For $\mathbb{Z}[\sqrt{-5}]$ it is $2$.

That is a repair of a kind worth recognising. Nothing was proved about the original numbers; the setting was enlarged until the desired property held, in the same spirit as adding a point at infinity to make a plane into a sphere or adding $i$ to make every polynomial factor.

Kummer’s ideal numbers were, at first, exactly as suspicious as the name suggests. They were not numbers; they were defined by their behaviour rather than exhibited; and their introduction to rescue a proof looked to some contemporaries like assuming what was wanted. Dedekind’s reformulation twenty years later replaced them with sets — an ideal is the collection of all multiples of the missing divisor — and that removed the suspicion entirely, because a set of numbers is a perfectly ordinary object.

The pattern is one of the most productive in mathematics and it has been run in this collection before. When an operation fails to have an inverse, invent the inverse and check that the arithmetic survives: negative numbers for subtraction, fractions for division, complex numbers for square roots. Kummer’s move is the same one applied to divisibility, and the object invented is a common divisor that was not there.

Where it works, and why #

The rings that do factor uniquely are worth naming, because the property that makes them work is not the one that looks responsible.

$\mathbb{Z}[i]$ factors uniquely, and the reason is that it has a division algorithm: given $\alpha$ and $\beta$, a quotient can be chosen so that the remainder has strictly smaller norm. That is enough to run Euclid’s algorithm, which produces the identity $\alpha x + \beta y = \gcd$, which gives Euclid’s lemma, which gives uniqueness. The chain is the same one the whole numbers use, and every link is the algorithm.

Geometrically, the division algorithm works in $\mathbb{Z}[i]$ because the lattice is square: every complex number is within half a diagonal — norm $\tfrac12$, which is less than one — of a lattice point. In $\mathbb{Z}[\sqrt{-5}]$ the lattice is stretched by $\sqrt5$ in one direction, the worst-placed point is a long way from any lattice point, and the remainder cannot be forced to shrink. The failure of unique factorisation in the earlier figure is, at bottom, a statement that a rectangle is too tall.

Polynomial rings over a field factor uniquely for the same reason: polynomial long division leaves a remainder of smaller degree. So “factors uniquely” is not a property of numbers but of anything carrying a size function that division can be made to reduce — which is why the theorem has the reach it does, and why the exceptions are exactly the cases where no such size function exists.

Easy one way, hard the other #

Unique factorisation says a number’s factorisation exists and is unique. It says nothing whatever about finding it, and that gap is the foundation of a large industry.

Multiplying two thousand-digit primes takes microseconds. Recovering them from the product is, as far as anybody knows, infeasible: the best general methods run in time roughly exponential in the cube root of the number of digits, and a two-thousand-digit product is comfortably out of reach.

The asymmetry is not a theorem. Nobody has proved that factoring is hard — only that nobody has found a way to do it quickly, over fifty years of trying — and the whole of RSA encryption rests on that unproven belief. Shor’s algorithm factors in polynomial time on a quantum computer, which means the belief is specifically about classical machines and is known to be false for a machine that may eventually be built.

What is worth extracting is the shape of the situation. A theorem guarantees a unique answer exists; a computation to find it may be impossible; and the two facts coexist without tension. The fundamental theorem is a statement about what is true, not about what can be found — which is the same distinction that separates Euclid’s proof that primes never run out from any method of producing the next one.

What the picture cannot show #

The lattice figure shows a finite patch and asserts that nothing anywhere has norm $2$ or $3$. The generator checks it over a much larger range than is drawn, but no drawing establishes it — the argument that does is two lines of algebra about $a^2 + 5b^2$, and it works because the norm is a positive form that grows in every direction.

More seriously, no picture distinguishes the ring where factorisation is unique from the one where it is not. $\mathbb{Z}[\sqrt{-1}]$, the Gaussian integers, is a lattice that looks like the one above with the vertical scale changed, and it does factor uniquely — which is the fact behind primes as sums of two squares. The two lattices are drawn the same way and behave completely differently, and the difference is invisible in the geometry: it is whether a division algorithm exists, which is a statement about how well the norm can be made to shrink.

This is the sharpest version of a limitation that runs through the whole collection. A picture can show an instance and cannot show a quantifier, and a theorem about every number is a quantifier. The figures at the top of this essay demonstrate two trees agreeing. What they cannot do, and what no drawing does, is rule out the pair that does not.

Where the ladder goes next #

The theorem’s immediate use is that a number’s divisors are exactly the products of subsets of its prime powers, so a number’s divisor structure is a lattice with an axis per prime. The shape of a number’s divisors reads that off, and gets the divisor count and the divisor sum from the shape rather than from any formula.

The other direction is the one Kummer opened. Rings where factorisation nearly works, and the exact measurement of how far off they are, is algebraic number theory; the fact that some primes split in the Gaussian integers and some do not is the first case of it, and it is decided by a remainder on division by four.