1.2: Divisibility and GCDs in the Integers

Learning Objectives

In this section, we'll seek to answer the questions:

• What does it mean for one integer to divide another?
• What properties does divisibility enjoy in the integers?
• What is the greatest common divisor of two integers?
• How can we compute the greatest common divisor of two integers?

1.2.1: Divisibility and the Division Algorithm

In this section, we begin to explore some of the arithmetic and algebraic properties of \(\mathbb{Z}\text{.}\) We focus specifically on the divisibility and factorization properties of the integers, as these are the main focus of the text as a whole. One of the primary goals of this section is to formalize definitions that you are likely already familiar with and of which you have an intuitive understanding. At first, this might seem to unnecessarily complicate matters. However, it will become clear as we move forward that formal mathematical language and notation are necessary to extend these properties to a more abstract setting. We begin with a familiar notion.

Definition: Divisibility and the Division Algorithm

Let \(a,b\in \mathbb{Z}\text{.}\) We say that \(a\) divides \(b\text{,}\) and write \(a\mid b\text{,}\) if there is an integer \(c\) such that \(ac = b\text{.}\) In this case, say that \(a\) and \(c\) are factors of \(b\text{.}\) If no such \(c\in \mathbb{Z}\) exists, we write \(a\nmid b\text{.}\)

Note that the symbol \(|\) is a verb; it is therefore correct to say, e.g., \(2|4\text{,}\) as 2 does divide 4. However, it is an abuse of notation to say that \(2\mid 4 = 2\text{.}\) Instead, we likely mean \(4\div 2 = 2\) or \(\dfrac{4}{2} = 2\) (though we will not deal in fractions just yet).

Investigation: 1.2.1

Determine whether \(a\mid b\) if:

1. \(a = 3\text{,}\) \(b = -15\)
2. \(a = 4\text{,}\) \(b = 18\)
3. \(a = -7\text{,}\) \(b = 0\)
4. \(a = 0\text{,}\) \(b = 0\)

Comment briefly on the results of this investigation. What did you notice? What do you still wonder?

We next collect several standard results about divisibility in \(\mathbb{Z}\) which will be used extensively in the remainder of this text.

Theorem 1.2.1

Let \(a,b,c\in\mathbb{Z}\text{.}\) If \(a\mid b\) and \(a\mid c\text{,}\) then \(a\mid (b+c)\text{.}\)

Theorem 1.2.2

Let \(a,b,c\in\mathbb{Z}\text{.}\) If \(a\mid b\text{,}\) then \(a\mid bc\text{.}\)

Investigation 1.2.2

Consider the following partial converse to Theorem 1.2.1 : If \(a,b,c\in\mathbb{Z}\) with \(a|bc\text{,}\) must \(a|b\) or \(a|c\text{?}\) Supply a proof or give a counterexample.

Theorem 1.2.3

Let \(a,b,c,d\in \mathbb{Z}\text{.}\) If \(a = b+c\) and \(d\) divides any two of \(a,b,c\text{,}\) then \(d\) divides the third.

Investigation 1.2.3

Formulate a conjecture akin to the previous theorems about divisibility in \(\mathbb{Z}\text{,}\) and then prove it

As we saw above, not all pairs of integers \(a,b\) satisfy \(a\mid b\) or \(b\mid a\text{.}\) However, our experience in elementary mathematics does apply: there is often something left over (a remainder). The following theorem formalizes this idea for \(a,b\in \mathbb{N}\text{.}\)

Theorem 1.2.4

The Division Algorithm for \(\mathbb{N}\).

Let \(a,b\in \mathbb{N}\text{.}\) Then there exist unique integers \(q,r\) such that \(a = bq + r\text{,}\) where \(0 \le r \lt b\text{.}\)

Hint 1

There are two parts to this theorem. First, you must establish that \(q\) and \(r\) exist. This is best done via Axiom 1.2.1 . If you're stuck on that, check the second hint.

