Page 263 - Discrete Mathematics and Its Applications

242 4 / Number Theory and Cryptography

THEOREM 5 Let m be a positive integer. If a ≡ b(mod m) and c ≡ d(mod m), then

a + c ≡ b + d(mod m) and ac ≡ bd (mod m).

Proof: We use a direct proof. Because a ≡ b(mod m) and c ≡ d(mod m), by Theorem 4 there
are integers s and t with b = a + sm and d = c + tm. Hence,

b + d = (a + sm) + (c + tm) = (a + c) + m(s + t)
and

bd = (a + sm)(c + tm) = ac + m(at + cs + stm).

Hence,

a + c ≡ b + d(mod m) and ac ≡ bd (mod m).

EXAMPLE 6 Because 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5), it follows from Theorem 5 that
18 = 7 + 11 ≡ 2 + 1 = 3 (mod 5)

and that

77 = 7 · 11 ≡ 2 · 1 = 2 (mod 5). ▲
We must be careful working with congruences. Some properties we may expect to be true
are not valid. For example, if ac ≡ bc (mod m), the congruence a ≡ b(mod m) may be false.
You cannot always Similarly, if a ≡ b(mod m) and c ≡ d(mod m), the congruence a ≡ b (mod m) may be
c
d
divide both sides
of a congruence false. (See Exercise 37.)
by the same number! Corollary 2 shows how to find the values of the mod m function at the sum and product of
two integers using the values of this function at each of these integers. We will use this result in
Section 5.4.

COROLLARY 2 Let m be a positive integer and let a and b be integers. Then

(a + b) mod m = ((a mod m) + (b mod m)) mod m

and

ab mod m = ((a mod m)(b mod m)) mod m.

Proof: By the definitions of mod m and of congruence modulo m, we know that a ≡
(a mod m) (mod m) and b ≡ (b mod m) (mod m). Hence, Theorem 5 tells us that

a + b ≡ (a mod m) + (b mod m) (mod m)
and

ab ≡ (a mod m)(b mod m) (mod m).

The equalities in this corollary follow from these last two congruences by Theorem 3.