1.12: Unique Factorization
- Page ID
- 83347
Our goal in this chapter is to prove the following fundamental theorem.
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 \]
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 \[n=p_1^{a_1}p_2^{a_2}\dotsm p_s^{a_s}\text{, some }s\ge 1,\nonumber \] where \(p_1<p_2<\dotsb<p_s\) and \(a_i\ge 1\) for all \(i\). Sometimes the product is written as \[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.
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 1.4.1, \(a\) divides the linear combination \(a(cs)+(bc)t=c\).
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\).
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\).
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\).
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 number of integers multiplied in the product. 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\).
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\).
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 1.11.3 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 Lemmas \(\PageIndex{4}\) and \(\PageIndex{5}\).
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{eq11-2ast} \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^1.\end{aligned}\] It follows that \[\gcd(600,252)=2^2\cdot 3^1\cdot 5^0\cdot 7^0 \quad \text{ and } \quad \operatorname{lcm}(600,252)=2^3\cdot 3^2\cdot 5^2\cdot 7^1.\nonumber \] In general, if \(a\) and \(b\) are given by equations \(\eqref{eq11-2ast}\) it can be proved that \[\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 \] and \[\boxed{\operatorname{lcm}(a,b)=p_1^{\max(a_1,b_1)}p_2^{\max(a_2,b_2)}\cdots p_k^{\max (a_k,b_k)}}\nonumber \] (try it!). This gives one way to calculate the gcd or lcm provided you can factor both numbers. But generally speaking factorization is very difficult! On the other hand, the Euclidean algorithm is relatively fast.
Exercises
Find the prime factorizations of \(1147\) and \(1716\) by trying all primes \(p\le\sqrt{1147}\) (\(p\le\sqrt{1716}\)) in succession.
Determine the prime factorization of \(15! = 1307674368000\).
- Using the prime factorization of \(100!\), determine how many 0’s appear at the end of the base 10 representation.
- How many 0’s appear at the end of the binary representation of \(100!\) ?
The prime factorization of an integer \(n\) expresses \(n\) as the product of one or more prime numbers, and by the Fundamental Theorem of Arithmetic, the factorization is unique when the primes are ordered by size.
Let’s examine the idea of factorizations in a different set. Let \(S\) be the set of all positive multiples of 3. For each \(n \in S\), define \(n\) to be \(S\)-prime if \(n\) cannot be written as the product of two smaller elements of \(S\).
- Write down the 10 smallest \(S\)-prime integers.
- Find a factorization of \(18\) into \(S\)-prime numbers.
- Explain how we know that every element of \(S\) can be written as the product of one or more \(S\)-prime numbers.
- Is the factorization of an element of \(S\) into \(S\)-prime units unique? If so, explain why. If not, give an example of an element of \(S\) that can be factored into \(S\)-prime numbers in at least two different ways (along with the two factorizations).
Let \(\mathbb{N}^*\) be the set \(\{4,5,6,7,\dots\}\). This set \(\mathbb{N}^*\) would the set of positive integers if for some reason we changed our mind and declared that \(1,2,3\) were not integers.
- If we define a number in \(\mathbb{N}^*\) to be “ prime\(^*\) ” if it cannot be written as a product of two or more smaller elements in \(\mathbb{N}^*\), then which numbers from the set \(\{4,5,\dots,25\}\) are prime\(^*\)?
- Express \(32\) as the product of two prime\(^*\) numbers.
- Find a number in \(\mathbb{N}^*\) that can be written as a product of prime\(^*\) numbers in at least two different ways. (As an additional challenge, try to find the smallest such number.)
Most students have seen the Fundamental Theorem of Arithmetic so long ago that it seems somehow obvious or unremarkable. Based on the previous two exercises, do you think that Theorem \(\PageIndex{1}\) is at all surprising? Explain your answer in at least a short paragraph.
Footnotes
[1] This result is proved in Proposition 30 of Book VII of Euclid's Elements.