Modular Arithmetic

Mr. Julius C. Reyes

 Introduction

Modular arithmetic is a system of arithmetic for

integers, which considers the remainder. In modular
arithmetic, numbers "wrap around" upon reaching a
given fixed quantity (this given quantity is known as the
modulus) to leave a remainder.

09/02/2023 PRESENTATION TITLE 2

An intuitive usage of modular
arithmetic is with a 12-hour
clock. If it is 10:00 now, then in 5
hours the clock will show 3:00
instead of 15:00. 3 is the
remainder of 15 with a modulus
of 12.
When we divide two integers, we will have an equation that looks like the
following:

A is the dividend
B is the divisor
Q is the quotient
R is the remainder

4
Sometimes, we are only interested in what the remainder is when we
divide A by B.

For these cases there is an operator called the modulo operator

(abbreviated as mod).

Using the same A, B, Q, and R as above, we would have: A mod B=R.

We would say this as A modulo B is equal to R. Where B is referred

to as the modulus.

5
Visualize modulus with clocks
Observe what happens when we
increment numbers by one and then
divide them by 3.

6
• The remainders start at 0 and increases by 1 each time, until the number
reaches one less than the number we are dividing by. After that, the sequence
repeats.
• By noticing this, we can visualize the modulo operator by using circles.
• We write 0 at the top of a circle and continuing clockwise writing integers 1,
2, ... up to one less than the modulus.
• For example, a clock with the 12 replaced by a 0 would be the circle for a
modulus of 12.

7
To find the result of A mod B we can follow these steps:
1.Construct this clock for size B

2.Start at 0 and move around the clock A step

3.Wherever we land is our solution.

(If the number is positive, we step clockwise, if it's negative,

we step counter-clockwise.)

8
EXAMPLE:
8 mod 4=?
With a modulus of 4 we make a clock with numbers 0, 1, 2, 3.
We start at 0 and go through 8 numbers in a clockwise sequence 1, 2, 3, 0, 1, 2,
3, 0.

8 mod 4 = 0

9
7 mod 2=?
With a modulus of 2 we make a clock with numbers 0, 1.
We start at 0 and go through 7 numbers in a clockwise sequence 1, 0, 1, 0, 1, 0,
1.

7 mod 2 = 1

10
−5 mod 3=?
With a modulus of 3 we make a clock with numbers 0, 1, 2.
We start at 0 and go through 5 numbers in counter-clockwise sequence (5 is
negative) 2, 1, 0, 2, 1.

−5 mod 3 = 1

11
1 .) What is -17 mod 10
-17 mod 10 =?

Get the Multiples of 10 so that ,if we add it from -17 our remainder will be
positive.
10, 20, 30…
20 is the least multiple of 10 that we can use to get a positive remainder.

• -17 + 20 = 3

• -17 mod 10 = 3 or in congruence -17 ≡ 3 mod 10

12
09/02/2023 PRESENTATION TITLE 13
What is 16 mod 12?
16 mod 12 = ?
16 divided by 12 is 1 remainder 4
16 mod 12 = 4 or 16 ≡ 4 mod 12

For this problem, suppose we wanted to evaluate -97 mod 11.

• Get the multiples of 11
• 9 (11) = 99
• -97 + 99 = 2
• -97 mod 11 = 2

14
Congruence Modulo
You may see an expression like:
A≡B (mod C) or A≡B (mod n)
This says that A is congruent to B modulo C. It is like the expressions we used
here, but not quite the same.
For a positive integer n, the integers a and b are congruent  mod  nif their
remainders when divided by n are the same.

15
Verify the following congruence
a.) 27 ≡ 2 mod 5
b.) 19 ≡ 4 mod 7

A.) Observe that 27 – 2 = 25 which is exactly divisible by 5, in fact = 5

Another way of defining this is that integers a and b are congruent  mod  n if their
difference (a−b) is an integer multiple of n, that is, if has a remainder of 0.

B.) 19 - 4 = 15
15 is not divisible by 7,n or that = which is not an integer . The congruence is
not correct.

16
Evaluate the following operations.
a. (15 + 18) mod 9 =
 15 + 18 = 33
 If you divide 33 by 9 , you will obtain a quotient of 3 and remainder of 6,
or = (3)(9)+6, which means the remainder is 6. Thus,
 (15+18) mod 9 ≡ 6
b. (41 +52) mod 5 =
 41 + 52 = 93
 93
 18
 93- 90 =3
 (41 + 52) mod 5 ≡ 3
17
c. (72- 35) mod 11 =
 72 -35 = 37
 37
 3
 37 – 33 = 4
 (72 -35) mod 11 = 4 or (72 -35) ≡ 4 mod 11
d. (13)(22) mod 6 =
 13 x 22 = 286
 286 6 = 47.66
 47 x 6 = 282
 286 – 282 = 4
 (13)(22) mod 6 = 4 or (13)(22) ≡ 4 mod 6
