# 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.