Page 259 - Discrete Mathematics and Its Applications

238 4 / Number Theory and Cryptography

later in this chapter, including generating pseudorandom numbers, assigning computer memory
locations to files, constructing check digits, and encrypting messages.

Division

When one integer is divided by a second nonzero integer, the quotient may or may not be
an integer. For example, 12/3 = 4 is an integer, whereas 11/4 = 2.75 is not. This leads to
Definition 1.

DEFINITION 1 If a and b are integers with a = 0, we say that a divides b if there is an integer c such that
b = ac, or equivalently, if b is an integer. When a divides b we say that a is a factor or divisor
a
of b, and that b is a multiple of a. The notation a | b denotes that a divides b. We write a | b
when a does not divide b.

Remark: We can express a | b using quantifiers as ∃c(ac = b), where the universe of discourse
is the set of integers.

In Figure 1 a number line indicates which integers are divisible by the positive integer d.
EXAMPLE 1 Determine whether 3 | 7 and whether 3 | 12.

Solution: We see that 3 | 7, because 7/3 is not an integer. On the other hand, 3 | 12 because
12/3 = 4. ▲

EXAMPLE 2 Let n and d be positive integers. How many positive integers not exceeding n are divisible by d?

Solution: The positive integers divisible by d are all the integers of the form dk, where k is
a positive integer. Hence, the number of positive integers divisible by d that do not exceed n
equals the number of integers k with 0 <dk ≤ n, or with 0 <k ≤ n/d. Therefore, there are
n/d positive integers not exceeding n that are divisible by d. ▲
Some of the basic properties of divisibility of integers are given in Theorem 1.

THEOREM 1 Let a, b, and c be integers, where a = 0. Then
(i) if a | b and a | c, then a | (b + c);
(ii) if a | b, then a | bc for all integers c;
(iii) if a | b and b | c, then a | c.

Proof: We will give a direct proof of (i). Suppose that a | b and a | c. Then, from the definition
of divisibility, it follows that there are integers s and t with b = as and c = at. Hence,
b + c = as + at = a(s + t).

–3d –2d –d 0 d 2d 3d

FIGURE 1 Integers Divisible by the Positive Integer d.