8.2: Prime Numbers and Prime Factorizations

Preview Activity \(\PageIndex{1}\): Exploring Examples where \(a\) Divides \(b \cdot c\)

1. Find at least three different examples of nonzero integers \(a\), \(b\), and \(c\) such that \(a\ |\ (bc)\) but a does not divide \(b\) and \(a\) does not divide \(c\). In each case, compute gcd(\(a\), \(b\)) and gcd(\(a\), \(c\)).
2. Find at least three different examples of nonzero integers \(a\), \(b\), and \(c\) such that gcd(\(a\), \(b\)) = 1 and \(a\ |\ (bc)\). In each example, is there any relation between the integers \(a\) and \(c\)?
3. Formulate a conjecture based on your work in Parts (1) and (2).

Preview Activity \(\PageIndex{2}\): Prime Factorizations

Recall that a natural number \(p\) is a prime number provided that it is greater than 1 and the only natural numbers that divide \(p\) are 1 and \(p\). A natural number other than 1 that is not a prime number is a composite number. The number 1 is neither prime nor composite. (See Exercise 13 from Section 2.4 on page 78.)

1. Give examples of four natural numbers that are prime and four natural numbers that are composite.

Theorem 4.9 in Section 4.2 states that every natural number greater than 1 is either a prime number or a product of prime numbers. When a composite number is written as a product of prime numbers, we say that we have obtained a prime factorization of that composite number. For example, since \(60 = 2^2 \cdot 3 \cdot 5\), we say that \(2^2 \cdot 3 \cdot 5\) is a prime factorization of 60.

2. Write the number 40 as a product of prime numbers by first writing \(40 = 2 \cdot 20\) and then factoring 20 into a product of primes. Next, write the number 40 as a product of prime numbers by first writing \(40 = 5 \cdot 8\) and then factoring 8 into a product of primes.
3. In Part (2), we used two different methods to obtain a prime factorization of 40. Did these methods produce the same prime factorization or different prime factorizations? Explain.
4. Repeat Parts (2) and (3) with 150. First, start with \(150 = 3 \cdot 50\), and then start with \(150 = 5 \cdot 30\).

Greatest Common Divisors and Linear Combinations

In Section 8.1, we introduced the concept of the greatest common divisor of two integers. We showed how the Euclidean Algorithm can be used to find the greatest common divisor of two integers, \(a\) and \(b\), and also showed how to use the results of the Euclidean Algorithm to write the greatest common divisor of \(a\) and \(b\) as a linear combination of \(a\) and \(b\).

In this section, we will use these results to help prove the so-called Fundamental Theorem of Arithmetic, which states that any natural number greater than 1 that is not prime can be written as product of primes in “essentially” only one way. This means that given two prime factorizations, the prime factors are exactly the same, and the only difference may be in the order in which the prime factors are written. We start with more results concerning greatest common divisors. We first prove Proposition 5.16, which was part of Exercise (18) in Section 5.2 and Exercise (8) in Section 8.1.

Theorem 5.16

Let \(a\), \(b\), and \(t\) be integers with \(t \ne 0\). If \(t\) divides \(a\) and \(t\) divides \(b\), then for all integers \(x\) and \(y\), \(t\) divides \((ax + by)\).

Proof

Let \(a\), \(b\), and \(t\) be integers with \(t \ne 0\), and assuem that \(t\) divides \(a\) and \(t\) divides \(b\). We will prove that for all integers \(x\) and \(y\), \(t\) divides \((ax + by)\).

So let \(x \in \mathbb{Z}\) and let \(y \in \mathbb{Z}\). Since \(t\) divides \(a\), there exists an integer \(m\) such that \(a = mt\) and since \(t\) divides \(b\), there exists an integer \(n\) such that \(b = nt\). Using substitution and algebra, we then see that

\[\begin{array} {rcl} {ax + by} &= & {(mt) x + (nt) y} \\ {} &= & {t(mx + ny)} \end{array}\]

