1.11: Unique Factorization

Our goal in this chapter is to prove the following fundamental theorem.

Theorem \(\PageIndex{1}\): The Fundamental Theorem of Arithmetic

Every integer \(n>1\) can be written uniquely in the form \[n=p_1p_2\dotsm p_s,\nonumber\] where \(s\) is a positive integer and \(p_1,p_2,\dotsc,p_s\) are primes satisfying \[p_1\le p_2\le\dotsb\le p_s.\nonumber\]

Remark \(\PageIndex{1}\)

If \(n=p_1p_2\dotsm p_s\) where each \(p_i\) is prime, we call this the prime factorization of \(n\). Theorem \(\PageIndex{1}\) is sometimes stated as follows:

Every integer \(n>1\) can be expressed as a product \(n=p_1p_2\dotsm p_s\), for some positive integer \(s\), where each \(p_i\) is prime and this factorization is unique except for the order of the primes \(p_i\).

Note for example that \[\begin{split} 600 &=2\cdot 2\cdot 2\cdot 3\cdot 5\cdot 5 \\ &=2\cdot 3\cdot 2\cdot 5\cdot 2\cdot 5 \\ &=3\cdot 5\cdot 2\cdot 2\cdot 2\cdot 5 \\ &\quad\text{etc.} \end{split}\]

Perhaps the nicest way to write the prime factorization of \(600\) is \[600=2^3\cdot 3\cdot 5^2.\nonumber\]

In general it is clear that \(n>1\) can be written uniquely in the form

\[\label{eq:1}n=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s},\text{ some }s\geq 1,\]

where \(p_1<p_2<\dotsb<p_s\) and \(a_i\ge 1\) for all \(i\). Sometimes \(\eqref{eq:1}\) is written \[\boxed{n=\prod_{i=1}^s p_i^{a_i}}\,.\nonumber\] Here \(\displaystyle\prod\) stands for product, just as \(\displaystyle\sum\) stands for sum.

To prove Theorem \(\PageIndex{1}\) we need to first establish a few lemmas.

Lemma \(\PageIndex{1}\)

If \(a\mid bc\) and \(\gcd(a,b)=1\) then \(a\mid c\).

Proof

Since \(\gcd(a,b)=1\) by Bezout’s Lemma there are \(s\), \(t\) such that \[1=as+bt.\nonumber\] If we multiply both sides by \(c\) we get \[c=cas+cbt=a(cs)+(bc)t.\nonumber\] By assumption \(a\mid bc\). Clearly \(a\mid a(cs)\) so, by Theorem 3.1, \(a\) divides the linear combination \(a(cs)+(bc)t=c\).

Definition \(\PageIndex{1}\)

We say that \(a\) and \(b\) are relatively prime if \(\gcd(a,b)=1\).

So we may restate Lemma \(\PageIndex{1}\) as follows: If \(a\mid bc\) and \(a\) is relatively prime to \(b\) then \(a\mid c\).

Example \(\PageIndex{1}\)

It is not true generally that when \(a\mid bc\) then \(a\mid b\) or \(a\mid c\). For example, \(6\mid 4\cdot 9\), but \(6\nmid 4\) and \(6\nmid 9\). Note that Lemma \(\PageIndex{1}\) doesn’t apply here since \(\gcd(6,4)\ne 1\) and \(\gcd(6,9)\ne 1\).

Lemma \(\PageIndex{2}\): Euclid's Lemma

If \(p\) is a prime and \(p\mid ab\), then \(p\mid a\) or \(p\mid b\).

Proof

Assume that \(p\mid ab\). If \(p\mid a\) we are done. Suppose \(p\nmid a\). Let \(d=\gcd(p,a)\). Note that \(d>0\) and \(d\mid p\) and \(d\mid a\). Since \(d\mid p\) we have \(d=1\) or \(d=p\). If \(d\ne 1\) then \(d=p\). But this says that \(p\mid a\), which we assumed was not true. So we must have \(d=1\). Hence \(\gcd(p,a)=1\) and \(p\mid ab\). So by Lemma \(\PageIndex{1}\), \(p\mid b\).

Lemma \(\PageIndex{3}\)

Let \(p\) be prime. Let \(a_1,a_2,\dotsc,a_n\), \(n\ge 1\), be integers. If \(p\mid a_1a_2\dotsm a_n\), then \(p\mid a_i\) for at least one \(i\in\{1,2,\dotsc,n\}\).

Proof

We use induction on \(n\). The result is clear if \(n=1\). Assume that the lemma holds for \(n\) such that \(1\le n\le k\). Let’s show it holds for \(n=k+1\). So assume \(p\) is a prime and \(p\mid a_1a_2\dotsm a_ka_{k+1}\). Let \(a=a_1a_2\dotsm a_k\) and \(b=a_{k+1}\). Then \(p\mid a\) or \(p\mid b\) by Lemma \(\PageIndex{2}\). If \(p\mid a=a_1\dotsm a_k\), by the induction hypothesis, \(p\mid a_i\) for some \(i\in\{1,\dotsc,k\}\). If \(p\mid b=a_{k+1}\) then \(p\mid a_{k+1}\). So we can say \(p\mid a_i\) for some \(i\in\{1,2,\dotsc,k+1\}\). So the lemma holds for \(n=k+1\). Hence by PMI it holds for all \(n\ge 1\).

Lemma \(\PageIndex{4}\): Existence Part of Theorem \(\PageIndex{1}\)

If \(n>1\) then there exist primes \(p_1,\dotsc,p_s\) for some \(s\ge 1\) such that \[n=p_1p_2\dotsm p_s\nonumber\] and \(p_1\le p_2\le\dotsb\le p_s\).

