3.7 Modular Arithmetic
3.7.1 Introduction:
Let us
look at the Calendar of May 2006 which is given on the right hand side. 1^{st}
date of the month is Monday. What day is 29th of that month? It is Monday
again. How did we arrive at that? If 1^{st}
is Monday then next Mondays are 1,8,15,22,29
Why is this so? This is
because days repeat after every 7 days. Mathematically we say 8_{}1(modulo 7) which implies that 7 exactly divides (81) 15 _{}1(mod 7) which implies that 7 exactly divides (151) 22 _{}1(mod 7) which implies that 7 exactly divides (221) In
general when x_{}y(mod m ) we mean that m exactly divides (xy). The above
statement can also be represented by If xy _{}0(mod m) then (xy)/m = is an integer. ‘_{}’ is pronounced as congruent 

We know that when we divide
any positive integer by another positive integer say ‘m’, the reminders has to
be among the set {0,1,2,3,4…..(m1)}.
The numbers 0,1,2,….(m1) are called residues of mod m.
The set Z_{m}= {0,1,2,3,4…..(m1)}is called the set of mod m.
Definition
: The ‘residue set’ of mod m is the possible set of reminders when a number
is divided by m and is represented by
Z_{m}= {0,1,2,3,4…..(m1)}
3.7.1 Example 1: Write the residues when a positive integer is
divided by 10
Solution :
The possible reminders when
10 is a divisor are
0,1,2,3….9
Therefore Z_{10}=
{0,1,2,3,4,5,6,7,8,9}
Will it be possible to
define addition and multiplication operations under the
modulo system?
Definition: If mod is m then
The symbol for addition
is _{} with m as subscript
to the symbol.
The symbol for
multiplication is _{}with m as subscript to the symbol.
We define
1. a +_{m} b _{} r (=reminder of
(a+b)/m)
2. a _{}_{m} b _{} r (=reminder of
(a*b)/m)
3.7.1 Example 2 :
Find 10 +_{12} 2 +_{12} 3
Solution :
10 +_{12} 2 +_{12}
3
=(10
+_{12} 2) +_{12} 3
=0+_{12} 3(_{}reminder of (10+2)/12 = 0)
= 3(_{}reminder of 3/12 is 3)
3.7.1 Example 3 :
Find 4 _{}_{11 }3 _{}_{11} 7
Solution :
4 _{}_{11 }3 _{}_{11} 7
=(4
_{}_{11 }3) _{}_{11} 7
= 1 _{}_{11} 7(_{}reminder of (4*3)/11 = 1)
=7 (_{}reminder of (1*7)/11 = 7)
3.7.1 Example 4 : What is
the value of y if y_{}y _{}1(mod 8)
Solution :
Since y_{}y _{}1(mod 8)
8 should divide y*y with
reminder = 1
_{} (y^{2}1)/8
= 0.
This is possible only if
y=3.
Verification:
3_{}_{8 }3 =1(_{}reminder of (3*3)/8 = 1) which is as given in the problem.
3.7.2 Caley’s Table:
The Caley’s table is a
representation of modular arithmetic operation.
The results of modulo
operations (addition and multiplication) on a given set, when represented in a
table format is called Caley’s table.
Let us represent Caley’s
table for addition operation (a_{}b) for mod 4.
Since
the residues of mod 4 can only be 0 or 1 or 2 or 3, we calculate a+_{4}b only for a =0,1,2,3 and b=
0,1,2,3.The set on which Caley’s table is arrived at is Z_{4}= {0,1,2,3} 
The
results of the operation [a_{}b mod 4] (denoted
by +_{4}) 

0 +_{4} 0 _{} 0 0 +_{4} 1 _{}1
0 +_{4 }2 _{} 2 0 +_{4 }3 _{} 3 1 +_{4}
0 _{} 1 1 +_{4} 1 _{}2 1
+_{4 }2 _{} 3 1 +_{4 }3 _{} 0 2
+_{4} 0 _{} 2 2 +_{4} 1 _{}3 2 +_{4
}2 _{} 0 2 +_{4 }3 _{} 1 3 +_{4} 0 _{} 3 3 +_{4} 1 _{}0 3 +_{4
}2 _{} 1 3 +_{4 }3 _{} 2 


Observe that the results in the table (Green Color Numbers) also belong to the set Z_{4}= {0,1,2,3} 
Since the
residues of mod 4 can only be 0 or 1 or 2 or 3, we calculate a X_{4}b
only for a =0,1,2,3 and b=
0,1,2,3.The set on which Caley’s table is arrived at is Z_{4}= {0,1,2,3} 
The
results of the operation [a_{}b mod4] (denoted by X_{4}) 

0 X_{4 }0 _{} 0 0 X_{4} 1 _{}0
0 X_{4 }2 _{} 0 0 X_{4 }3 _{} 0 1 X_{4}
0 _{} 0 1 X_{4 }1 _{}1 1
X_{4 }2 _{} 2 1 X_{4 }3 _{} 3 2
X_{4} 0 _{} 0 2 X_{4} 1 _{}2 2 X_{4
}2 _{} 0 2 X_{4 }3 _{} 2 3 X_{4} 0 _{} 0 3 X_{4} 1 _{}3 3 X_{4
}2 _{} 2 3 X_{4 }3 _{} 1 


Observe that the results in the table (Green Color Numbers) also belong to the set Z_{4}= {0,1,2,3} 
3.7.2 Problem 1
: Construct
Caley’s Table for Q ={0,2,4,6,8} under _{} mod 10
Solution
:
We are required to arrive
at values of a_{}b mod 10 when a, b _{} to the set Q= {0,2,4,6,8}
Since 0 is reminder of
(6+4)/10, 2 is reminder of (6+6)/10 and
4 is reminder of (8+6)/10
We get
6
+_{10} 4 _{} 0 6 +_{10} 6 _{}2 8 +_{10
}6 _{} 4
Similarly we can arrive at
the remainders for other values of a and b.
bà 
0 
2 
4 
6 
8 
a 
a +_{10 }b= 

0 
0 
2 
4 
6 
8 
2 
2 
4 
6 
8 
0 
4 
4 
6 
8 
0 
2 
6 
6 
8 
0 
2 
4 
8 
8 
0 
2 
4 
6 
3.7.2 Problem 2
: Construct
Caley’s Table for A = {1,5,7,11} under _{} mod 12
We are required to arrive
at values of a_{}b mod 12 when a, b _{} to the set A ={1,5,7,11}
Since 1 is reminder of
(7*7)/12 , 5 is reminder of (7*11)/12 and 1 is
reminder of (11*11)/12
We get
7
_{}_{12}7 _{} 1 7 _{}_{12 }11 _{}5 11 _{}_{12 }11 _{} 1
Similarly we can arrive at
the remainders for other values of a and b.
bà 
1 
5 
7 
11 
a 
a _{}_{12 }b = 

1 
1 
5 
7 
11 
5 
5 
1 
11 
7 
7 
7 
11 
1 
5 
11 
11 
7 
5 
1 
3.7 Summary of learning
No. 
Points learnt 
1 
Definition
of Modulo operations 
2 
Modulo
addition and multiplication 
3 
Caley’s
Table 