Since \((mx + ny\)) is an integer, the last equation proves that \(t\) divides \(ax + by\) and this proves that for all integers \(x\) and \(y\), \(t\) divides \((ax + by)\).

We now let \(a, b \in \mathbb{Z}\), not both 0, and let \(d = \text{gcd}(a, b)\). Theorem 8.8 states that d can be written as a linear combination of \(a\) and \(b\). Now, since \(d\ |\ a\) and \(d\ |\ b\), we can use the result of Proposition 5.16 to conclude that for all \(x, y \in \mathbb{Z}\), \(d\ |\ (ax + by)\). This means that \(d\) divides every linear combination of \(a\) and \(b\). In addition, this means that \(d\) must be the smallest positive number that is a linear combination of \(a\) and \(b\). We summarize these results in Theorem 8.9.

Theorem 8.9.

Let \(a, b \in \mathbb{Z}\), not both 0.

1. The greatest common divisor, \(d\), is a linear combination of \(a\) and \(b\). That is, there exist integers \(m\) and \(n\) such that \(d = am + bn\).
2. The greatest common divisor, \(d\), divides every linear combination of \(a\) and \(b\). That is, for all \(x, y \in \mathbb{Z}\), \(d\ |\ (ax + by)\).
3. The greatest common divisor, \(d\), is the smallest positive number that is a linear combination of \(a\) and \(b\).

Relatively Prime Integers

In Preview Activity \(\PageIndex{1}\), we constructed several examples of integers \(a\), \(b\), and \(c\) such that \(a\ |\ (bc)\) but \(a\) does not divide \(b\) and \(a\) does not divide \(c\). For each example, we observed that \(\text{gcd}(a, b) \ne 1\) and \(\text{gcd}(a, c) \ne 1\).

We also constructed several examples where \(a\ |\ (bc)\) and \(\text{gcd}(a, b) = 1\). In all of these cases, we noted that \(a\) divides \(c\). Integers whose greatest common divisor is equal to 1 are given a special name.

Definition: relatively prime

Two nonzero integers \(a\) and \(b\) are relatively prime provided that \(\text{gcd}(a, b) = 1\).

Progress Check 8.10: Relatively Prime Integers

1. Construct at least three different examples where \(p\) is a prime number, \(a \in \mathbb{Z}\), and \(p\ |\ a\). In each example, what is gcd(\(a\), \(p\))? Based on these examples, formulate a conjecture about gcd(\(a\), \(p\)) when \(p\ |\ a\).
2. Construct at least three different examples where \(p\) is a prime number, \(a \in \mathbb{Z}\), and \(p\) does not divide \(a\). In each example, what is gcd(\(a, p\))? Based on these examples, formulate a conjecture about gcd(\(a\), \(p\)) when \(p\) does not divide \(a\).
3. Give at least three different examples of integers \(a\) and \(b\) where a is not prime, \(b\) is not prime, and \(\text{gcd}(a, b) = 1\), or explain why it is not possible to construct such examples.

Answer

Add texts here. Do not delete this text first.

Theorem 8.11.

Let \(a\) and \(b\) be nonzero integers, and let \(p\) be a prime number.

1. If \(a\) and \(b\) are relatively prime, then there exist integers \(m\) and \(n\) such that \(am + bn = 1\). That is, 1 can be written as linear combination of \(a\) of \(b\).
2. If \(p\ |\ a\), then \(\text{gcd}(a, p) = p\).
3. If \(p\) does not divide \(a\), then \(\text{gcd}(a, p) = 1\).

Part (1) of Theorem 8.11 is actually a corollary of Theorem 8.9. Parts (2) and (3) could have been the conjectures you formulated in Progress Check 8.10. The proofs are included in Exercise (1).

