I have read right from school that prime factorization is unique, but have never found proof for this. Can someone show me the proof?
How can we prove that among positive integers any number can have only one prime factorization?
-
1I think this may be relevant: prime factorization is not unique for certain representations. For example, if you include all complex numbers of the form $a+ib\sqrt{5}$ where $a,b$ are integers. But presumably you are referring to the case of only integers, which does have unique factorization. – 2012-12-13
4 Answers
Below is a direct elementary proof of the Fundamental Theorem of Arithmetic from first principles. Similar proofs were given by Hasse, Klappauf, Lindemann, and Zermelo (circa 1912).
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
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.
-
0"Link only" answer. ${}{}$ – 2018-01-07
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
-
0@Belgi Thanks for the update, apparently a serial downvoting reversal occurred. But I'm happy to explain even to serial downvoters too! – 2012-12-11