1.11: Unique Factorization (2024)

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.

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\).

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\).