Given nonzero integers a and b, we have seen that it is possible to use the Euclidean Algorithm to write their greatest common divisor as a linear combination of \(a\) and \(b\). We have also seen that this can sometimes be a tedious, time-consuming process, which is why people have programmed computers to do this. Fortunately, in many proofs of number theory results, we do not actually have to construct this linear combination since simply knowing that it exists can be useful in proving results. This will be illustrated in the proof of Theorem 8.12, which is based on work in Preview Activity \(\PageIndex{1}\).

Theorem 8.12

Let \(a\), \(b\), be nonzero integers and let \(c\) be an integer. If \(a\) and \(b\) are relatively prime and \(a\ |\ (bc)\), then \(a\ |\ c\)

The explorations in Preview Activity \(\PageIndex{1}\) were related to this theorem. We will first explore the forward-backward process for the proof. The goal is to prove that \(a\ |\ c\). A standard way to do this is to prove that there exists an integer \(q\) such that

\[c = aq.\]

Since we are given \(a\ |\ (bc)\), there exists an integer \(k\) such that

\[bc = ak.\]

It may seem tempting to divide both sides of Equation \ref{8.2.3} by \(b\), but if we do so, we run into problems with the fact that the integers are not closed under division. Instead, we look at the other part of the hypothesis, which is that \(a\) and \(b\) are relatively prime. This means that \(\text{gcd}(a, b) = 1\). How can we use this? This means that \(a\) and \(b\) have no common factors except for 1. In light of Equation \ref{8.2.3}, it seems reasonable that any factor of \(a\) must also be a factor of \(c\). But how do we formalize this?

One conclusion that we can use is that since \(\text{gcd}(a, b) = 1\), by Theorem 8.11, there exist integers \(m\) and \(n\) such that

\[am + bn = 1.\]

We may consider solving equation (8.2.4) for \(b\) and substituting this into Equation \ref{8.2.3}. The problem, again, is that in order to solve Equation \ref{8.2.4} for \(b\), we need to divide by \(n\).

Before doing anything else, we should look at the goal in Equation \ref{8.2.2}. We need to introduce c into Equation \ref{8.2.4}. One way to do this is to multiply both sides of equation (8.2.4) by \(c\). (This keeps us in the system of integers since the integers are closed under multiplication.) This gives

\[\begin{array} {rcl} {(am + bn) c} &= & {1 \cdot c} \\ {acm + bcn} &= & {c.} \end{array}\]

Notice that the left side of Equation \ref{8.2.5} contains a term, \(bcn\), that contains \(bc\). This means that we can use Equation \ref{8.2.3} and substitute bc D ak in Equation \ref{8.2.5}. After doing this, we can factor the left side of the equation to prove that \(a\ |\ c\).

Progress Check 8.13: Completing the Proof of Theorem 8.12

Write a complete proof of Theorem 8.12.

Answer

Add texts here. Do not delete this text first.

Corollary 8.14

1. Let \(a, b \in \mathbb{Z}\), and let \(p\) be a prime number. If \(p\ |\ (ab)\), then \(p\ |\ a\) or \(p\ |\ b\).
2. Let \(p\) be a prime number, let \(n \in \mathbb{N}\), and let \(a_1, a_2, ..., a_n \in \mathbb{Z}\). If \(p\ |\ (a_{1}a_{2}\cdot\cdot\cdot a_{n})\), then there exists a natural number \(k\) with \(1 \le k \le n\) such that \(p\ |\ a_{k}\).

Part (1) of Corollary 8.14 is a corollary of Theorem 8.12. Part (2) is proved using mathematical induction. The basis step is the case where \(n = 1\), and Part (1) is the case where \(n = 2\). The proofs of these two results are included in Exercises (2) and (3).

Historical Note: Euclid’s Lemma

Part (1) of Corollary 8.14 is known as Euclid’s Lemma. Most people associate geometry with Euclid’s Elements, but these books also contain many basic results in number theory. Many of the results that are contained in this section appeared in Euclid’s Elements.

Prime Numbers and Prime Factorizations

