Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Subsection The System of Integers

Number theory is a study of the system of integers, which consists of the set of integers, \(\mathbb{Z} = \left\{ \ldots , - 3, - 2, - 1, 0, 1, 2, 3, \ldots \right\}\) and the various properties of this set under the usual operations of addition and multiplication and under the usual ordering relation of “less than.” The properties of the integers in Table 8.1 will be considered axioms in this text.

We will also assume the properties of the integers shown in Table 8.2. These properties can be proven from the properties in Table 8.1. (However, we will not do so here.)

We have already studied a good deal of number theory in this text in our discussion of proof methods. In particular, we have studied even and odd integers, divisibility of integers, congruence, and the Division Algorithm. See the summary Section 3.7 for a summary of results concerning even and odd integers as well as results concerning properties of divisors. We reviewed some of these properties and the Division Algorithm in the beginning activities.

Subsection The Greatest Common Divisor

One of the most important concepts in elementary number theory is that of the greatest common divisor of two integers. The definition for the greatest common divisor of two integers (not both zero) was given in Beginning Activity 1.

1. If \(a, b \in \mathbb{Z}\) and \(a\) and \(b\) are not both 0, and if \(d \in \mathbb{N}\text{,}\) then \(d = \gcd( {a, b} )\) provided that it satisfies all of the following properties:

   • \(d \mid a\) and \(d \mid b\text{.}\) That is, \(d\) is a common divisor of \(a\) and \(b\text{.}\)

   • If \(k\) is a natural number such that \(k \mid a\) and \(k \mid b\text{,}\) then \(k \leq d\text{.}\) That is, any other common divisor of \(a\) and \(b\) is less than or equal to \(d\text{.}\)

2. Consequently, a natural number \(d\) is not the greatest common divisor of \(a\) and \(b\) provided that it does not satisfy at least one of these properties. That is, \(d\) is not equal to \(\gcd( {a, b} )\) provided that

   • \(d\) does not divide \(a\) or \(d\) does not divide \(b\text{;}\) or

   • There exists a natural number \(k\) such that \(k \mid a\) and \(k \mid b\) and \(k > d\text{.}\)

   This means that \(d\) is not the greatest common divisor of \(a\) and \(b\) provided that it is not a common divisor of \(a\) and \(b\) or that there exists a common divisor of \(a\) and \(b\) that is greater than \(d\text{.}\)

In the beginning activities, we determined the greatest common divisors for several pairs of integers. The process we used was to list all the divisors of both integers, then list all the common divisors of both integers and, finally, from the list of all common divisors, find the greatest (largest) common divisor. This method works reasonably well for small integers but can get quite cumbersome if the integers are large. Before we develop an efficient method for determining the greatest common divisor of two integers, we need to establish some properties of greatest common divisors.

One property was suggested in Beginning Activity 1. If we look at the results in Exercise 7 of that beginning activity, we should observe that any common divisor of \(a\) and \(b\) will divide \(\gcd( {a, b} )\text{.}\) In fact, the primary goals of the remainder of this section are

1. To find an efficient method for determining \(\gcd( {a, b} )\text{,}\) where \(a\) and \(b\) are integers.

2. To prove that the natural number \(\gcd( {a, b} )\) is the only natural number \(d\) that satisfies the following properties:

   • \(d\) divides \(a\) and \(d\) divides \(b\text{;}\) and

   • if \(k\) is a natural number such that \(k \mid a\) and \(k \mid b\text{,}\) then \(k \mid d\text{.}\)

The second goal is only slightly different from the definition of the greatest common divisor. The only difference is in the second condition where \(k \leq d\) is replaced by \(k \mid d\text{.}\)

We will first consider the case where \(a\) and \(b\) are integers with \(a \ne 0\) and \(b > 0\text{.}\) The proof of the result stated in the second goal contains a method (called the Euclidean Algorithm) for determining the greatest common divisor of the two integers \(a\) and \(b\text{.}\) The main idea of the method is to keep replacing the pair of integers \(\left( {a, b} \right)\) with another pair of integers \(\left( {b, r} \right)\text{,}\) where \(0 \leq r \lt b\) and \(\gcd ( {b, r} ) = \gcd ( {a, b} )\text{.}\) This idea was explored in Beginning Activity 2. Lemma 8.3 is a conjecture that could have been formulated in Beginning Activity 2.

Subsection The Euclidean Algorithm

The example in Progress Check 8.4 illustrates the main idea of the Euclidean Algorithm for finding \(\gcd( {a, b} )\text{,}\) which is explained in the proof of the following theorem.

Subsection Some Remarks about Theorem 8.5

Theorem 8.5 was proven with the assumptions that \(a, b \in \mathbb{Z}\) with \(a \ne 0\) and \(b > 0\text{.}\) A more general version of this theorem can be proven with \(a, b \in \mathbb{Z}\) and \(b \ne 0\text{.}\) This can be proven using Theorem 8.5 and the results in the following lemma.

The proofs of these results are in Exercise 4. An application of this result is given in the next example.

Subsection Writing \(\boldsymbol{\gcd (a, b)}\) in Terms of \(a\) and \(b\)

We will use Example 8.8 to illustrate another use of the Euclidean Algorithm. It is possible to use the steps of the Euclidean Algorithm in reverse order to write \(\gcd( {a, b} )\) in terms of \(a\) and \(b\text{.}\) We will use these steps in reverse order to find integers \(m\) and \(n\) such that \(\gcd( {234, 42} ) = 234m + 42n\text{.}\) The idea is to start with the row with the last nonzero remainder and work backward as shown in the following table:

Hence, we can write

(Check this with a calculator.) In this case, we say that we have written \(\gcd( {234, 42} )\) as a linear combination of 234 and 42. More generally, we have the following definition.

The previous example and progress check illustrate the following important result in number theory, which will be used in the next section to help prove some other significant results.

We will not give a formal proof of this theorem. Hopefully, the examples and activities provide evidence for its validity. The idea is to use the steps of the Euclidean Algorithm in reverse order to write \(\gcd( {a, b} )\) as a linear combination of \(a\) and \(b\text{.}\) For example, assume the completed table for the Euclidean Algorithm is

We can use Step 3 to write \(r_3 = \gcd( {a, b} )\) as a linear combination of \(r_1\) and \(r_2\text{.}\) We can then solve the equation in Step 2 for \(r_2\) and use this to write \(r_3 = \gcd( {a, b} )\) as a linear combination of \(r_1\) and \(b\text{.}\) We can then use the equation in Step 1 to solve for \(r_1\) and use this to write \(r_3 = \gcd( {a, b} )\) as a linear combination of \(a\) and \(b\text{.}\)

In general, if we can write \(r_p = \gcd( {a, b} )\) as a linear combination of a pair in a given row, then we can use the equation in the preceding step to write \(r_p = \gcd( {a, b} )\) as a linear combination of the pair in this preceding row.

The notational details of this induction argument get quite involved. Many mathematicians prefer to prove Theorem 8.10 using a property of the natural numbers called the Well-Ordering Principle. The Well-Ordering Principle for the natural numbers states that any nonempty set of natural numbers must contain a least element. It can be proven that the Well-Ordering Principle is equivalent to the Principle of Mathematical Induction.