Page 260 - Discrete Mathematics and Its Applications

4.1 Divisibility and Modular Arithmetic 239

Therefore, a divides b + c. This establishes part (i) of the theorem. The proofs of parts (ii) and
(iii) are left as Exercises 3 and 4.

Theorem 1 has this useful consequence.

COROLLARY 1 If a, b, and c are integers, where a = 0, such that a | b and a | c, then a | mb + nc whenever
m and n are integers.

Proof: We will give a direct proof. By part (ii) of Theorem 1 we see that a | mb and a | nc
whenever m and n are integers. By part (i) of Theorem 1 it follows that a | mb + nc.

The Division Algorithm

When an integer is divided by a positive integer, there is a quotient and a remainder, as the
division algorithm shows.

THEOREM 2 THE DIVISION ALGORITHM Let a be an integer and d a positive integer. Then there
are unique integers q and r, with 0 ≤ r< d, such that a = dq + r.

We defer the proof of the division algorithm to Section 5.2. (See Example 5 and
Exercise 37.)

Remark: Theorem 2 is not really an algorithm. (Why not?) Nevertheless, we use its traditional
name.

DEFINITION 2 In the equality given in the division algorithm, d is called the divisor, a is called the dividend,
q is called the quotient, and r is called the remainder. This notation is used to express the
quotient and remainder:

q = a div d, r = a mod d.

Remark: Note that both a div d and a mod d forafixed d are functions on the set of inte-
gers. Furthermore, when a is an integer and d is a positive integer, we have a div d = a/d
and a mod d = a − d. (See exercise 18.)

Examples 3 and 4 illustrate the division algorithm.

EXAMPLE 3 What are the quotient and remainder when 101 is divided by 11?

Solution: We have

101 = 11 · 9 + 2.

Hence, the quotient when 101 is divided by 11 is 9 = 101 div 11, and the remainder is
2 = 101 mod 11. ▲