We are now ready to prove the Fundamental Theorem of Arithmetic. The first part of this theorem was proved in Theorem 4.9 in Section 4.2. This theorem states that each natural number greater than 1 is either a prime number or is a product of prime numbers. Before we state the Fundamental Theorem of Arithmetic, we will discuss some notational conventions that will help us with the proof. We start with an example.

We will use \(n = 120\). Since \(5\ |\ 120\), we can write \(120 = 5 \cdot 24\). In addition, we can factor 24 as \(24 = 2 \cdot 2 \cdot 2 \cdot 3\). So we can write

\[\begin{array} {rcl} {120} &= & {5 \cdot 24} \\ {} &= & {5(2 \cdot 2 \cdot 2 \cdot 3).} \end{array}\]

This is a prime factorization of 120, but it is not the way we usually write this factorization. Most often, we will write the prime number factors in ascending order. So we write

\(120 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5\) or \(120 = 2^{3} \cdot 3 \cdot 5\).

Now, let \(n \in \mathbb{N}\). To write the prime factorization of \(n\) with the prime factors in ascending order requires that if we write \(n = p_{1}p_{2}\cdot\cdot\cdot p_{r}\), where \(p_{1}p_{2}\cdot\cdot\cdot p_{r}\) are prime numbers, we will have \(p_{1} \le p_{2} \le \cdot\cdot\cdot \le p_{r}\).

Theorem 8.15: The Fundamental Theorem of Arithmetic

1. Each natural number greater than 1 is either a prime number or is a product of prime numbers.
2. let \(n \in \mathbb{N}\) with \(n > 1\). Assume that
   \[n = p_{1}p_{2}\cdot\cdot\cdot p_{r} \text{ and that } n = q_{1}q_{2}\cdot\cdot\cdot q_{s},\]
   where \(p_{1}p_{2}\cdot\cdot\cdot p_{r}\) and \(q_{1}q_{2}\cdot\cdot\cdot q_{s}\) are prime with \(p_{1} \le p_{2} \le \cdot\cdot\cdot \le p_{r}\) and \(q_{1} \le q_{2} \le \cdot\cdot\cdot \le q_{s}\). Then \(r = s\), and for each \(j\) from 1 to \(r\), \(p_{j} = q{j}\).

Proof

The first part of this theorem was proved in Theorem 4.9. We will prove the second part of the theorem by induction on \(n\) using the Second Principle of Mathematical Induction. (See Section 4.2.) For each natural number \(n\) with \(n > 1\), let \(P(n)\) be

If \(n = p_{1}p_{2}\cdot\cdot\cdot p_{r}\) and \(n = q_{1}q_{2}\cdot\cdot\cdot q_{s}\), where \(p_{1}p_{2}\cdot\cdot\cdot p_{r}\) and \(q_{1}q_{2}\cdot\cdot\cdot q_{s}\) are primes with \(p_{1} \le p_{2} \le \cdot\cdot\cdot \le p_{r}\) and \(q_{1} \le q_{2} \le \cdot\cdot\cdot \le q_{s}\), then \(r = s\), and for each \(j\) from 1 to \(r\), \(p_{j} = q{j}\).

For the basis step, we notice that since 2 is a prime number, its only factorization is \(2 = 1 \cdot 2\). This means that the only equation of the form \(n = p_{1}p_{2}\cdot\cdot\cdot p_{r}\), where \(p_{1}p_{2}\cdot\cdot\cdot p_{r}\) are prime numbers, is the case where \(r = 1\) and \(p_1 = 2\).This proves that \(P(2)\) is true.

For the inductive step, let \(k \in \mathbb{N}\) with \(k \ge 2\). We will assume that \(P(2), P(3), ..., P(k)\) are true. The goal now is to prove that \(P(k + 1)\) is true. To prove this, we assume that \((k + 1)\) has two prime factorizations and then prove that these prime factorizations are the same. So we assume that

