Mathematics in the Modern World
Mathematical
Systems
Prepared by: Asst. Prof. Marcelo T. Buen
6.1 Modulo Arithmetic
In mathematics,
modular arithmetic
(sometimes called clock
arithmetic) is a system
of arithmetic for
integers, where numbers
wrap around after they
reach a certain value –
the modulus.
2
6.1 Modulo Arithmetic
Leonhard Euler
• pioneered the modern approach to
congruence in 1750, when he
explicitly introduced the idea of
congruence modulo a number N.
Carl Friedrich Gauss
• further advanced in his book
published in 1801
3
6.1 Modulo Arithmetic
For example, a 12-hr clock.
Once 12 is reached (AM or
PM) on the clock, we begin
again with 1.
3⊕8 8 ⊖ 11
9⊕8 2⊖8
8⊕7
10 ⊖ 7
We use ⊕ and ⊖ to denote addition and
subtraction on a 12-hr clock, respectively.
4
6.1 Modulo Arithmetic
Similar example involves
day-of-the-week arithmetic.
5⊞6 7 ⊟ 11
1 ⊞ 16
We use ⊞ and ⊟ to denote addition and subtraction
on a day-of-the-week arithmetic, respectively.
5
6.1 Modulo Arithmetic
related to that of the remainder in division
The operation of finding the
remainder is sometimes referred to as
the modulo operation.
6
6.1 Modulo Arithmetic
Dividing an integer Z by 5 will have
the remainders
{0 , 1 , 2 , 3 , 4}.
7
6.1 Modulo Arithmetic
Thus, we define Zn as the set of integers
from 0 , 1 , 2 ,…, n - 1 modulo n, i.e.
Zn = {0, 1, 2, …, n -1}
8
6.1 Modulo Arithmetic
In particular, we define Zn with the
following set of positive integers:
Z3 = {0, 1, 2}, modulo 3
Z5 = {0, 1, 2, 3, 4}, modulo 5
Z8 = {0, 1, 2 , 3 , 4 , 5, 6 , 7}, modulo 8
Note that Zn has exactly n non-negative integers.
9
6.1 Modulo Arithmetic
In Zn, modulo is simply the
remainder r when an integer 𝑎 ∈ ℤ
is simply divided by n.
𝐚
𝐡𝐚𝐬 𝐚 𝐫𝐞𝐦𝐚𝐢𝐧𝐝𝐞𝐫 𝐫 < 𝐧
𝐧
10
6.1 Modulo Arithmetic
Perform the following operations:
In Z8, what is 4 + 9?
Answer: 5
5 is the remainder when 13 is divided by 8.
11
6.1 Modulo Arithmetic
Perform the following operations:
In Z8, what is 15 + 21?
Answer: 4
12
6.1 Modulo Arithmetic
Perform the following operations:
In Z8, what is 106 + 102?
Answer: 0
13
6.1 Modulo Arithmetic
Perform the following operations:
In Z8, what is 22 - 3?
Answer: 3
14
6.1 Modulo Arithmetic
Perform the following operations:
In Z8, what is 3 - 20?
Answer: 7
15
6.1 Modulo Arithmetic
Perform the following operations:
In Z8, what is 11 5? .
Answer: 7
16
6.1 Modulo Arithmetic
Perform the following operations:
In Z15, what is 11 + 12?
Answer: 8
17
6.1 Modulo Arithmetic
Perform the following operations:
In Z15, what is 11 + 22?
Answer: 3
18
6.1 Modulo Arithmetic
Perform the following operations:
In Z15, what is 14 6? .
Answer: 9
19
6.1 Modulo Arithmetic
The Modulo Table
Zn is closed under the
In Z3 = {0, 1, 2}
binary operations of + 0 1 2
addition and 0 0 1 2
multiplication of 1 1 2 0
integers modulo n.
2 2 0 1
20
6.1 Modulo Arithmetic
The Modulo Table
Zn is closed under the
In Z3 = {0, 1, 2}
binary operations of . 0 1 2
addition and 0 0 0 0
multiplication of 1 0 1 2
integers modulo n.
2 0 2 1
21
6.1 Modulo Arithmetic
The Modulo Congruence
Two integers a and b are said to be
congruent modulo n,
𝒂−𝒃
where n is a natural number, if is an integer.
𝒏
𝒂 ≡ 𝒃 mod n
n: modulus
congruence
22
6.1 Modulo Arithmetic
TRUE or FALSE.
29 ≡ 8 mod 3
TRUE
29 −8
because 3 is 7
and 7 is an integer.
23
6.1 Modulo Arithmetic
TRUE or FALSE.
15 ≡ 4 mod 6
FALSE
15 −4 5
because is 16
6
5
and 1 is NOT an integer.
6
24
6.1 Modulo Arithmetic
TRUE or FALSE.
37 ≡9 mod 7
TRUE
25
6.1 Modulo Arithmetic
TRUE or FALSE.
115 ≡ 10 mod 3
TRUE
26
6.1 Modulo Arithmetic
TRUE or FALSE.
84 ≡3 mod 9
TRUE
27
6.1 Modulo Arithmetic
Equations Involving Modulo Congruence
Solving a congruence equation means finding all whole number values of the
variable for which the congruence is true.
Solve 3x + 5 ≡ 3 mod 4.
If x = 0, is 3(0) + 5 ≡ 3 mod 4? No
If x = 1, is 3(1) + 5 ≡ 3 mod 4? No
2 , 6, 10, … are
If x = 2, is 3(2) + 5 ≡ 3 mod 4? Yes solutions to
If x = 3, is 3(3) + 5 ≡ 3 mod 4? No 3x + 5 ≡ 𝟑 𝐦𝐨𝐝 𝟒
If x = 4, is 3(4) + 5 ≡ 3 mod 4? No
If x = 5, is 3(5) + 5 ≡ 3 mod 4? No
If x = 6, is 3(6) + 5 ≡ 3 mod 4? Yes
28
6.1 Modulo Arithmetic
Equations Involving Modulo Congruence
Solve 2x + 1 ≡ 3 mod 10 .
1 , 6, 11, … are
solutions to
2x + 1 ≡ 𝟑 𝐦𝐨𝐝 𝟏𝟎
29
6.1 Modulo Arithmetic
Additive Inverse
In Zn, two numbers a and b are additive
inverse of each other if a + b ≡ 0 mod n.
30
6.1 Modulo Arithmetic
Additive Inverse
In Zn, two numbers a and b are additive
inverse of each other if a + b ≡ 0 mod n.
Example: Find the additive inverse of
7 in mod 16
Answer: 9
because 7 + 9 = 0 mod 16
31
6.1 Modulo Arithmetic
Additive Inverse
In Zn, two numbers a and b are additive
inverse of each other if a + b ≡ 0 mod n.
Example: Find the additive inverse of
2 in mod 12
Answer: 10
32
6.1 Modulo Arithmetic
Additive Inverse
In Zn, two numbers a and b are additive
inverse of each other if a + b ≡ 0 mod n.
Example: Find the additive inverse of
5 in Z7
Answer: 2
33
6.1 Modulo Arithmetic
Multiplicative Inverse
In Zn, two numbers a and b are multiplicative
inverse of each other if ab ≡ 1 mod n.
Example: Find the multiplicative inverse of
5 in Z7
Answer: 3
because (5)(3) = 1 mod 7
34
6.1 Modulo Arithmetic
Multiplicative Inverse
In Zn, two numbers a and b are multiplicative
inverse of each other if ab ≡ 1 mod n.
Example: Find the multiplicative inverse of
3 in Z10
Answer: 7
because (3)(7) = 1 mod 10
35
6.1 Modulo Arithmetic
Multiplicative Inverse
In Zn, two numbers a and b are multiplicative
inverse of each other if ab ≡ 1 mod n.
Example: Find the multiplicative inverse of
4 in mod 6
Answer: none
36
6.1 Modulo Arithmetic
Every number has an additive
inverse but not necessarily a
multiplicative inverse.
37
6.2 Applications of Modulo Arithmetic
Applications of
Modulo Arithmetic
38
6.2 Applications of Modulo Arithmetic
Zeller’s congruence
39
6.2 Applications of Modulo Arithmetic
Zeller’s congruence
Where:
d = date of the month
m = month (3 = March, 4 = April, 5 = May .....13 = Jan, 14 = Feb)
y = year (last two digits of the year)
c = century (first two digits of the year)
x = day (0 = Saturday, 1 = Sunday, 2 = Monday...)
40
6.2 Applications of Modulo Arithmetic
Zeller’s congruence
Cautions:
[x] is the rounded down value of x.
Jan and Feb are the 13th and 14th months of the
previous year.
January 20, 2011 is like the 13th month of 2010
41
6.2 Applications of Modulo Arithmetic
On what day is University
of Santo Tomas founded?
April 28, 1611
13(4 + 1) 11 16
𝑥 = 28 + + 11 + + + 5(16) mod7
5 4 4
𝑥 = 28 + 13 + 11 + 2 + 4 + 80 mod7
x = 138 mod 7
x=5
42
6.2 Applications of Modulo Arithmetic
On what day is
January 15, 2019
13(13 + 1) 18 20
𝑥 = 15 + + 18 + + + 5(20) mod7
5 4 4
𝑥 = 15 + 36 + 18 + 4 + 5 + 100 mod7
x = 178 mod 7
x=3
43
6.2 Applications of Modulo Arithmetic
Determine the day you
were born.
46
