692
Modeling Arithmetic, Computation, and Languages
example 7
Let Z 5 = 50, 1, 2, 3, 46 and define addition modulo 5, denoted by + 5 , on Z 5 by
x + 5 y = r, where r is the remainder when x + y is divided by 5. In other
words, x + 5 y = (x + y) mod 5. For example, 1 + 5 2 = 3 and 3 + 5 4 = 2.
Multiplication modulo 5 is defined by x # 5 y = (x # y) mod5. Thus, 2 # 5 3 = 1 and
3 # 5 4 = 2. Then 3Z 5 , + 5 4 is a commutative group, and 3Z 5 , # 5 4 is a commutative
monoid.
PrACtiCe 9
a. Complete the following tables defining + 5 and # 5 on Z 5 .
+ 5 0
1
2
3
4
0
1
3
2
3
4
#   5
0
1
2
3
4
0
1
2
1
3
2
4
b. What is an identity in 3Z 5 , + 5 4? In 3Z 5 , # 5 4?
c. What is an inverse of 2 in 3Z 5 , + 5 4?
d. Which elements in 3Z 5 , + 5 4 have inverses?
As we did on Z 5 , we can define operations of addition modulo n and multiplication modulo n on the set Z n = 50, 1, … , n − 16 where n is any positive
integer. Again 3Z n , + n 4 is a commutative group and 3Z n , # n 4 is a commutative
monoid. (See Exercise 47 for the relationship between the group 3Z n , + n 4 and the
set of equivalence classes under the binary relation of congruence modulo n.)
PrACtiCe 10
a. Give the table for # 6 on Z 6 .
b. Which elements in 3Z 6 , # 6 4 have inverses?
■
Notice that when we use a table to define an operation on a finite set, it
is easy to check for commutativity by looking for symmetry around the main
diagonal. It is also easy to find an identity element because its row looks like
the top of the table and its column looks like the side. And it is easy to locate
an inverse of an element. Look along the row until you find a column where the
identity appears; then check to see that changing the order of the elements still
gives the identity. However, associativity (or the lack of it) is not immediately
apparent from the table.
■