\(k + 1 = p_{1}p_{2}\cdot\cdot\cdot p_{r}\) and that \(k + 1 = q_{1}q_{2}\cdot\cdot\cdot q_{s}\), wher \(p_{1}p_{2}\cdot\cdot\cdot p_{r}\) and \(q_{1}q_{2}\cdot\cdot\cdot q_{s}\) are prime with \(p_{1} \le p_{2} \le \cdot\cdot\cdot \le p_{r}\) and \(q_{1} \le q_{2} \le \cdot\cdot\cdot \le q_{s}\).

We must now prove that \(r = s\), and for each \(j\) from 1 to \(r\), \(p_{j} = q_{j}\). We can break our proof into two cases: (1) \(p_{1} \le q_{1}\); and (2) \(q_{1} \le p_{1}\). Since one of these must be true, and since the proofs will be similar, we can assume, without loss of generality, that \(p_{1} \le q_{1}\).

Since \(k + 1 = p_{1}p_{2}\cdot\cdot\cdot p_{r}\), we know that \(p_{1}\ |\ (k + 1)\), and hence we may conclude that \(p_{1}\ |\ (q_{1}q_{2}\cdot\cdot\cdot q_{s})\). We now use Corollary 8.14 to conclude that there exists a \(j\) with \(1 \le j \le s\) such that \(p_{1}\ |\ q_{j}\). Since \(p_{1}\) and \(q_{j}\) are primes, we conclude that

\(p_{1} = q_{j}\).

We now use this and the fact that \(k + 1 = p_{1}p_{2}\cdot\cdot\cdot p_{r} = q_{1}q_{2}\cdot\cdot\cdot q_{s}\) to conclude that

\(p_{2}\cdot\cdot\cdot p_{r} = q_{2}\cdot\cdot\cdot q_{s}\).

The product in the previous equation is less that \(k + 1\). Hence, we can apply our induction hypothesis to these factorizations and conclude that \(r = s\), and for each \(j\) from 2 to \(r\), \(p_{j} = q_{j}\).

This completes the proof that if \(P(2), P(3), ..., P(k)\) are true, then \(P(k + 1)\) is true. Hence, by the Second Principle of Mathematical Induction, we conclude that \(P(n)\) is true for all \(n \in \mathbb{N}\) with \(n \ge 2\). This completes the proof of the theorem.

Note: We often shorten the result of the Fundamental Theorem of Arithmetic by simply saying that each natural number greater than one that is not a prime has a unique factorization as a product of primes. This simply means that if \(n \in \mathbb{N}\), \(n > 1\), and n is not prime, then no matter how we choose to factor n into a product of primes, we will always have the same prime factors. The only difference may be in the order in which we write the prime factors.

Further Results and Conjectures about Prime Numbers

1. The Number of Prime Numbers
   Prime numbers have fascinated mathematicians for centuries. For example, we can easily start writing a list of prime numbers in ascending order. Following is a list of the prime numbers less than 100.
   
   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
   
   This list contains the first 25 prime numbers. Does this list ever stop? The question was answered in Euclid’s Elements, and the result is stated in Theorem 8.16. The proof of this theorem is considered to be one of the classical proofs by contradiction.

   Theorem 8.16.

   There are infinitely many prime numbers.

   Proof

   We will use a proof by contradiction. We assume that there are only finitely many primes, and let

   \(p_{1}, p_{2}, ..., p_{m}\)

   be the list of all the primes. Let

   \[M = p_{1}p_{2}, ..., p_{m} + 1.\]

   Notice that \(M \ne 1\). So \(M\) is either a prime number or, by the Fundamental Theorem of Arithmetic, \(M\) is a product of prime numbers. In either case, \(M\) has a factor that is a prime number. Since we have listed all the prime numbers, this means that there exists a natural number \(j\) with \(1 \le j \le m\) such that \(p_{j}\ |\ M\). Now, we can rewrite equation (8.2.8) as follows:

   \[1 = M - p_{1}p_{2} \cdot\cdot\cdot p_{m}.\]

   We have proved \(p_{j}\ |\ M\), and since \(p_{j}\) is one of the prime factors of \(p_{1}p_{2} \cdot\cdot\cdot p_{m}\), we can also conclude that \(p_{j}\ |\ (p_{1}p_{2}\cdot\cdot\cdot p_{m})\). Since \(p_{j}\) divides both of the terms on the right side of equation (8.2.9), we can use this equation to conclude that \(p_{j}\) divides 1. This is a contradiction since a prime number is greater than 1 and cannot divide 1. Hence, our assumption that there are only finitely many primes is false, and so there must be infinitely many primes.

