Unique factorization

Suppose factorization of numbers into primes were not unique. This would mean that some number N would have two different factorizations into primes.

BCDE...F = N = PQRS...T

Let us suppose that we have chosen N to be the smallest positive number with at least two different prime factorizations, and let's suppose also (by reordering/renaming the primes and possibly interchanging the two factorizations) that P is the smallest prime mentioned above as a factor. The prime number P doesn't appear as one of the factors in BCDE...F, for else we could cancel it from both factorizations, yielding two different factorizations of a number smaller than N. Now we know that B, in particular, is larger than P, since P is the smallest prime of them all. Replacing B by B-P in the original equation yields the following equation, which you can check using the distributive rule.

(B-P)CDE...F = N-PCDE...F = P(QRS...T-CDE...F)

We know that B-P is positive, hence so is the left side of the equation, the right side of the equation, and the parenthesized expression on the right hand side. Replacing both parenthesized expressions above by factorizations of them into primes and eliminating the middle of the equation yields something like the following equation.

(VWXY...Z)CDE...F = P(HIJK...L)

We know from before that P does not occur as one of the factors in CDE...F, and if P were to occur as one of the factors in VWXY...Z, which is equal to B-P, that would imply that P is a divisor of B, which can't happen because B is a prime number larger than P. Since P appears as a factor on the right hand side but not on the left hand side, the two sides of the equation are different prime factorizations of the same number, and that number is smaller than N, because it was obtained from N by subtracting something positive. This can't be happening, for we chose N originally to be the smallest positive number with two different prime factorizations. Hence, our original assumption that some number had two prime factorizations must have been wrong. Q.E.D.


This proof was constructed together with David Grayson and Greg Girolami. It turns out that it's essentially the same as the proof in the book, "What is Mathematics?", by Richard Courant and Herbert Robbins, published by Oxford University Press, New York, 1941. It is also presented in the book, "Lectures on elementary number theory", by Hans Rademacher, published in New York by Blaisdell Pub. Co., 1964, and attributed there to Hasse, F. A. Lindemann, and Zermelo.