§1.2 Divisibility

Definition of Divides

An important case of division occurs when the remainder is 0, that is, when the divisor is a factor of the dividend. Here is a formal definition:

Definition of Divides:

Let $a$ and $b$ be integers with $b \neq 0$. We say that $b$ divides $a$ (or that $b$ is a divisor of $a$, or that $b$ is a factor of $a$) if $a = bc$ for some integer $c$. In symbols, "b divides a" is written $b | a$ and "b does not divide a" is written $b \nmid a$.

Example 1.2.1: Simple Divisibility

$3 | 24$ because $24 = 3 \cdot 8$, but $3 \nmid 17$. Negative divisors are allowed: $-6 | 54$ because $54 = (-6)(-9)$, but $-6 \nmid (-13)$.

Example 1.2.2: Divisibility of Zero and One

Every nonzero integer $b$ divides 0 because $0 = b \cdot 0$. For every integer $a$, we have $1 | a$ because $a = 1 \cdot a$.

Reflection 1.2.1: Divisors of Opposite Integers

If $b$ divides $a$, then $a = bc$ for some $c$. Hence $-a = b(-c)$, so that $b | (-a)$. An analogous argument shows that every divisor of $-a$ is also a divisor of $a$. Therefore

$$ a \text{ and } -a \text{ have the same divisors.} $$

Reflection 1.2.2: Divisor Count and Limits

Suppose $a \neq 0$ and $b | a$. Then $a = bc$, so that $|a| = |b||c|$. Consequently, $0 \leq |b| \leq |a|$. This last inequality is equivalent to $-|a| \leq b \leq |a|$. Therefore:

Every divisor of the nonzero integer $a$ is less than or equal to $|a|$;
A nonzero integer has only finitely many divisors.

All the divisors of the integer 12 are:

$$ 1, -1, 2, -2, 3, -3, 4, -4, 6, -6, 12, -12. $$

Similarly, all the divisors of 30 are:

$$ 1, -1, 2, -2, 3, -3, 5, -5, 6, -6, 10, -10, 15, -15, 30, -30. $$

The common divisors of 12 and 30 are the numbers that divide both 12 and 30, that is, the numbers that appear on both of the preceding lists:

$$ 1, -1, 2, -2, 3, -3, 6, -6. $$

The largest of these common divisors, namely 6, is called the "greatest common divisor" of 12 and 30. This is an example of the following definition:

Definition of Greatest Common Divisor

Let $a$ and $b$ be integers, not both 0. The greatest common divisor (gcd) of $a$ and $b$ is the largest integer $d$ that divides both $a$ and $b$. In other words, $d$ is the gcd of $a$ and $b$ provided that:

$d | a$ and $d | b$;
If $c | a$ and $c | b$, then $c \leq d$.

The greatest common divisor of $a$ and $b$ is usually denoted $(a, b)$.

If $a$ and $b$ are not both 0, then their gcd exists and is unique. The reason is that a nonzero integer has only finitely many divisors, and so there are only a finite number of common divisors. Hence, there must be a unique largest one. Furthermore, the greatest common divisor of $a$ and $b$ satisfies the inequality:

$$ (a, b) \geq 1 $$

because 1 is a common divisor of $a$ and $b$.

Example 1.2.3: Relatively Prime Numbers

$(12, 30) = 6$, as shown above. The only common divisors of 10 and 21 are 1 and $-1$. Hence $(10, 21) = 1$. Two integers whose greatest common divisor is 1, such as 10 and 21, are said to be relatively prime.

Example 1.2.4: Divisors of a Number and Zero

The common divisors of an integer $a$ and 0 are just the divisors of $a$. If $a > 0$, then the largest divisor of $a$ is clearly $a$ itself. Hence, if $a > 0$, then $(a, 0) = a$.

Listing all the divisors of two integers in order to find their gcd can be quite time-consuming. However, the Euclidean Algorithm (Exercise 15) is a relatively quick method for finding gcd’s by hand. You can also use technology.

We have seen that $6 = (12, 30)$. A little arithmetic shows that something else is true here: 6 is a linear combination of 12 and 30. For instance:

$$ 6 = 12(-2) + 30(1) \quad \text{and} \quad 6 = 12(8) + 30(-3). $$

You can readily find other integers $u$ and $v$ such that $6 = 12u + 30v$. The following theorem shows that the same thing is possible for any greatest common divisor.

Theorem 1.2: The Linear Combination of the GCD

Let $a$ and $b$ be integers, not both 0, and let $d$ be their greatest common divisor. Then there exist (not necessarily unique) integers $u$ and $v$ such that

$$ d = au + bv. $$

CAUTION: Read the theorem carefully. The fact that $d = au + bv$ does not imply that $d = (a, b)$. See Exercise 1.25.

For the benefit of inexperienced readers, the proofs of Theorem 1.2 and Corollary 1.3 will be broken into several steps. The basic idea of the proof of Theorem 1.2 is to look at all possible linear combinations of $a$ and $b$ and find one that is equal to $d$.

Proof of Theorem 1.2