2. There are infinitely many primes, but when we write a list of the prime numbers, we can see some long sequences of consecutive natural numbers that contain no prime numbers. For example, there are no prime numbers between 113 and 127. The following theorem shows that there exist arbitrarily long sequences of consecutive natural numbers containing no prime numbers. A guided proof of this theorem is included in Exercise (15).

   Theorem 8.17,

   For any natural number \(n\), there exist at least \(n\) consecutive natural numbers that are composite numbers.

   There are many unanswered questions about prime numbers, two of which will now be discussed.

3. By looking at the list of the first 25 prime numbers, we see several cases where consecutive prime numbers differ by 2. Examples are: 3 and 5; 11 and 13; 17 and 19; 29 and 31. Such pairs of prime numbers are said to be twin primes. How many twin primes exist? The answer is not known. The Twin Prime Conjecture states that there are infinitely many twin primes. As of June 25, 2010, this is still a conjecture as it has not been proved or disproved.

   For some interesting information on prime numbers, visit the Web site The Prime Pages (primes.utm.edu/), where there is a link to The Largest Known Primes Web site. According to information at this site as of June 25, 2010, the largest known twin primes are
   \[(65516468355 \times 2^{333333} - 1) \text{ and } (65516468355 \times 2^{333333} + 1).\]
   Each of these prime numbers contains 100355 digits.

4. Given an even natural number, is it possible to write it as a sum of two prime numbers? For example,
   
   4 = 2 + 2 6 = 3 + 3 8 = 5 + 3
   78 = 37 + 41 90 = 43 + 47 128 = 67 + 71
   

   One of the most famous unsolved problems in mathematics is a conjecture made by Christian Goldbach in a letter to Leonhard Euler in 1742. The conjecture, now known as Goldbach’s Conjecture, is as follows:

   Every even integer greater than 2 can be expressed as the sum of two (not necessarily distinct) prime numbers.

   As of June 25, 2010, it is not known if this conjecture is true or false, al- though most mathematicians believe it to be true.

Exercise 8.2

1. Prove the second and third parts of Theorem 8.11.
   
   (a) Let \(a\) be a nonzero integer, and let \(p\) be a prime number. If \(p\ |\ a\), then \(\text{gcd}(a, p) = p\).
   (b) Let \(a\) be a nonzero integer, and let \(p\) be a prime number. If \(p\) does not divide \(a\), then \(\text{gcd}(a, p) = 1\).
2. Prove the first part of Corollary 8.14.
   Let \(a, b \in \mathbb{Z}\), let \(p\) be a prime number. If \(p\ |\ (ab)\), then \(p\ |\ a\) or \(p\ |\ b\). Hint: Consider two cases: (1) \(p\ |\ a\); and (2) \(p\) does not divide \(a\).
3. Use mathematical induction to prove the second part of Corollary 8.14.
   Let \(p\) be a prime number, let \(n \in \mathbb{N}\), and let \(a_1, a_2, ..., a_n \in \mathbb{Z}\). If \(p\ |\ (a_{1}a_{2} \cdot\cdot\cdot a_{n})\), then there exists a \(k \in \mathbb{N}\) with \(1 \le k \le n\) such that \(p\ |\ a_k\).
4. (a) Let \(a\) and \(b\) be nonzero integers. If there exist integers \(x\) and \(y\) such that \(ax + by = 1\), what conclusion can be made about gcd(\(a, b\))? Explain.
   (b) Let \(a\) and \(b\) be nonzero integers. If there exist integers \(x\) and \(y\) such that \(ax + by = 2\), what conclusion can be made about gcd(\(a, b\))? Explain.
