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.

Let's suppose also that P is the smallest prime mentioned above as a factor. If it's not, then we may reorder the primes and possibly switch the left and right factorizations to make it happen.

The prime number P doesn't appear as one of the factors in BCDE...F; if it did, we could remove it from both factorizations and replace N by N/P, leading to two different factorizations of a number smaller than N, which can't happen, because we chose N originally to be the smallest positive number with two different prime factorizations.

Now we know that B is larger than P, since P is the smallest prime of them all. Now we replace B by B-P in the left-hand factorization, and we get 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, and from that we know that the left side of the equation is positive, the middle of the equation is positive, the right side of the equation is positive, and the expression in parentheses on the right hand side is positive, too. Replacing B-P by a prime factorization VWXY...Z of it, replacing QRS...T-CDE...F by a prime factorization HIJK...L of it, and naming the middle of the equation M produces the following equation.

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

We know from before that P is not equal to any of the factors in CDE...F, and if P were equal to any of the factors in VWXY...Z, which is equal to B-P, then P would be a divisor of B-P, and then P would also be 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 M, and that number M 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. Now we know that our original assumption that some number N had two prime factorizations must have been wrong. And that's what we wanted to prove!


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.