Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Subsection 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\text{,}\) 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\text{.}\)

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.22, which was part of Activity 30 in Section 5.2 and Activity 47 in Section 8.1.

Proposition 5.22: Let a, b, and t be integers with \(t \ne 0\text{.}\) If \(t\) divides \(a\) and \(t\) divides \(b\text{,}\) then for all integers \(x\) and \(y\text{,}\) \(t\) divides \(\left( ax + by \right)\text{.}\)

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

Subsection Relatively Prime Integers

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

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

Item 1 of Theorem 8.13 is actually a corollary of Theorem 8.11. Item 2 and Item 3 could have been the conjectures you formulated in Progress Check 8.12. The proofs are included in Exercise 1.

Given nonzero integers \(a\) and \(b\text{,}\) 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\text{.}\) 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.14, which is based on work in Beginning Activity 1.

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

Since we are given that \(a \mid \left( {bc} \right)\text{,}\) there exists an integer \(k\) such that

It may seem tempting to divide both sides of equation (70) by \(b\text{,}\) 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 \(\gcd( {a, b} ) = 1\text{.}\) How can we use this? This means that \(a\) and \(b\) have no common factors except for 1. In light of equation (70) it seems reasonable that any factor of \(a\) must also be a factor of \(c\text{.}\) But how do we formalize this?

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

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

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

Notice that the left side of equation (72) contains a term, \(bcn\text{,}\) that contains \(bc\text{.}\) This means that we can use equation (70) and substitute \(bc = ak\) in equation (72). After doing this, we can factor the left side of the equation to prove that \(a \mid c\text{.}\)

Item 1 of Corollary 8.16 is a corollary of Theorem 8.14. Item 2 is proved using mathematical induction. The basis step is the case where \(n = 1\text{,}\) and Item 1 is the case where \(n = 2\text{.}\) The proofs of these two results are included in Exercise 2 and Exercise 3.

Subsection Historical Note

Item 1 of Corollary 8.16 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.

Subsection 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.11 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\text{.}\) Since \(5 \mid 120\text{,}\) we can write \(120 = 5 \cdot 24\text{.}\) In addition, we can factor 24 as \(24 = 2 \cdot 2 \cdot 2 \cdot 3\text{.}\) So we can write

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

Now, let \(n \in \mathbb{N}\text{.}\) To write the prime factorization of \(n\) with the prime factors in ascending order requires that if we write \(n = p_1 p_2 \cdots p_r\text{,}\) where \(p_1 , p_2 , \ldots, p_r\) are prime numbers, we will have \(p_1 \leq p_2 \leq \cdots \leq p_r\text{.}\)

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}\text{,}\) \(n > 1\text{,}\) 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.

Subsection Further Results and Conjectures about Prime Numbers

• 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.18. The proof of this theorem is considered to be one of the classical proofs by contradiction.

  Theorem 8.18.

  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

  \begin{equation*} p_1 , p_2 , \ldots , p_m \end{equation*}

  be the list of all the primes. Let

  \begin{equation} M = p_1 p_2 \cdots p_m + 1\text{.}\tag{76} \end{equation}

  Notice that \(M \ne 1\text{.}\) 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 \leq j \leq m\) such that \(p_j \mid M\text{.}\) Now, we can rewrite equation (76) as follows:

  \begin{equation} 1 = M - p_1 p_2 \cdots p_m\text{.}\tag{77} \end{equation}

  We have proved \(p_j \mid M\text{,}\) and since \(p_j\) is one of the prime factors of \(p_1 p_2 \cdots p_m\text{,}\) we can also conclude that \(p_j \mid \left( {p_1 p_2 \cdots p_m } \right)\text{.}\) Since \(p_j\) divides both of the terms on the right side of equation (77), 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.

• The Distribution of Prime Numbers.

  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.19.

  For any natural number \(n\text{,}\) 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.

• The Twin Prime Conjecture.

  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⁸ 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

  \begin{equation*} \left( 65516468355 \times 2^{333333} - 1 \right) \text{ and } \left( 65516468355 \times 2^{333333} + 1 \right)\text{.} \end{equation*}

  Each of these prime numbers contains 100355 digits.

• Goldbach's Conjecture.

  Given an even natural number, is it possible to write it as a sum of two prime numbers? For example,

  \begin{align*} 4 \amp = 2 + 2 \amp 6 \amp = 3 + 3 \amp 8 \amp = 5+3\\ 78 \amp = 37 + 41 \amp 90 \amp = 43 + 47 \amp 138 \amp = 67 + 71 \end{align*}

  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, although most mathematicians believe it to be true.