# How can we prove that among positive integers any number can have only one prime factorization?

I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?

-
@gigahari: The result is not difficult, but it takes a fair while to build the required machinery. You could work your way to it by following Wikipedia links. But best would be to go through the beginnings of a book on Elementary Number Theory. I think there are some freely available, but best would be to find such a book at your local library. – André Nicolas Feb 27 '12 at 5:36
I am honestly baffled that some people (with internet access!) seem to be so unable to find the answers to their questions on the internet. The OP says that s/he has "never found proof for this". As an experiment, I cut and pasted the title of the question into google. The first hit was (surprise!) this very page. The second hit is en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic.... – Pete L. Clark Feb 27 '12 at 6:51
To adjust the ancient proverb: if there is a magical web that will do much of your fishing for you automatically, then surely we help someone out more by telling him about this magical web and showing him how easy it is to use then catching individual fish for him (and maybe using the magic web to do it). No? – Pete L. Clark Feb 27 '12 at 6:52
@PeteL.Clark I did search, but somehow assumed the answer to my question would not be at this link. But I now concede it was a mistake. Having never seen the fish I was looking for, I threw it back into the waters, when the magical web presented it to me! – gigahari Feb 27 '12 at 7:31

Below is a direct elementary proof of the Fundamental Theorem of Arithmetic from first principles, based on ideas going back to Zermelo (1901).

THEOREM $\$ Every natural $\rm\:n \ge 1\:$ has a prime factorization, unique up to order of factors.

Proof $\ \$ By induction on $\rm\:n.$ $\rm\:n = 1\:$ is an empty product of primes. Let $\rm\:n>1\:.\:$ Suppose that the theorem is true for all naturals $\rm < n.\:$ Let $\rm\:p\:$ be the least factor $\ne 1\:$ of $\rm\:n.$ $\rm\:p\:$ has no smaller factors $\rm\:q\ne 1,\:$ else $\rm\:q\:|\:p\:|\:n,\:$ contra leastness of $\rm\:p.\:$ Thus $\rm\:p\:$ is prime. By induction $\rm\:n/p\:$ has a unique prime factorization which, appended to $\rm\:p,\:$ yields a prime factorization of $\rm\:n.\:$ We show it unique.

Consider a second prime factorization of $\rm\:n.\:$ It has at least one prime $\rm\:q\:$ since $\rm\:n > 1\:.\:$ Hence $\rm\ n = q\ q_2\cdots\:q_k = q\:Q\$ for $\rm\: q_i\:$ primes. If $\rm\:p\:$ equals one of the $\rm\:q$'s then deleting $\rm\:p\:$ from the second factorization must leave said unique factorization of $\rm\:n/p\:.\:$ Thus both factorizations of $\rm\:n\:$ are the same up to order. Hence if $\rm\:p = q\:$ then the proof is complete.

Otherwise, it suffices to show $\rm\:p\:$ equals one of the $\rm\:q_i.\:$ By leastness of $\rm\:p,\:$ $\rm\ p\ne q\ \Rightarrow\ p < q\:,\:$ so $\rm\ \bar n\: =\: n - p\:Q\: =\: (q - p)\:Q\$ is $\rm\ 0 < \bar n < n\:.\:$ $\rm\:p\:|\:n\ \Rightarrow\ p\:|\:\bar n,\:$ so by induction $\rm\ \bar n/p\$ has a prime factorization which, appended to $\rm\:p,\:$ gives a prime factorization of $\rm\:\bar n\:.\:$ By induction $\rm\:q-p\:$ has a prime factorization which, appended to $\rm\:Q = q_2\cdots q_k$ is a second factorization of $\rm\:\bar n.\:$ By induction both factorizations of $\rm\:\bar n\:$ are equal up to order, thus $\rm\:p\:$ occurs in said factorization of $\rm\:(q-p)\:Q,\:$ but not in that of $\rm\:q -p\:,\:$ else $\rm\:p\ |\ q-p\:$ $\Rightarrow$ $\rm\:p\:|\:q\:,\:$ contra $\rm p\ne q\:.$ Thus $\rm\:p\:$ must occur in the factorization $\rm\:Q = q_2\cdots\:q_k.\:$ Hence, indeed, $\rm\:p\:$ equals one of the $\rm\:q_i.\ \$ QED