Proof

Proof by induction on \(n\), with starting value \(n=2\): If \(n=2\) then since \(2\) is prime we can take \(p_1=2\), \(s=1\). Assume the lemma holds for \(n\) such that \(2\le n\le k\). Let’s show it holds for \(n=k+1\). If \(k+1\) is prime we can take \(s=1\) and \(p_1=k+1\) and we are done. If \(k+1\) is composite we can write \(k+1=ab\) where \(1<a<k+1\) and \(1<b<k+1\). By the induction hypothesis there are primes \(p_1,\dotsc,p_u\) and \(q_1,\dotsc,q_v\) such that \[a=p_1\dotsm p_u\text{ and }b=q_1\dotsm q_v.\nonumber\] This gives us \[k+1=ab=p_1p_2\dotsm p_uq_1q_2\dotsm q_v,\nonumber\] that is \(k+1\) is a product of primes. Let \(s=u+v\). By reordering and relabeling where necessary we have \[k+1=p_1p_2\dotsm p_s\nonumber\] where \(p_1\le p_2\le\dotsb\le p_s\). So the lemma holds for \(n=k+1\). Hence by PMI, it holds for all \(n>1\).

Lemma \(\PageIndex{5}\): Uniqueness Part of Theorem \(\PageIndex{1}\)

Let \[n=p_1p_2\dotsm p_s \mbox{ for some } s\ge 1,\nonumber\] and \[n=q_1q_2\dotsm q_t \mbox{ for some } t\ge 1,\nonumber\] where \(p_1,\dotsc,p_s,q_1,\dotsc,q_t\) are primes satisfying \[p_1\le p_2\le\dotsb\le p_s\nonumber\] and \[q_1\le q_2\le\dotsb\le q_t.\nonumber\] Then, \(t=s\) and \(p_i=q_i\) for \(i=1,2,\dotsc,t\).

Proof

Our proof is by induction on \(s\). Suppose \(s=1\). Then \(n=p_1\) is prime and we have \[p_1=n=q_1q_2\dotsm q_t.\nonumber\] If \(t>1\), this contradicts the fact that \(p_1\) is prime. So \(t=1\) and we have \(p_1=q_1\), as desired. Now assume the result holds for all \(s\) such that \(1\le s\le k\). We want to show that it holds for \(s=k+1\). So assume \[n=p_1p_2\dotsm p_kp_{k+1}\nonumber\] and \[n=q_1q_2\dotsm q_t\nonumber\] where \(p_1\le p_2\le\dotsb\le p_{k+1}\) and \(q_1\le q_2\le\dotsb\le q_t\). Clearly \(p_{k+1}\mid n\) so \(p_{k+1}\mid q_1\dotsm q_t\). So by Lemma \(\PageIndex{3}\) \(p_{k+1}\mid q_i\) for some \(i\in\{1,2,\dotsc,t\}\). It follows from Exercise 10.9 that \(p_{k+1}=q_i\). Hence \(p_{k+1}=q_i\le q_t\).

By a similar argument \(q_t\mid n\) so \(q_t\mid p_1\dotsm p_{k+1}\) and \(q_t=p_j\) for some \(j\). Hence \(q_t=p_j\le p_{k+1}\). This shows that \[p_{k+1}\le q_t\le p_{k+1}\nonumber\] so \(p_{k+1}=q_t\). Note that \[p_1p_2\dotsm p_kp_{k+1}=q_1q_2\dotsm q_{t-1}q_t\nonumber\] Since \(p_{k+1}=q_t\) we can cancel this prime from both sides and we have \[p_1p_2\dotsm p_k=q_1q_2\dotsm q_{t-1}.\nonumber\] Now by the induction hypothesis \(k=t-1\) and \(p_i=q_i\) for \(i=1,\dotsc,t-1\). Thus we have \(k+1=t\) and \(p_i=q_i\) for \(i=1,2,\dotsc,t\). So the lemma holds for \(s=k+1\) and by the PMI, it holds for all \(s\ge 1\).

Now the proof of Theorem \(\PageIndex{1}\) follows immediately from Lemma \(\PageIndex{4}\) and Lemma \(\PageIndex{5}\).

Remark \(\PageIndex{2}\)

If \(a\) and \(b\) are positive integers we can find primes \(p_1,\dotsc,p_k\) and integers \(a_1,\dotsc,a_k,b_1,\dotsc,b_k\) each \(\ge 0\) such that \[\label{eq:2} \begin{cases} a=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k} \\ b=p_1^{b_1}p_2^{b_2}\dotsm p_k^{b_k} \end{cases} \] For example, if \(a=600\) and \(b=252\) we have \[\begin{aligned} 600 &=2^3\cdot 3^1\cdot 5^2\cdot 7^0 \\ 252 &=2^2\cdot 3^2\cdot 5^0\cdot 7.\end{aligned}\] It follows that \[\gcd(600,252)=2^2\cdot 3^1\cdot 5^0\cdot 7^0.\nonumber\] In general, if \(a\) and \(b\) are given by \(\eqref{eq:2}\) we have \[\boxed{\gcd(a,b)=p_1^{\min(a_1,b_1)}p_2^{\min(a_2,b_2)}\cdots p_k^{\min (a_k,b_k)}}\,.\nonumber\] This gives one way to calculate the gcd provided you can factor both numbers. But generally speaking factorization is very difficult! On the other hand, the Euclidean algorithm is relatively fast.

Exercise \(\PageIndex{1}\)

Find the prime factorizations of \(1147\) and \(1716\) by trying all primes \(p\le\sqrt{1147}\) (\(p\le\sqrt{1716}\)) in succession.