5. (a) Let \(a \in \mathbb{Z}\). What is gcd.a; a C 1/? That is, what is the greatest common divisor of two consecutive integers? Justify your conclusion.

   Hint: Exercise (4) might be helpful.

   (b) Let \(a \in \mathbb{Z}\). What conclusion can be made about gcd(\(a\), \(a + 2\))? That is, what conclusion can be made about the greatest common divisor of two integers that differ by 2? Justify your conclusion.

6. (a) Let \(a \in \mathbb{Z}\). What conclusion can be made about gcd(\(a\), \(a + 3\))? That is, what conclusion can be made about the greatest common divisor of two integers that differ by 3? Justify your conclusion.
   (b) Let \(a \in \mathbb{Z}\). What conclusion can be made about gcd(\(a\), \(a + 4\))? That is, what conclusion can be made about the greatest common divisor of two integers that differ by 4? Justify your conclusion.
7. (a) Let \(a = 16\) and \(b = 28\). Determine the value of \(d = \text{gcd}(a, b)\), and then determine the value of gcd(\(\dfrac{a}{d}\), \(\dfrac{b}{d}\)).
   (b) Repeat Exercise (7a) with \(a = 10\) and \(b = 45\).
   (c) Let \(a, b \in \mathbb{Z}\), not both equal to 0, and let \(d = \text{gcd}(a, b)\). Explain why \(\dfrac{a}{d}\) and \(\dfrac{b}{d}\) are integers. Then prove that \(\text{gcd}(\dfrac{a}{d}, \dfrac{b}{d}) = 1\). Hint: Start by writing \(d\) as a linear combination of \(a\) and \(b\).
   This says that if you divide both \(a\) and \(b\) by their greatest common divisor, the result will be two relatively prime integers.
8. Are the following propositions true or false? Justify your conclusions.
   
   (a) For all integers \(a\), \(b\), and \(c\), if \(a\ |\ c\) and \(b\ |\ c\), then \((ab)\ |\ c\).
   (b) For all integers \(a\), \(b\), and \(c\), if \(a\ |\ c\), \(b\ |\ c\), and \(\text{gcd}(a, b) = 1\), then \((ab)\ |\ c\).
9. In Exercise (16) in Section 3.5, it was proved that if \(n\) is an odd integer, then \(8\ |\ (n^2 - 1\)\). (This result was also proved in Exercise (19) in Section 7.4.) Now, prove the following proposition:
   If \(n\) is an odd integer and 3 does not divide \(n\), then \(24\ |\ (n^2 - 1)\).
10. (a) Prove the following proposition:
    For all \(a, b, c \in \mathbb{Z}\), \(\text{gcd}(a, bc) = 1\) if and only if \(\text{gcd}(a, b) = 1\) and \(\text{gcd}(a, c) = 1\).
    (b) Use mathematical induction to prove the following proposition:
    Let \(n \in \mathbb{N}\) and let \(a, b_1, b_2, ..., b_n \in \mathbb{Z}\). If \(\text{gcd}(a, b_i) = 1\) for all \(i \in \mathbb{N}\) with \(1 \le i \le n\), then \(\text{gcd}(a, b_{1}b_{2} \cdot\cdot\cdot b_{n}) = 1\).
11. Is the following proposition true or false? Justify your conclusion.
    Fro all integer \(a\), \(b\), and \(c\), if \(\text{gcd}(a, b) = 1\) and \(c\ |\ (a + b)\), then \(\text{gcd}(a, c) = 1\) and \(\text{gcd}(b, c) = 1\).
12. Is the following proposition true or false? Justify your conclusion.
    If \(n \in \mathbb{N}\), then \(\text{gcd}(5n + 2, 12n + 5) = 1\)