18
In 12-hour, clock, determine the time:
a.) 5 hours after 11 o’ clock
b.) 65 hours after 8 o’ clock
c.) 15 hours before 5 o’ clock
d.) 25 hours before 10 o’ clock

Solution
A.) 5 + 11 mod 12 =
16 mod 12 =
16
16 – 12 = 4
16 ≡ 4 mod 12 ( so the answer is 4 o’ clock )
19
B.) 65 hours after 8 o’ clock
8 + 65 mod 12 =
8 + 65 = 73
73
12 x 6 = 72
73 – 72 = 1
73 ( so the answer is 1 o’ clock )

C.) 15 hours before 5 o’ clock

5 – 15 mod 12 =
-10 mod 12 =
-10 + 12 = 2
-10 ( so the answer is 2 o’ clock ) 20
D.) 25 hours before 10 o’ clock
10 -25 mod 12 =
10 – 25 = -15
-15 mod 12 =
-15 + 24 = 9
-15 ( so the answer is 9 o’ clock )

21
1. What day of the week is 25 days from now if today is a Monday?
 Day of the week ( Monday, Tuesday, Wednesday, Thursday, Friday, Saturday,
and Sunday )
 Apply modulo 7
 25 mod 7 =
 25
 3 x 7 = 21
 25 – 21 = 4
 25 mod 7 = 4
Counting 4 days after Monday( take note, Monday is not included in the count) ,
you will get Friday

22
ISBN CODE ( INTERNATIONAL STANDARD BOOK NUMBER )
• ISBN was introduced as a scheme of regulating and keeping track of various
publications in different parts of the world.
• From 10-digit code it was expanded in 2007 to a 13-digit code.

the remaining digit except the last are used to identify the author and the
title of the book. The last digit, is called the check digit.
FORMULA:
= 10 – ( + 3 + + 3 + + 3 + +3 + +3 + +
3 mod 10
If = 10, then the check digit is 0

23
a. Determine the check digit of “ Larry Can’t Cook” 978-971-27-2769-?
= 10 – ( + 3 + + 3 + + 3 + +3 + +3 + +
3 mod 10
= 10 – [ 9 + 3(7) + 8 + 3(9) + 7 + 3(1) + 2 + 3(7) + 2 + 3(7) + 6 + 3(9) ]
mod 10
= 10 – (9 + 21 + 8 +27 + 7 + 3 + 2 + 21 + 2 + 21 + 6 + 27) mod 10
= 10 – ( 154 mod 10 )
= 10 – 4
=6

The check digit is 6

24
b. Determine if the ISBN CODE 978-971-27-2770-4 is valid or not
= 10 – ( + 3 + + 3 + + 3 + +3 + +3 + +
3 mod 10
= 10 – [9 + 3(7) + 8 + 3(9) + 7 + 3(1) + 2 + 3(7) + 2 + 3(7) + 7 + 3(0)]
mod 10
= 10 – ( 9 + 21 + 8 + 27 + 7 + 3 + 2 + 21 + 2 + 21 + 7 + 0) mod 10
= 10 – ( 128 mod 10 )
= 10 – 8
=2
The ISBN CODE is not VALID

25
Related to the ISBN is UPC ( Universal Product Code ) a 12-digit
code that usually accompanies the bar code of product. For UPC, the
last digit (or the 12th digit) is the check digit. Like in ISBN , it can be
computed using the
FORMULA:
= 10 – ( + + 3 + + + + 3 + + + + mod 10

If = 10 , then the check digit is 0

26
a. 3- 8137-115208 - ?
= 10 – ( + + 3 + + + + 3 + + + +
mod 10
= 10 – [ 3(3) + 8 + 3(1) + 3 + 3(7) + 1 + 3(1) + 5 + 3(2) + 0 + 3(8)]mod10
= 10 – ( 9 + 8 + 3 + 3 + 21 + 1 + 3 + 5 + 6 + 0 + 24 ) mod 10
= 10 – ( 83 mod 10 )
= 10 – 3
=7
The check digit is 7

27
CREDIT CARDS
Credit cards can be checked by doubling every number or digit starting from the
second to the last digit reading from left to right. Then summing up all the
resulting number. If the doubled digit results in a 2-digit number , simply treat
the two digits as separate digits. The card number is valid only if the sum of the
digits under modulo 10 is congruent to 0
EXAMPLE:
Determine if the credit card number is valid
a. 5234 8213 3410 1298
• 5234 8213 3410 1298
digits 5 2 3 4 8 2 1 3 3 4 1 0 1 2 9 8

Doubl
ed
28
( 10, 2, 6, 4, 16, 2, 2, 3, 6, 4, 2, 0, 2, 2, 18, 8 )

SUM = 1+0+2+6+4+1+6+2+2+3+6+4+2+0+2+2+1+8+8

SUM = 60
60 mod 10 =

60 mod 10 = 0
60
The indicated credit card is valid

29
Thank you