Let $S$ be the set of all linear combinations of $a$ and $b$, that is

$$ S = \{am + bn \mid m, n \in \mathbb{Z}\}. $$

Step 1: Find the smallest positive element of $S$.

Proof of Step 1: Note that $a^2 + b^2 = aa + bb$ is in $S$ and $a^2 + b^2 \geq 0$. Since $a$ and $b$ are not both 0, $a^2 + b^2$ must be positive. Therefore $S$ contains positive integers and hence must contain a smallest positive integer by the Well-Ordering Axiom. Let $t$ denote this smallest positive element of $S$. By the definition of $S$, we know that $t = au + bv$ for some integers $u$ and $v$.

Step 2: Prove that $t$ is the gcd of $a$ and $b$, that is, $t = d$.

Proof of Step 2: We must prove that $t$ satisfies the two conditions in the definition of the gcd:

$t \mid a$ and $t \mid b$;
If $c \mid a$ and $c \mid b$, then $c \leq t$.

Proof of (1):

By the Division Algorithm, there are integers $q$ and $r$ such that $a = tq + r$, with $0 \leq r < t$. Consequently:

$$ r = a - tq, \\ r = a - (au + bv)q = a - aqu - bvq, \\ r = a(1 - qu) + b(-vq). $$

Thus $r$ is a linear combination of $a$ and $b$, and hence $r \in S$. Since $r < t$ (the smallest positive element of $S$), we know that $r$ is not positive. Since $r \geq 0$, the only possibility is that $r=0$. Therefore:

$$ a = tq + r = tq + 0 = tq, $$

so that $t \mid a$. A similar argument shows that $t \mid b$. Hence, $t$ is a common divisor of $a$ and $b$.

Proof of (2):

Let $c$ be any other common divisor of $a$ and $b$, so that $c \mid a$ and $c \mid b$. Then $a = ck$ and $b = cs$ for some integers $k$ and $s$. Consequently:

$$ t = au + bv = (ck)u + (cs)v = c(ku + sv). $$

The first and last terms of this equation show that $c \mid t$. Hence, $c \leq t$ by the second Remark on page 9. But $t$ is positive, so $|t| = t$. Thus $c \leq t$.

This shows that $t$ is the greatest common divisor $d$ and completes the proof of the theorem. $\blacksquare$

Corollary 1.3: Conditions for the GCD

Let $a$ and $b$ be integers, not both 0, and let $d$ be a positive integer. Then $d$ is the greatest common divisor of $a$ and $b$ if and only if $d$ satisfies these conditions:

$d \mid a$ and $d \mid b$;
If $c \mid a$ and $c \mid b$, then $c \mid d$.

Proof of Corollary 1.3

The proof of an "if and only if" statement requires two steps (see page 507 in Appendix A).

Step 1: If $d = (a, b)$, then $d$ satisfies conditions (i) and (ii).

Proof of Step 1: If $d = (a, b)$, then by the definition of the gcd, $d$ divides both $a$ and $b$. So $d$ satisfies condition (i).

To verify that $d$ satisfies condition (ii), suppose that $c$ is an integer such that $c \mid a$ and $c \mid b$. Then $a = cr$ and $b = cs$ for some integers $r$ and $s$, by the definition of "divides". By Theorem 1.2, there are integers $u$ and $v$ such that

$$ d = au + bv $$

$$ d = (cr)u + (cs)v \quad \text{[Because } a = cr \text{ and } b = cs.] $$

$$ d = c(ru + sv) \quad \text{[Factor } c \text{ out of both terms.]} $$

But this last equation says that $c \mid d$. Therefore, $d$ satisfies condition (ii).

Step 2: If $d$ is a positive integer that satisfies conditions (i) and (ii), then $d = (a, b)$.

Proof of Step 2: To prove that $d = (a, b)$, we must show that $d$ satisfies the requirements of the definition of the gcd, namely:

$d \mid a$ and $d \mid b$;
If $c \mid a$ and $c \mid b$, then $c \leq d$.

Obviously, $d$ satisfies (1) since requirement (1) and condition (i) are identical. To prove that $d$ satisfies requirement (2), suppose $c$ is an integer that divides both $a$ and $b$, then $c \mid d$ by condition (ii). Consequently, by the second Remark on page 9, $c \leq |d|$. But $d$ is positive, so $|d| = d$. Thus, $c \leq d$.

This proves that $d$ is the gcd of $a$ and $b$. $\blacksquare$

Theorem 1.4: Divisibility Condition

If $a \mid bc$ and $(a, b) = 1$, then $a \mid c$.

Proof of Theorem 1.4

Since $(a, b) = 1$, Theorem 1.2 shows that $au + bv = 1$ for some integers $u$ and $v$. Multiplying this equation by $c$ shows that $acu + bcv = c$. But $a \mid bc$, so that $bc = ar$ for some $r$. Therefore:

$$ c = acu + bcv = acu + (ar)v = a(cu + rv). $$

The first and last parts of this equation show that $a \mid c$, completing the proof. $\blacksquare$