# Uniqueness of factorization for math-phobes?

The unique factorization theorem states that for any integer $n > 1$, there exists a unique increasing finite sequence of prime numbers $p_1 \leq p_2 \leq p_3 \leq \dots \leq p_r$ such that

$$n = \prod_{i=1}^r p_i\;.$$

I've been searching for a proof of this theorem that even a "math-phobe" could understand, with little success. All the proofs I've been able to find either require familiarity with a fair bit of machinery (e.g. the Euclidean algorithm), or are so lengthy and convoluted (at least to the uninitiated) that no "math-phobe" would have the stamina to work through it.

Maybe this is the theorem that divides the population into those who are math-adept and those who are math-phobes, but "hope springs eternal", as they say, so...

If anyone happens to know of a particularly simple and clear proof, please let me know.

NOTE: in case there's any confusion: I don't want this proof for me. I've seen plenty of proofs of this theorem that I understand. So please, don't urge me to "embrace" anything. Needless to say, urging a math-phobe to "embrace" anything mathematical is a complete waste of time. Math-phobia simply means, by definition, an active avoidance of anything mathematical. The proof I'm looking for is one that does not require any "embracing" from anyone, but rather one that is readily understandable. Now, I realize that such proof may not exist, and the article that kahen linked to argues that this in fact the case.

• Why is the Euclidean algorithm scary? It's just long division with integers, and most of us learned it in grade school. It's not as if you even have to do any long division: you just need the concept for the proof. I think in any proof of factorization, you are going to need mathematical induction, too. That is also "scary", but it is well worth learning, so don't avoid it... embrace it! It is a well-known result that the way to stop hating something is to get good at it :) – rschwieb Apr 16 '13 at 15:10
• – kahen Apr 16 '13 at 15:10
• Nice link @kahen! – rschwieb Apr 16 '13 at 15:12
• @rschwieb: please see my edit. – kjo Apr 16 '13 at 15:49
• @kjo Sorry, you're right that I read it as if you were the one learning it, but the advice I gave still applies. It would be ironic and unfortunate if you avoided teaching useful mathematical concepts because you bought into the fantasy that math phobes have that they can't understand those things. Certainly avoiding the Euclidean algorithm because you think they can't stand it is not the right direction to go. The message is still positive: the proof using the Euclidean algorithm is worth learning, and it would be convoluted (or even futile) to try to avoid it. – rschwieb Apr 16 '13 at 16:11

Below is one simple proof (which has the nice property that it is conceptually faithful to the essence of the matter). I've had much success explaining this proof to educated laypersons, bright high-school students (and even some talented elementary students). Since you say you already know a few proofs, I will omit the easy parts, such as the simple inductive proof of the existence of prime factorizations. Instead, I concentrate only on the most difficult step: the key inductive step of the uniqueness of prime factorizations, viz. Euclid's Lemma. That follows immediately from the following fundamental lemma - which has widespread applications in number theory.

Lemma $\$ If $\rm\,S\,$ is a nonempty set of positive integers that is closed under positive subtraction (i.e. for any $\rm\:m,n\in S,\:$ if $\rm\: m > n\:$ then $\rm\: m-n\in S),\:$ then every integer in $\rm\:S\:$ is a multiple of the least integer $\rm\:d\:$ in $\rm\:S.$

Proof $\$ Suppose $\rm\:s\in S.\:$ By repeatedly subtracting $\rm\:d,\:$ we deduce that $\rm\:S\:$ contains all of the positive integers in the sequence $\rm\ s,\ s\!-\!d,\ s\!-\!2d,\ s\!-\!3d,\ldots$ By the Division Algorithm, the least nonegative integer in this sequence is the remainder $\rm\:r = s-qd\:$ left on dividing $\rm\:s\:$ by $\rm\:d,\:$ and $\rm\:0 \le r < d.\:$ The remainder $\rm\:r\:$ must be $\,0\:$ $\rm(\Rightarrow\:s = qd),\:$ else $\rm\:0 < r< d,\:$ contra $\rm\:d\:$ is the least element of $\rm\:S.\$ QED

For example, the positive even integers $\rm\:S = \{2,4,6,\ldots\}\,$ are closed under positive subtraction since $\rm\: 2m-2n = 2(m-n)\:$ is even. Thus the Lemma implies that every positive even integer is a multiple of the least positive even integer, i.e. $\rm\:2n\:$ is a multiple of $\,2.\:$ Similarly for $\rm\:S = \{3,6,9\},\:$ but not for $\rm\:\{6,9\}\:$ since it is not closed under positive subtraction: $\rm\:9\!-\!6=3\not\in S.\:$ One corollary of the Lemma is the following result, which is the keystone of uniqueness of prime factorizations.

Euclid's Lemma $\ \$ Prime $\rm\ p\mid ab\:\Rightarrow\: p\mid a\ \ or\ \ p\mid b, \$ for all positive integers $\rm\ a,b.$

Proof $\$ Let $\rm\:S\:$ be the set of positive integers $\rm\:n\:$ such the $\rm\:p\mid an,\:$ i.e. $\rm\:p\:$ divides $\rm\:an.\:$ Note $\rm\:S\:$ is nonempty since $\rm\:p\mid ap,ab\:\Rightarrow\:p,b\in S.\:$ Also $\rm\:S\:$ is closed under positive subtraction, since if $\rm\:m,n\in S\:$ and $\rm\:m>n\:$ then $\rm\:p\mid am,an\:\Rightarrow\:p\mid am\!-\!an = a(m\!-\!n),\:$ so $\rm\:m\!-\!n\in S.\:$ Let $\rm\,d\,$ be the least element of $\rm\:S.\:$ By the Lemma, $\rm\:d\:$ divides every element of $\rm\:S.\:$ Thus $\rm\:d\mid p.\:$ But the only divisors of the prime $\rm\:p\:$ are $\rm\:d = 1\:$ or $\rm\:d = p.\:$ In the first case, $\rm\:d = 1\in S,\:$ so $\rm\:p\mid a\cdot 1 = a,\:$ by definition of $\rm\:S.\:$ In the second case, $\rm\:d = p\:$ so, by the Lemma, $\rm\:p\mid b,\:$ by $\rm\:b\in S.\:$ Thus either $\rm\:p\mid a\:$ or $\rm\:p\mid b.\ \$ QED

Now it is straightforward to inductively apply Euclid's Lemma to match up, then cancel primes in any two prime factorizations of an integer, so inductively proving the uniqueness of prime factorizations, e.g. see this proof, which uses a fractional version of the Lemma. That page also includes many other proofs you may find of interest, including a famous proof of Zermelo, which eliminates the division algorithm by directly inlining into the proof its inductive essence. One can also do the same for the above Lemma if one so desires, e.g. see here. But that only serves to obscure the conceptual essence of the matter (the Euclidean algorithm, or principality of ideals, etc). The point of abstracting out the above lemma is that this (ideal) structure is ubiquitous in number theory and algebra - something that will become much clearer when one studies (algebraic) number theory and university algebra.