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

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

• en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic Commented Feb 27, 2012 at 5:25
• 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.... Commented Feb 27, 2012 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? Commented Feb 27, 2012 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! Commented Feb 27, 2012 at 7:31
• I 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. Commented Dec 13, 2012 at 6:00

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

Remark  This inductive argument can be presented more clearly by abstracting it out into an inductive proof of Euclid's Lemma e.g. as here (or similar variations).

• 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. Commented Jun 7, 2013 at 6:28
• For another example of such direct inductive proofs see this proof of prime $\,p\mid ab\,\Rightarrow\,p\mid a\ {\rm or}\ p\mid b\,$ where gcd structure has been eliminated, unwound into its primitive constituents of repeated subtraction and induction. Commented Jul 16, 2017 at 15:51
• @BillDubuque The most elementary property of integers: every $n \gt 1$ has a least (unique) factor $p \ne 1$. Simply a matter of working around that to get the FTA. (I was close to getting this proof in my work) Commented May 22, 2019 at 1:37

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.

• "Link only" answer. ${}{}$ Commented Jan 7, 2018 at 15:24

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 $$\,p,q\,$$ is representable with denominator $$\,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 $$\,n>1\,$$ are unique up to order.

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

Euclid's Lemma $$\ \ \gcd(a,b)=1,\,\ a\, |\, b\,c\ \Rightarrow\ a\, |\, c\ \,$$ for all naturals $$\, a,b,c > 0$$.

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

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

Proof $$\,$$ If not then choose a counterexample of least size $$:= a\!+\!b.\,$$ Note $$\,a\neq b\,$$ (since $$\,a\!=\!b\,$$ and $$a,b$$ coprime $$\Rightarrow a=1\Rightarrow r\in\Bbb Z),\,$$ so wlog $$\,a< b.\,$$ Subtracting $$\,ar = c\,$$ from $$\,br = d\,$$ yields $$\, (b\!-\!a)r = d\!-\!c,\,$$ so $$\,r = (d\!-\!c)/(b\!-\!a)\,$$ with $$\,\gcd(a,b\!-\!a) = \gcd(a,b)=1,\,$$ so we have a counterexample $$\, r = c/a = (d-c)/(b-a)\,$$ of smaller size $$\, a\!+\!(b\!-\!a)\!=\!b < a\!+\!b$$ $$\,\Rightarrow\!\Leftarrow$$

Remark  The proof does not require gcds. We use $$\,\gcd(a,b)=1\,$$ only as notation for $$\,a,b\,$$ coprime, to make it clear that this implies that $$\,a,b\!-\!a\,$$ are also coprime (being a special case of the well-known law $$\,\gcd(a,b-na) = \gcd(a,b),\,$$ whose proof follows immediately from divisibility laws). We could specialize that proof to directly prove $$\,a,b\,$$ coprime $$\Rightarrow\,a,b\!-\!a\,$$ coprime, then eliminate all uses of "gcd", but that would be conceptually less clear. For completeness let's do that. If $$\,n\mid a,b\!-\!a\,$$ then $$\,n\mid a\!+\!(b\!-\!a)=b,\,$$ so $$\,n\,$$ divides the coprimes $$\,a,b\,$$ so $$\,n=1$$.

• I hope that upvote will make it a bit better :) Commented Dec 11, 2012 at 19:44
• by the way: the count say that there are no downvotes... Commented Dec 11, 2012 at 19:44
• See here for existence of prime factorizations, and see here for other proofs of Euclid's Lemma. Commented Jun 1, 2023 at 4:50