-
The 1901 date is wrong, as far as I can tell, though the attribution to Zermelo is appropriate. As mentioned here, this seems to date from 1912 or so. – Andrés E. Caicedo Jun 7 '13 at 6:28

Definition. An integer $p$ is a prime if and only if $p\neq \pm 1$, $p\neq 0$, and, whenever $p|ab$, either $p|a$ or $p|b$.

Definition. An integer $n$ is irreducible if and only if $n\neq \pm 1$ and, if $n=ab$ with $a$ and $b$ integers, then either $a=\pm 1$ or $b\pm 1$.

Lemma. If $a$ and $b$ are integers, then $a$ and $b$ have a greatest common divisor that can be written as $\alpha a + \beta b$ for some integers $\alpha$ and $\beta$.

Proof. Consider the set $I=\{\alpha a + \beta b \mid \alpha,\beta\in\mathbb{Z}\}$. If this set equals $\{0\}$, then $a=b=0$, $\gcd(0,0)=0$, and we can take $\alpha=\beta=1$. If the set is not equal to $0$, then it contains a smallest positive member $d$; if $n$ is any element of the set, then dividing $n$ by $d$ with remainder we have $n = qd + r$, $0\leq r \lt d$. But $qd\in I$, and if $n$ and $qd$ are both in $I$, then so is $n-qd$; hence $r\in I$; by minimality of $d$, we conclude that $r=0$, so $n$ is a multiple of $d$. That is, $I$ is exactly all multiples of $d$. Since $a,b\in I$, then $d|a$ and $d|b$; if $c$ is any integer that divides both $a$ and $b$, then $c$ divides every element of $I$, hence divides $d$. Thus, $d$ is a gcd of $a$ and $b$. $\Box$

Lemma. If $n$ is irreducible, then for every integer $a$, either $\gcd(n,a) = n$, or $\gcd(n,a)=1$.

Proof. Let $d=\gcd(n,a)$. Then $d|n$, hence $n=dm$ for some integer $m$; since $n$ is irreducible, either $d=\pm 1$, or else $m=\pm 1$ (in which case $d=\pm n$). $\Box$