Once you have established that \(q\) and \(r\) exist, show that they are unique but assuming \(a = bq+r\) and \(a = bq' + r'\text{,}\) where \(r,r'\) both satisfy the conditions of the theorem. Argue that \(q = q'\) and \(r = r'\text{.}\)

Hint 2

Let \(S = \{ a-bs : s\in \mathbb{N}_0, a-bs\ge 0\}\text{.}\)

Warning!

This theorem has two parts: existence and uniqueness. Do not try to prove them both at the same time.

Unsurprisingly, the Division Algorithm also holds in \(\mathbb{Z}\text{,}\) though the existence of negative integers requires a careful restatement.

Corollary 1.2.1

Let \(a,b\in \mathbb{Z}\) with \(b\ne 0\text{.}\) Then there exist unique integers \(q,r\) such that \(a = bq + r\text{,}\) where \(0 \le r \lt |b|\text{.}\)

Hint

Consider cases, and apply Theorem 1.2.4 wherever possible.

1.2.2:Greatest Common Divisors

We next turn to another familiar property of the integers: the existence of greatest common divisors.

Definition: Greatest Common Divisor

Let \(a,b\in \mathbb{Z}\) such that \(a\) and \(b\) are not both 0. A greatest common divisor of \(a\) and \(b\text{,}\) denoted \(\gcd(a,b)\text{,}\) is a natural number \(d\) satisfying

1. \(d\mid a\) and \(d\mid b\)
2. if \(e\in \mathbb{N}\) and \(e\mid a\) and \(e\mid b\text{,}\) then \(e\mid d\text{.}\)

If \(\gcd(a,b) = 1\text{,}\) we say that \(a\) and \(b\) are relatively prime or coprime.

Note: This formalizes the idea of greatest common factors that is introduced around sixth grade

This definition may be different than the one you are used to, which likely stated that \(d \ge e\) rather than condition 2 in Definition: Greatest Common Divisor. It can be proved using the order relations of \(\mathbb{Z}\) that the definition given here is equivalent to that one. However, we will prefer this definition, as it generalizes naturally to other number systems which do not have an order relation like \(\mathbb{Z}\text{.}\)

Activity 1.2.1

Compute \(\gcd(a,b)\) if:

1. \(a = 123\text{,}\) \(b = 141\)
2. \(a = 0\text{,}\) \(b = 169\)
3. \(a= 85\text{,}\) \(b = 48\)

Now that you have had a bit of practice computing gcds, describe your method for finding them in a sentence or two.

How did you answer the last question in Activity 1.2.1 ? If you are like the authors' classes, the answers probably varied, though you have referred at some point to a "prime" (whatever those are), or possibly some other ad hoc method for finding the gcd. Most such methods rely in some form on our ability to factor integers. However, the problem of factoring arbitrary integers is actually surprisingly computationally intensive. Thankfully, there is another way to compute \(\gcd(a,b)\text{,}\) to which we now turn.

Theorem 1.2.5

Let \(a,b,c\in\mathbb{Z}\) such that \(a = b+c\) with \(a\) and \(b\) not both zero. Then \(\gcd(a,b) = \gcd(b,c)\text{.}\)

Investigation 1.2.4

Suppose \(a,b,c\in\mathbb{Z}\) such that there exists \(q\in\mathbb{Z}\) with \(a = bq + c\) and \(a\) and \(b\) not both zero. Prove or disprove: \(\gcd(a,b)=\gcd(b,c)\text{.}\)

Investigation 1.2.5

(Euclidean Algorithm).

Let \(a,b\in \mathbb{N}\text{.}\) Use Theorem 1.2.4 and Investigation 1.2.4 to determine an algorithm for computing \(\gcd(a,b)\text{.}\) How could your method be modified to compute \(\gcd(a,b)\) for \(a,b\in\mathbb{Z}\text{?}\)

Activity 1.2.2

Use the Euclidean algorithm to compute \(\gcd(18489,17304)\text{.}\)

The following identity provides a useful characterization of the greatest common divisor of two integers, not both zero. We will return to this idea several times, even after we have left the familiar realm of the integers.

Theorem 1.2.6 : Bézout's Identity

For any integers \(a\) and \(b\) not both 0, there are integers \(x\) and \(y\) such that

\begin{equation*} ax + by = \gcd(a,b)\text{.} \end{equation*}

Hint 1

Apply Axiom 1.2.1 to a well-chosen set.

Hint 2

Apply Axiom 1.2.1 to \(S = \{as+bt : s,t\in\mathbb{Z}, \ as+bt \gt 0\}\text{.}\)

We conclude with an answer to the questions raised by Investigation 1.2.2 .

Theorem 1.2.7

Let \(a, b\text{,}\) and \(c\) be integers. If \(a|bc\) and \(\gcd(a,b) = 1\text{,}\) then \(a|c\text{.}\)

In this section, we have collected some initial results about divisibility in the integers. We'll next explore the multiplicative building blocks of the integers, the primes, in preparation for a deeper exploration of factorization.