Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

276 PROPERTIES OF THE INTEGERS [CHAP. 11

EXAMPLE 11.12 Observe that 2≡8 (mod 6) and 5≡41 (mod 6). Then:

(a) 2+ 5 ≡ 8 +41 (mod 6) or 7≡49 (mod 6)

(b) 2· 5 ≡ 8 ·41 (mod 6) or 10≡328 (mod 6)

(c) Supposep(x)= 3 x^2 − 7 x+5. Then

p( 2 )= 12 − 14 + 5 =3 and p( 8 )= 192 − 56 + 5 = 141

Hence 3≡141 (mod 6).

Arithmetic of Residue Classes

Addition and multiplication are defined for our residue classes modulomas follows:

[a]+[b]=[a+b] and [a]·[b]=[ab]

For example, consider the residue classes modulom=6; that is,

[ 0 ],[ 1 ],[ 2 ],[ 3 ],[ 4 ],[ 5 ]

Then
[ 2 ]+[ 3 ]=[ 5 ], [ 4 ]+[ 5 ]=[ 9 ]=[ 3 ], [ 2 ]·[ 2 ]=[ 4 ], [ 2 ]·[ 5 ]=[ 10 ]=[ 4 ]

Thecontentof Theorem 11.22 tells us that the above definitions are well defined, that is, the sum and product of
the residue classes do not depend on the choice of representative of the residue class.
There are only a finite numbermof residue classes modulom. Thus one can easily write down explicitly
their addition and multiplication tables whenmis small. Figure 11-4 shows the addition and multiplication tables
for the residue classes modulom=6. For notational convenience, we have omitted brackets and simply denoted
the residue classes by the numbers 0, 1, 2, 3, 4, 5.

Fig. 11-4

Integers Modulom,Zm

Theintegers modulo m, denoted byZm, refers to the set

Zm={ 0 , 1 , 2 , 3 ,...,m− 1 }

where addition and multiplication are defined by the arithmetic modulomor, in other words, the corresponding
operations for the residue classes. For example, Fig. 11-4 may also be viewed as the addition and multiplication
tables forZ 6 , This means:

There is no essential difference betweenZmand the arithmetic of the residue

classes modulom, and so they will be used interchangeably.