Theorem. (Euclid's Lemma) Irreducible integers are prime and prime integers are irreducible.

Proof. Assume $p$ is prime, and $p=ab$. Then $p|ab$, hence $p|a$ or $p|b$; if $p|a$, then we can write $a=pr$, so $p=ab = prb$; since $p\neq 0$, we get $rb=1$, hence $b=\pm 1$; symmetrically, if $p|b$, then $b=ps$, so $p=ab=asp$ and we conclude $as=1$ so $a=\pm 1$. Thus, if $p$ is prime, then $p$ is irreducible.

Now assume that $p$ is irreducible; then note that $p\neq 0$, since $0=0\times 2$ and neither $0$ nor $2$ are equal to $1$ or $-1$. Now assume that $p|ab$; we need to show that $p|a$ or that $p|b$.

Since $p$ is irreducible, either $\gcd(p,a)=p$, in which case $p|a$ and we are done, or else $\gcd(p,a)=1$; then we can write $1=\alpha a + \beta p$; multiplying through by $b$ we get $b = \alpha ab + \beta b p$. Since $p|ab$, then $p|(\alpha ab+\beta bp) = b$, so $p|b$. $\Box$

The usual proof that factorizations exist is by strong induction:

Theorem. (Euclid) For every positive integer $n$, if $n\gt 1$, then $n$ can be written as a product of prime numbers.

Proof. Assume that every number strictly smaller than $n$ is either equal to $1$, or can be written as a product of prime numbers. We prove that the same holds for $n$. If $n=1$, we are done. If $n$ is prime, then we can express $n$ as $n=n$, a product of primes, and we are done. If $n$ is not prime, then it is not irreducible, so we can write $n=ab$ with $a$ and $b$ integers, neither equal to $1$; since $n\gt 0$, we may (changing signs if necessary) assume that $a$ and $b$ are both positive, hence $1\lt a \lt n$ and $1\lt b \lt n$. By the induction hypothesis, both $a$ and $b$ can be written as products of primes, $a= p_1\cdots p_r$ and $b=q_1\cdots q_s$; therefore, $n = ab = p_1\cdots p_rq_1\cdots q_s$, so $n$ can be written as a product of primes. This proves the result for all positive integers, by induction. $\Box$

The key to uniqueness is Euclid's Lemma:

Theorem. (Gauss) The factorization of positive integers into primes is unique. That is, if $x$ is a positive integer, $x\gt 1$, and $$x = p_1^{a_1}\cdots p_r^{a_r} = q_1^{b_1}\cdots q_s^{b_s}$$ where $p_1\lt\cdots\lt p_r$, $q_1\lt\cdots\lt q_s$ are primes, and $a_i,b_j$ are positive integers for all $i$ and $j$, then $r=s$, $p_i=q_i$, and $a_i=b_i$ for all $i$.

Proof. We may assume that $a_1+\cdots+a_r\leq b_1+\cdots +b_s$ by exchanging the two factorizations if necessary. We proceed by induction on $n=a_1+\cdots+a_r$.

If $n=1$, then $x=p_1$ is a prime; thus, $p_1 = q_1^{b_1}\cdots q_s^{b_s}$. Since primes are irreducible, all factors in $q_1^{b_1}\cdots q_s^{b_s}$ except one must be equal to $1$ or $-1$; since all factors are prime, $s=1$ and $b_1=1$. Thus, we have uniqueness.

Assume the result holds if $n=k$, and that the factorization of $x$ has $k+1$ factors.

Since $p_1|x$, then $p_1|q_1^{b_1}\cdots q_s^{b_s}$. Since $p_1$ is prime, it divides some $q_j$, $p_1|q_j$. Since $q_j$ is prime, it is irreducible, so we must have $p_1=q_j$. Cancelling $p_1$ and $q_j$ from $$x = p_1^{a_1}\cdots p_r^{a_r} = q_1^{b_1}\cdots q_s^{b_s}$$ we obtain $$y = p_1^{a_1-1}\cdots p_r^{a_r} = q_1^{b_1}\cdots q_{j-1}^{b_{j-1}}q_j^{b_j-1}q_{j+1}^{b_{j+1}}\cdots q_s^{b_s}.$$ The number of prime factors of $y$ is $n$; by the induction hypothesis, the two remaining factorizations are identical.

I claim we cannot have exactly one of $a_1$ and $b_j$ equal to $1$.

If $a_1\gt 1$ and $b_j=1$, then by the induction hypothesis we either have $j\gt 1$, in which case $q_1=p_1$, which contradicts $p_1=q_1\lt q_j=p_1$; or $j=1$, in which case we would again get the contradiction that the equality of the two factorizations for $y$ give $p_1 = q_2\gt q_1 = p_1$.

If $a_1=1$ and $b_j\gt 1$, then either $j\gt 1$, in which case we get a contradiction that $p_1 = q_j \gt q_1 = p_2 \gt p_1$; or $j=1$, in which case we get a contradiction that $p_1\lt p_2 = q_1 = p_1$.

Thus, either $a_1=b_j=1$, or else $a_1\gt 1$, $b_j\gt 1$.

If $a_1\gt 1$, $b_j\gt 1$, then since both factorizations for $y$ are identical, $p_1=q_1$, so $j=1$; $r=s$, $p_i=q_i$ for $i=1,\ldots,r$, $a_i=b_i$ for $i=2,\ldots,r$; and $a_1-1=b_1-1$, hence $a_1=b_1$, so the two factorizations of $x$ are identical.

If $a_1=b_j=1$, since both factorizations of $y$ are identical, if $j\gt 1$ we have $p_2 = q_1\lt q_j = p_1 \lt p_2$; this is impossible so $j=1$, and so $r-1=s-1$ (so $r=s$), $p_i=q_i$ for $i=2,\ldots,r$ (and we already have $p_1=q_1$); $a_j=b_j$ for $j=2,\ldots,r$, and we also have $a_1=b_1=1$. So the two factorizations for $x$ are identical. $\Box$

-

Besides the Wikipedia article mentioned by M Turgeon above, there is a very nice explanation by Tim Gowers here.

-

Here is a simple self-contained conceptual proof of uniqueness of prime factorizations of integers. $\:$ It employs Euclid's Lemma to prove that if a prime divides a product then it divides some factor. It proves Euclid's Lemma by exploiting the structure of the set of possible denominators of a fraction: it is closed under subtraction hence it is closed under gcd. Therefore a fraction representable with coprime denominators $\rm\:p,q\:$ is representable with denominator $\rm\:gcd(p,q)= 1,\:$ so it is an integer. For more on the innate algebraic structure see my posts on denominator ideals.)

