Problem 6.2. According to our definition, is 1 a prime number or composite number? Explain your answer. You may have heard prime numbers defined as something like, “a prime number is a natural number that is only divisible by 1 and itself." Does this definition agree with the one above?
The upshot is that according to our definition, 1 is neither prime nor composite. However, throughout history, this has not always been the case. There were times when and mathematicians for whom the number one was considered prime. Whether 1 is prime or not is a matter of definition, and hence a matter of choice. There are compelling reasons—that we will not elaborate on here—why 1 is intentionally excluded from being prime. However, if you would like to learn more, check out the excellent article “What is the Smallest Prime?" by Chris Caldwell and Yeng Xiong.
Problem 6.3. List the first 10 prime numbers.
Problem 6.4. Prove or provide a counterexample: For all \(n\in\mathbb\) , if \(4^n-1\) is prime, then \(n\) is odd.
Problem 6.5. Prove or provide a counterexample: For all \(n\in\mathbb\) , \(n^2-n+11\) is prime.
The next result makes up half of the Fundamental Theorem of Arithmetic. We provide a substantial hint for its proof. Let \(S\) be the set of natural numbers for which the theorem fails. For sake of a contradiction, assume \(S\neq \emptyset\) . By the Well-Ordering Principle (Theorem 4.38), \(S\) contains a least element, say \(n\) . Then \(n\) cannot be prime since this would satisfy the theorem. So, it must be the case that \(n\) has a divisor other than 1 and itself. This implies that there exists natural numbers \(a\) and \(b\) greater than 1 such that \(n=ab\) . Since \(n\) was our smallest counterexample, what can you conclude about both \(a\) and \(b\) ? Use this information to derive a counterexample for \(n\) .
Theorem 6.6. If \(n\) is a natural number greater than 1, then \(n\) can be expressed as a product of primes. That is, we can write \[n=p_1 p_2 \cdots p_k,\] where each of \(p_1, p_2, \ldots, p_k\) is a prime number (not necessarily distinct).
Theorem 6.6 states that we can write every natural number greater than 1 as a product of primes, but it does not say that the primes and the number of times each prime appears are unique. To prove uniqueness, we will need Euclid’s Lemma (Theorem 6.15). To prove Euclid’s Lemma, we will utilize a special case of Bézout’s Lemma (Theorem 6.13), the proof of which relies on the following result, known as the Division Algorithm. We include the proof of the Division Algorithm below, which makes use of the Well-Ordering Principle (Theorem 4.38).
Theorem 6.7. If \(n,d\in\mathbb\) such that \(d>0\) , then there exists unique \(q,r\in\mathbb\) such that \(n=dq+r\) with \(0\leq r
Let \(n,d\in\mathbb\) such that \(d>0\) such that \(n>0\) . We have two tasks. First, we need to show that \(q\) and \(r\) exist, and then we need to show that both are unique.
If \(d=1\) , it is clear that we can take \(q=n\) and \(r=0\) , so that \(n=1\cdot n+0=dq+r\) , as desired. Now, assume that \(d>1\) and define \[S:= \
First, suppose \(n\geq 0\) . If we take \(k=0\) , then we get \(n-dk=n-d\cdot 0=n\geq 0\) , which shows that \(n\in S\) .
In the Division Algorithm, we call \(n\) the dividend, \(d\) the divisor, \(q\) the quotient, and \(r\) the remainder. It is worth pointing out that the Division Algorithm holds more generally where the divisor \(d\) is not required to be positive. In this case, we must replace \(0\leq r
Contrary to its name, our statement of the Division Algorithm is not actually an algorithm, but this is the theorem’s traditional name. However, there is an algorithm buried in this theorem. If \(n\) is nonnegative, repeatedly subtract \(d\) from \(n\) until we obtain an integer value that lies between 0 (inclusive) and \(d\) (exclusive). The resulting value is the remainder \(r\) while the number of times that \(d\) is subtracted is the quotient \(q\) . On the other hand, if \(n\) is negative, repeatedly add \(d\) to \(n\) until we obtain an integer value that lies between 0 (inclusive) and \(d\) (exclusive). Again, the resulting value is \(r\) . However, in this case, we take \(-q\) to be the number of times that \(d\) is added, so that \(q\) (a negative value) is the quotient.
Problem 6.8. Suppose \(n=27\) and \(d=5\) . Find the quotient and remainder that are guaranteed to exist by the Division Algorithm. That is, find the unique \(q,r\in\mathbb\) such that \(0\leq r
It is a little trickier to determine \(q\) and \(r\) when \(n\) is negative.
Problem 6.9. Suppose \(n=-26\) and \(d=3\) . Find the quotient and remainder that are guaranteed to exist by the Division Algorithm. That is, find the unique \(q,r\in\mathbb\) such that \(0\leq r
It is useful to have some additional terminology.
Definition 6.10. Let \(m,n\in\mathbb\) such that at least one of \(m\) or \(n\) is nonzero. The greatest common divisor (gcd) of \(m\) and \(n\) , denoted \(\gcd(m,n)\) , is the largest positive integer that divides both \(m\) and \(n\) . If \(\gcd(m,n)=1\) , we say that \(m\) and \(n\) are relatively prime.
Problem 6.11. Find \(\gcd(54,72)\) .
Problem 6.12. Provide an example of two natural numbers that are relatively prime.
The next result is a special case of a theorem known as Bézout’s Lemma (or Bézout’s Identity). Ultimately, we will need this theorem to prove Euclid’s Lemma (Theorem 6.15), which we then use to prove uniqueness for the Fundamental Theorem of Arithmetic (Theorem 6.17). To prove our special case of Bézout’s Lemma, consider the set \(S:= \ 0\mid s,t\in \mathbb\>\) . First, observe that \(p\in S\) (choose \(s=1\) and \(t=0\) ). It follows that \(S\) is nonempty. By the Well-Ordering Principle (Theorem 4.38), \(S\) contains a least element, say \(d\) . This implies that there exists \(s_1,t_1\in \mathbb\) such that \(d=ps_1+at_1\) . Our goal is to show that \(d=1\) . Now, choose \(m\in S\) . Then there exists \(s_2,t_2\in \mathbb\) such that \(m=ps_2+at_2\) . By the definition of \(d\) , we know \(d\leq m\) . By the Division Algorithm, there exists unique \(q,r\in \mathbb\cup\\) such that \(m=qd+r\) with \(0\leq r < d\) . Now, solve for \(r\) and then replace \(m\) and \(d\) with \(ps_1+at_1\) and \(ps_2+at_2\) , respectively. You should end up with an expression for \(r\) involving \(p, a, s_1, s_2, t_1\) , and \(t_2\) . Next, rearrange this expression to obtain \(r\) as a linear combination of \(p\) and \(a\) (i.e., a sum of a multiple of \(p\) and a multiple of \(a\) ). What does the minimality of \(d\) imply about \(r\) ? You should be able to conclude that \(m\) is a multiple of \(d\) . That is, every element of \(S\) is a multiple of \(d\) . However, recall that \(p\in S\) , \(p\) is prime, and \(p\) and \(a\) are relatively prime. What can you conclude about \(d\) ?
Theorem 6.13. If \(p,a\in\mathbb\) such that \(p\) is prime and \(p\) and \(a\) are relatively prime, then there exists \(s,t\in\mathbb\) such that \(ps+at=1\) .
Problem 6.14. Consider the natural numbers 2 and 7, which happen to be relatively prime. Find integers \(s\) and \(t\) guaranteed to exist according to Theorem 6.13. That is, find \(s,t\in\mathbb\) such that \(2s+7t=1\) .
The following theorem is known as Euclid’s Lemma. Note that if \(p\) divides \(a\) , the conclusion is certainly true. So, assume otherwise. That is, assume that \(p\) does not divide \(a\) , so that \(p\) and \(a\) are relatively prime. Apply Theorem 6.13 to \(p\) and \(a\) and then multiply the resulting equation by \(b\) . Try to conclude that \(p\) divides \(b\) .
Theorem 6.15. Assume that \(p\) is prime. If \(p\) divides \(ab\) , where \(a,b\in\mathbb\) , then either \(p\) divides \(a\) or \(p\) divides \(b\) .
In Euclid’s Lemma, it is crucial that \(p\) is prime as illustrated by the next problem.
Problem 6.16. Provide an example of integers \(a, b, d\) such that \(d\) divides \(ab\) yet \(d\) does not divide \(a\) and \(d\) does not divide \(b\) .
Alright, we are finally ready to tackle the proof of the Fundamental Theorem of Arithmetic. Let \(n\) be a natural number greater than 1. By Theorem 6.6, we know that \(n\) can be expressed as a product of primes. All that remains is to prove that this product is unique (up to the order in which they appear). For sake of a contradiction, suppose \(p_1 p_2 \cdots p_k\) and \(q_1 q_2 \cdots q_l\) are both prime factorizations of \(n\) . Your goal is to prove that \(k=l\) and that each \(p_i\) is equal to some \(q_j\) . Make repeated use of Euclid’s Lemma.
Theorem 6.17. Every natural number greater than 1 can be expressed uniquely (up to the order in which they appear) as the product of one or more primes.
The Fundamental Theorem of Arithmetic is one of the many reasons why 1 is not considered a prime number. If 1 were prime, prime factorizations would not be unique.
This page titled 6.1: The Fundamental Theorem of Arithmetic is shared under a CC BY-SA 4.0 license and was authored, remixed, and/or curated by Dana Ernst via source content that was edited to the style and standards of the LibreTexts platform.