13. Let \(y \in \mathbb{N}\). Use the Fundamental Theorem of Arithmetic to prove that there exists an odd natural number x and a nonnegative integer \(k\) such that \(y = 2^{k}x\).
14. (a) Determine five different primes that are congruent to 3 modulo 4.
    (b) Prove that there are infinitely many primes that are congruent to 3 modulo 4.
15. (a) Let \(n \in \mathbb{N}\). Prove that 2 divides \([(n + 1)! + 2]\).
    (b) Let \(n \in \mathbb{N}\) with \(n \ge 2\). Prove that 3 divides \([(n + 1)! + 3]\).
    (c) Let \(n \in \mathbb{N}\). Prove that for each \(k \in \mathbb{N}\) with \(2 \le k \le (n + 1)\), \(k\) divides \([(n + 1)! + k]\).
    (d) Use the result of Exercise (15c) to prove that for each \(n \in \mathbb{N}\), there exist at least \(n\) consecutive composite natural numbers.
16. The Twin Prime Conjecture states that there are infinitely many twin primes, but it is not known if this conjecture is true or false. The answers to the following questions, however, can be determined.
    
    (a) How many pairs of primes \(p\) and \(q\) exist where \(q - p = 3\)? That is, how many pairs of primes are there that differ by 3? Prove that your answer is correct. (One such pair is 2 and 5.)
    (b) How many triplets of primes of the form \(p\), \(p + 2\), and \(p + 4\) are there? That is, how many triplets of primes exist where each prime is 2 more than the preceding prime? Prove that your answer is correct. Notice that one such triplet is 3, 5, and 7.
    Hint: Try setting up cases using congruence modulo 3.
17. Prove the following proposition:
    Let \(n \in \mathbb{N}\). For each \(a \in \mathbb{Z}\), if \(\text{gcd}(a, n) = 1\), then for every \(b \in \mathbb{Z}\), there exists an \(x \in \mathbb{Z}\) such that \(ax \equiv b\) (mod \(n\)).
    Hint: One way is to start by writing 1 as a linear combination of \(a\) and \(n\).
18. Prove the following proposition:

    For all natural numbers \(m\) and \(n\), if \(m\) and \(n\) are twin primes other than the pair 3 and 5, then 36 divides \(mn + 1\) and \(mn + 1\) is a perfect square.

    Hint: Look at several examples of twin primes. What do you notice about the number that is between the two twin primes? Set up cases based on this observation.

Explorations and Activities

19. Square Roots and Irrational Numbers. In Chapter 3, we proved that some square roots (such as \(\sqrt{2}\) and \(\sqrt{3}\)) are irrational numbers. In this activity, we will use the Fundamental Theorem of Arithmetic to prove that if a natural number is not a perfect square, then its square root is an irrational number.
(a) Let \(n\) be a natural number. Use the Fundamental Theorem of Arithmetic to explain why if n is composite, then there exist prime numbers \(p_{1}, p_{2}, ..., p_{r}\) and natural numbers \(\alpha_{1}, \alpha_{2}, ..., \alpha_{r}\) such that

\[n = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}} \cdot\cdot\cdot p_{r}^{\alpha_{r}}.\]

Then,if we use \(r = 1\) and \(\alpha_{1} = 1\) for a prime number, explain why we can write any natural number in the form given in equation (8.2.11).

(b) A natural number \(b\) is a perfect square if and only if there exists a natural number \(a\) such that \(b = a^2\). Explain why 36, 400, and 15876 are perfect squares. Then determine the prime factorization of these perfect squares. What do you notice about these prime factorizations?

(c) Let \(n\) be a natural number written in the form given in equation (8.2.11) in part (a). Prove that \(n\) is a perfect square if and only if for each natural number \(k\) with \(1 \le k \le r\), \(\alpha_{k}\) is even.

(d) Prove that for all natural numbers \(n\), if \(n\) is not a perfect square, then \(\sqrt{n}\) is an irrational number. Hint: Use a proof by contradiction.

Answer

Add texts here. Do not delete this text first.