CHAPTER 9.
Mathematical System–
Introduction
to Modular Arithmetic
Core Idea
“Mathematics creates connections and fosters efficiency
through visual tools like graphs and algorithms.”
learning objectives
1. perform clock arithmetic;
2. describe modulus and congruence;
3. verify different modular congruence;
4. perform addition and subtraction modulo !; and
5. calculate time or day using modulo.
challenge… It’s Your BirthDAY
TUESDAY
MONDAY WEDNESDAY
What day of the week
where you born?
THURSDAY FRIDAY
SATURDAY SUNDAY
MODULAR ARITHMETIC is also called as
“clock arithmetic”.
In real life, this idea can
also be used to deal
with “time” in terms of
a 12-hour clock .
MODULAR ARITHMETIC
Addition on a 12-hour clock
Notation: ⊕
1. What is 8 hours after 3 o’clock?
3 ⨁ 8 = 11 o’ clock
MODULAR ARITHMETIC
Addition on a 12-hour clock
Notation: ⊕
2. What is 8 hours after 9 o’clock?
9 ⨁ 8 = 5 o’ clock
MODULAR ARITHMETIC
Subtraction on a 12-hour clock
Notation: ⊝
3. If the time now is 3 o’clock,
what is the time 7 hours ago?
3 ⊝ 7 = 8 o’ clock
MODULAR ARITHMETIC
Subtraction on a 12-hour clock
Notation: ⊝
4. What is 7 hours before 10 o’clock?
10 ⊝ 7 = 3 o’ clock
MODULAR ARITHMETIC
Evaluate each of the following,
where ⊕ and ⊝ indicate addition
and subtraction, respectively, on a
12-hour clock.
1. 8⨁7 = 3 o’ clock
2. 7 ⨁ 12 = 7 o’ clock
3. 8 ⊝ 11 = 9 o’ clock
4. 2⊝8 = 6 o’ clock
MODULO n
Two integers ! and " are said to be congruent
!%"
modulo # , where $ is a natural number, if is an
#
integer. In this case, we write ! ≡ " '() #.
The number # is called the modulus.
The statement ! ≡ " '() # is called a congruence.
Determine whether the following congruence is true or false.
1. 29 ≡ 8 mod 3 3. 7 ≡ 12 mod 5
2. 15 ≡ 4 mod 6 4. 15 ≡ 1 mod 8
MODULO n
!%"
Two integers ! and " are said to be congruent modulo # , where $ is a natural number, if is an
#
integer. In this case, we write ! ≡ " '() #.
The number # is called the modulus.
The statement ! ≡ " '() # is called a congruence.
Determine whether the following congruence is true or false
a b n
1. 29 ≡ 8 mod 3 2. 15 ≡ 4 mod 6 3. 7 ≡ 12 mod 5 4. 15 ≡ 1 mod 8
<%;7 ;=%;
=
78%9
=
;=%> = =
: = 9
?
7; ;; %= ;>
= = = =
: ? = 9
EFGHD = −; EFGHD
= < ABCD
ABCD
MODULO n Days of the Week
Consider a day-of-the-week Monday = 1 Friday = 5
arithmetic. Suppose each day Tuesday = 2 Saturday = 6
is associated with a number as Wednesday = 3 Sunday = 7
shown on the right.
Thursday = 4
1. What is 6 days after Friday? 5 ⨁ 6 = 11 − 7 = 4 Hence, 6 days after
Friday is Thursday.
2. What is 16 days after Monday?
1 ⨁ 16 1 + 16 ≡ ___ mod 7 2
→ 17 ≡ ___ mod 7
7 17
14
17 ≡ / mod 7 3
Hence, 16 days after Monday is Wednesday.
MODULO n Days of the Week
Consider a day-of-the-week Monday = 1 Friday = 5
arithmetic. Suppose each day Tuesday = 2 Saturday = 6
is associated with a number as Wednesday = 3 Sunday = 7
shown on the right.
Thursday = 4
3. If today is Friday, what day is it 16 days from now?
5 ⨁ 16 5 + 16 ≡ ___ mod 7 3
→ 21 ≡ ___ mod 7
7 21
21
17 ≡ 0 or 7 mod 7 0 Ifthethere is no remainder, let
answer be equal to the
value of the modulus /.
Hence, 16 days after Friday is Sunday.
MODULO n Days of the Week
Consider a day-of-the-week Monday = 1 Friday = 5
arithmetic. Suppose each day Tuesday = 2 Saturday = 6
is associated with a number as Wednesday = 3 Sunday – 7
shown on the right.
Thursday = 4
1. If July 4, 2010 was a Sunday, what day of the week is
July 4, 2015? 261
7 1833
2010 ↔ 2015 = 5 years 7 + 1826 ≡ ___ mod 7 1827
1 leap year → 2012 6
1833 ≡ , mod 7
Total number of days:
5(365) +1 = 1826
Hence, July 4, 2015 is Saturday.
MODULO n Days of the Week
Monday = 1 Friday = 5
Consider a day-of-the-week
Tuesday = 2 Saturday = 6
arithmetic. Suppose each day
is associated with a number as Wednesday = 3 Sunday = 7
shown on the right. Thursday = 4
2. In 2008, Abraham Lincoln’s birthday fell on Tuesday, February 12.
On what day of the week does Lincoln’s birthday fall in 2017?
470
2008↔ 2017 = 9 years 7 3290
3 leap years → 2008,2012,2016 2 + 3,288 ≡ ___ mod 7 3290
0
Total number of days: 3,290 ≡ 0 ./ 7 mod 7
9(365) +3 = 3,288
Hence, February 12, 2017 is Sunday.
ARITHMETIC OPERATIONS MODULO n
Addition Modulo !
Evaluate the following:
1. (23 + 38) mod 12 2. (51 + 72) mod 3
61 mod 12 123 mod 3
1 0
Moreover, adding the modulus to a number does not change the value and can
generate another congruence.
Examples: Generate a congruence equivalent to the following.
3. 13 ≡ 6 mod 7 4. 10 ≡ 1 mod 3
7 7 3 3
20 ≡ 13 mod 7 13 ≡ 4 mod 3
ARITHMETIC OPERATIONS MODULO n
Subtraction Modulo !
Evaluate the following:
1. (33 – 16) mod 6 2. (14 – 27) mod 5
17 mod 6 -13 mod 6
5 5 mod 6
5
Find the value of # .
3. 37 – 13 ≡ # mod 15 4. 21 – 43 ≡ # mod 7
24 ≡ # mod 15 -22 ≡ # mod 15
x=9 x=8
End of Discussion…