Theorem $\$ Prime factorizations of an integer $\rm\:n>1\:$ are unique up to order.

Proof $\$ Suppose $\rm\:n\:$ has prime factorizations $\rm\:p\: p_2\cdots p_j = q\:q_2\cdots q_k.$ Note $\rm\:j,k \ge 1\:$ by $\rm\:n > 1.\:$ Inductively applying Euclid's Lemma (below) yields that $\rm\:p\:$ divides one of the $\rm\:q$'s, say $\rm\:p\ |\ q,\:$ so $\rm\:p = q.\:$ Canceling $\rm\:p\:$ from both factorizations yields factorizations of $\rm n/p.\:$ By induction, they are unique up to order. Hence so too are the above factorizations, obtained by appending $\rm\:p.\ \$ QED

Euclid's Lemma $\rm\ \ a,b\:$ coprime, $\rm\ a\: |\: b\:c\ \Rightarrow\ a\: |\: c\ \:$ for all naturals $\rm\: a,b,c > 0\:.$

Proof $\$ For some $\rm\: d \in \mathbb N,\ a\:d\: =\: b\:c\: \Rightarrow\: \dfrac{c}a \: =\: \dfrac{d}b.\:$ Below Theorem $\rm\Rightarrow\: \dfrac{c}a\in\mathbb Z\ \ \$ QED

Theorem $\ \:$ If the rational number $\rm\ r\: =\: \dfrac{c}a\: =\: \dfrac{d}b\$ for coprime $\rm\:a, b\in \mathbb N\:$ then $\rm\: r\:$ is an integer.

Proof $\$ By the symmetry of the hypotheses, we may suppose the notation is chosen so $\rm\: b \ge a\:.\$ First, we prove that if $\rm\ b > a\$ then there is such a representation of $\rm\:r\:$ with smaller value of $\rm\:b\:.\:$ View the fractions as vectors $\rm\:(a,c),\ (b,d)\:$ of slope $\rm\:r.\:$ Subtracting the smallest vector from the largest vector we deduce that $\rm\ r\: =\: \dfrac{c}a\: =\: \dfrac{d-c}{b-a}.\ \:.\phantom{\dfrac{.}{\dfrac{.}.}}\!\!\!\!\!\!\!\!\!\phantom{\dfrac{\dfrac{.}.}{.}}\!\!\!\!\!\!\!\!\!$ This is smaller since both $\rm\:a,\: b-a < b,\:$ and $\rm a,\:b-a\:$ are coprime: $\rm\: c\ |\ a,b\!-\!a\: \Rightarrow\: c\ |\ a+(b\!-\!a) = b\: \Rightarrow\: c\: |\: a,b\:$ so $\rm\: c\: |\: 1\:$ by $\rm\:a,b\:$ coprime.

Of all such representations of $\rm\:r\:$ satisfying the hypotheses, consider one with the least value of $\rm\:b\:.\:$ Necessarily, $\rm\ b\: =\: a\$ (else $\rm\:b > a,\:$ so, by above, there is a representation with smaller value of $\rm\:b$). Therefore $\rm\ a,b\: =\: a,a\$ coprime $\rm\:\Rightarrow\ a = 1\:.\:$ Hence $\rm\ r\: =\: c/a\: =\: c/1\: =\: c\:$ is an integer. $\$ QED

-
I hope that upvote will make it a bit better :) – Belgi Dec 11 '12 at 19:44
by the way: the count say that there are no downvotes... – Belgi Dec 11 '12 at 19:44
@Belgi Thanks for the update, apparently a serial downvoting reversal occurred. But I'm happy to explain even to serial downvoters too! – Bill Dubuque Dec 11 '12 at 20:15