Page 264 - Discrete Mathematics and Its Applications

4.1 Divisibility and Modular Arithmetic 243
EXAMPLE 7
Associativity If a, b, and c belong to Z m , then (a + m b) + m c = a + m (b + m c) and
Additive inverses If a = 0 belongs to Z m , then m − a is an additive inverse of a modulo m and
Arithmetic Modulo m
We can define arithmetic operations on Z m , the set of nonnegative integers less than m, that is,
the set {0, 1,...,m − 1}. In particular, we define addition of these integers, denoted by + m by
a + m b = (a + b) mod m,
where the addition on the right-hand side of this equation is the ordinary addition of integers,
and we define multiplication of these integers, denoted by · m by
a · m b = (a · b) mod m,
where the multiplication on the right-hand side of this equation is the ordinary multiplication of
integers. The operations + m and · m are called addition and multiplication modulo m and when
we use these operations, we are said to be doing arithmetic modulo m.
Use the definition of addition and multiplication in Z m to find 7 + 11 9 and 7 · 11 9.
Solution: Using the definition of addition modulo 11, we find that
7 + 11 9 = (7 + 9) mod 11 = 16 mod 11 = 5,
and
7 · 11 9 = (7 · 9) mod 11 = 63 mod 11 = 8.
Hence 7 + 11 9 = 5 and 7 · 11 9 = 8. ▲
The operations + m and · m satisfy many of the same properties of ordinary addition and
multiplication of integers. In particular, they satisfy these properties:
Closure If a and b belong to Z m , then a + m b and a · m b belong to Z m .
(a · m b) · m c = a · m (b · m c).
Commutativity If a and b belong to Z m , then a + m b = b + m a and a · m b = b · m a.
Identity elements The elements 0 and 1 are identity elements for addition and multiplication
modulo m, respectively. That is, if a belongs to Z m , then a + m 0 = 0 + m a = a and a · m 1 =
1 · m a = a.
0 is its own additive inverse. That is a + m (m − a) = 0 and 0 + m 0 = 0.
Distributivity If a, b, and c belong to Z m , then a · m (b + m c) = (a · m b) + m (a · m c) and
(a + m b) · m c = (a · m c) + m (b · m c).
These properties follow from the properties we have developed for congruences and remainders
modulo m, together with the properties of integers; we leave their proofs as Exercises 42–44.
Note that we have listed the property that every element of Z m has an additive inverse, but no
analogous property for multiplicative inverses has been included. This is because multiplicative
inverses do not always exists modulo m. For instance, there is no multiplicative inverse of 2
modulo 6, as the reader can verify. We will return to the question of when an integer has a
multiplicative inverse modulo m later in this chapter.