MODULAR
ARITHMETIC
MODULE 1
STEM Teach Mapúa 2024
Introduction
Modular Arithmetic
Welcome to the world of modular arithmetic!
In this lesson, we will explore the basics of modular arithmetic and
how it can be applied to solve various mathematical problems.
Modular arithmetic is particularly useful in many areas, including
number theory, cryptography, and computer science.
It allows us to perform calculations efficiently and solve problems that
involve periodic patterns or repeating sequences.
Intended Learning Outcomes
At the end of the module, the participants will be
able to:
perform fundamental operations in modular
arithmetic.
apply modular inverses to solve equations.
find solutions to modular equations.
apply modular arithmetic operations to solve
problems involving remainders and periodic
patterns.
Intended Learning Outcomes
explore how modular arithmetic can be used
to calculate day of the week for a given date.
Use modular arithmetic to verify the validity of
credit cards, ISBN and UPC codes.
Lesson 1
The Arithmetic Modulo n
Welcome to today's lesson on modular arithmetic. Now, you
might be wondering, what exactly is modular arithmetic?
Well, modular arithmetic is a fascinating branch of mathematics
that deals with remainders.
In this lesson, we focus on numbers and their remainders when
divided by a fixed positive integer called the modulus.
Lesson 1
The Arithmetic Modulo n
Perhaps the best representation of modular arithmetic is a clock
which repeats itself after 12 hours.
Imagine you have a clock that resets every 12 hours. If it's 10
o'clock now and 5 hours pass, what time will it be?”
The expected answer is 3 o’clock.
This repeating process of a clock is what modular arithmetic is all
about.
Definition
Modulo n
Consider two integers and and a natural number .
Then and are congruent modulo (or is congruent to
modulo ) if the difference is exactly divisible by .
Definition
Modulo n
In symbols,
(mod ) whenever is an integer.
The symbol or is used to denote congruence.
The natural number is commonly termed as the modulus of the
congruence .
Definition
Modulo n
The modular value is actually the remainder when a
given number is divided by the modulus.
Consequently, the modular value should be less than
the modulus.
As a matter of convention, only natural numbers are
allowed when getting the modular value of a number
Example 1
Verify the following congruence:
a. 27 2 mod 5
b. 19 4 mod 7
Example 1
a. 27 2 mod 5
Note that 27 – 2 = 25, which is divisible by 5.
In fact, .
Thus, the congruence is correct.
b. 19 4 mod 7
Observe that is not an integer.
The congruence is not true.
Arithmetic Operations Modulo n
■Perform the arithmetic operation and
then divide by the modulus. The answer is
the remainder.
Example 2 Addition Modulo n
Evaluate (15 + 28) mod 7
Solution
First add 15 + 28 to get 43
Get the modular value of 43:
So, the remainder is 1
Therefore, (15 + 28) mod 7 = 1
Equivalently, we can say (15 + 28) 1 (mod 7)
Example 3 Subtraction Modulo n
Evaluate (72 - 35) mod 11
Solution
First obtain the difference: 72 – 35 = 37
Get the modular value of 37:
So, the remainder is 4
Therefore, (72 - 35) mod 11 = 4
Equivalently, we can say (72 - 35) 4 (mod 11)
Example 4 Negative Remainder
Evaluate (12 - 27) mod 4
Solution
First obtain the difference: 12 – 27 = -15
Get the equivalent positive modular value of -15:
So, the remainder is -3 which is equivalent to (-3+modulus=-3+4)=1
Therefore, (12 - 27) mod 4 = 1
Equivalently, we can say (12 - 27) 1 (mod 4)
Example 5 Multiplication Modulo n
Evaluate (44)(29) mod 23
Solution
First multiply: (44)(29) = 1276
Get the modular value of 1276:
So, the remainder is 11
Therefore, (44)(29) mod 23 = 11
Equivalently, we can say (44)(29) 11 (mod 23)
Example 6 Clock Problem
Disregarding A.M. or P.M., if it is 8 o’clock now, what
time was it 47 hours ago?
Solution
8-47= -39 X mod 12
x = -3 = -3 + 12 = 9
Thus, time was 9:00.
Exercise
Evaluate the following
a. (77 + 26) mod 13
b. (25 – 42) mod 8
c. (18)(43) mod 15
Solving Congruence Equations
■Solve
■ Solution: 2x + 12 – 7 = 2x + 5
■ Try x=0,1,2 (mod 3)
■ For x=0, 2(0) + 5 = 5 (not congruence)
■ For x = 1, 2(1) + 5 = 7 (not congruence)
■ For x = 2, 2(2) + 5 = 9 (congruence)
Solving Congruence Equations
■ In general, once a solution is determined, additional
solutions can be found by repeatedly adding the
modulus to the original solution.
■ Thus, the solutions are 2, 5, 8, 11, 14, ....
Identity and Inverse elements in
modular arithmetic
1. Like in ordinary addition and multiplication, 0 and 1
are the identity elements for modular addition and
modular multiplication, respectively.
2. For positive integers and , the integer is an additive
inverse under modulo if (mod ).
3. For positive integers and , the integer is a
multiplicative inverse of under modulo if (mod ).
Identity and Inverse elements in
modular arithmetic
Remarks:
1. Unlike in ordinary addition and multiplication, the inverse elements for
modular addition and multiplication are not unique. In fact, the
multiplicative inverse of under modulo may not even exist if and are not
relatively prime (that is, must be 1).
2. If is an additive inverse of mod , then we can write:
(mod )
Here, the symbol “” is aptly read “additive inverse of ”, rather than simply
saying “negative ”. Similarly, the symbol or should mean “multiplicative
inverse of ” and not simply “reciprocal of ”.
Example 1
What is the additive inverse of 9 mod 15?
Here, we need only to find a number such that
9 + b 0 (mod 15)
Clearly, satisfies this congruence, that is, 9 + 6 = 15 (mod 15).
Thus, we can write (mod 15) or equivalently, (mod 15) = 6.
Note that also satisfies the congruence, since
9 + 21 = 30 0 (mod 15)
In general, the additive inverse of 9 are those numbers that are congruent to 6 (mod 15)
(e.g., 21, 36, 51, and so on).
Example 2
What is the multiplicative inverse of 3 mod 5?
By definition, the multiplicative inverse of 3 mod 5 is a number that satisfies
the congruence
(3)(d) 1 (mod 5)
The possible remainders under modulo 5 are: 0, 1, 2, 3, 4
By substitution, we can verify that satisfies the congruence.
Thus, we can now write
2 (mod 5) or (mod 5)
Other than , there are other possible inverses of 3: 7,12,17,….
Example 3
What is the multiplicative inverse of 4 mod 12?
By definition, the multiplicative inverse of 4 mod 12 is a number that satisfies
the congruence
(4)(d) 1 (mod 12)
The possible remainders under modulo 12 are: 0, 1, 2, 3, …,11
Doing trial-and-error: (4)(0)=0, (4)(1)=4, (4)(2)=8, (4)(3)=12, (4)(4)=16, (4)(5)=20,
(4)(6)=24, (4)(7)=28, (4)(8)=32, (4)(9)=36, (4)(10)=40, (4)(11)=44.
None of the resulting product is congruent to 1 (mod 12).
In this case, the multiplicative inverse of 4 (mod 12) does not exist.
Exercise:
1. What is the additive inverse of 15 mod 12?
2. What is the multiplicative inverse of 7 mod 13?
3. What is the multiplicative inverse of 15 mod 6?
Lesson 2 Practical Applications
In this part of module 1, we will discuss
some of the practical applications of
Modular arithmetic.
Let’s start our lesson with the definition of
floor fuction.
The Floor Function
■In the floor function of x, we take the
highest integer less than x.
■The symbol for the floor function of x is .
■Examples:
How to Calculate the Day of the Week
■ where D is the day of the week using 1 for Monday, ..., 6 for Saturday, 7 for
Sunday)
■ d is the day of the month
■ m is the month using 1 for March, 2 for April, ..., 10 for December while 11
for January and 12 for February
■ x is the first two digits of the year
■ y is the last two digits of the year if the month is March through December;
if the month is January or February, the last two digits minus 1.
Example 1
Determine the day of the week on which Abraham Lincoln’s birthday
(February 12) will fall in 2155.
Solution
We have d = 12, m=12, x=21, y = 55-1=54
D = 31 + 13 + 5 + 24 = 73
= 3 (mod 7)
Answer is Wednesday.
Example 2
What day of the week is August 21 in 2019 if it fell on a
Saturday in 1993?
Solution:
The year 1993 covered 132 days from August 22 to December 31 while
2019 will cover 233 days from January 1 to August 21.
The indicated period covers six leap years (1996, 2000, 2004, 2008,
2012, 2016), each year contributing 366 days.
All remaining years will add 365 days each. All in all, there are 9,496
days from August 22, 1993 to August 21, 2019. Now,
9,496 4 (mod 7).
Counting 4 days after Saturday, you will get Wednesday.
Example 3
Stephen celebrated her 12th birthday on February 25,
2018, a Sunday. What day of the week was she born?
Solution:
Stephen was born on February 25, 2006. Verify that there are 4,383
days covered in the 12-year period.
Since you moved backward, you should consider the number of days
as negative (to distinguish the forward time being positive). Now,
–4,383 –1 (mod 7) 6 (mod 7)
(either move one day backward or 6 days forward).
Thus, February 25 fell on a Saturday in 2006.
International Standard Book Number (ISBN)
The International Standard Book Number (ISBN) was introduced
as a scheme of regulating and keeping track of various
publications in different parts of the world.
Every published book including electronic, paperback, hardcover
—is assigned a distinctive ISBN code.
This 13-digit number is designed to improve the accuracy of book
orders and ensure correct cataloging of books.
In the Philippines, the National Library of the Philippines (NLP)
takes charge of the ISBN registration, allocation, and designation
for Filipino publishers and authors.
ISBN Code Formula
■ The first three digits of an ISBN are 978, the next digit
indicates the country in which the publisher is incorporated (0,
and sometimes 1, for books written in English), the next two to
seven digits indicate the publisher, the next group of digits
indicates the title of the book, and the last digit, x13 is called
the check digit.
The check digit can be obtained using the formula
x13 = 10 – (x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + x7 + 3x8 + x9 + 3x10 + x11 +
3x12) mod 10
If x13 = 10, then the check digit is 0.
Example 1:
Determine the check digit for the book “Larry
Can’t Cook”: 978-971-27-2769-?
Solution:
x13 = 10 – [9+3(7)+8+3(9)+7+3(1)+2+3(7)+2+3(7)+6+3(9)] mod 10
= 10 – (154 mod 10) = 10 – 4 = 6
The check digit is 6.
Example 2:
Determine if the ISBN code 978-971-37-2771-4 is
valid or not.
Solution:
x13 = 10 – [9+3(7)+8+3(9)+7+3(1)+3+3(7)+2+3(7)+7+3(1)] mod 10
= 10 – (132 mod 10)
= 10 – 2
=8 4
The ISBN code is not valid.
Exercise
A purchase order for the book The
Mathematical Tourist by Ivars Peterson
includes the ISBN 978-0-760-73261-6.
Determine whether this is a valid ISBN.
Universal Product Code (UPC)
■ Another coding system closely related to the ISBN is
the UPC (Universal Product Code), extensively used in
various items, especially in grocery stores.
■ It aids in pricing goods and offers store managers
precise data on inventory and customer purchasing
patterns.
Universal Product Code (UPC)
The UPC (Universal Product Code) number is a 12-digit code
that usually accompanies the bar code of a product.
It satisfies a congruence equation similar to the one for
ISBN. The last digit (or the 12th digit) is the check digit.
The code can be computed using the formula
X12 = 10 – (3x1+x2+3x3+x4+3x5+x6+3x7+x8+3x9+x10 +3x11) mod
10
If x12 = 10, then the check digit is 0.
Example
Determine the validity of the UPC 036000291452.
■ Sum of the digits in odd positions times 3:
■ (0+6+0+2+1+5)3 = 14 (3) = 42
■ Sum of the digits in even positions.
■ 3+0+0+9+4 = 16
■ Total = 42 + 16 = 58 (mod 10) = 8
■ Check digit = 10 – 8 = 2
■ Hence, the code is valid.
Exercise
■You can typically find UPC on the
packaging of a Coca-Cola can. Find the
check digit of a 12-oz coke in can
whose first 11 digits are 04900004212.
Credit Card Numbers.
Credit card numbers can be easily checked through the
“check digit” which also uses mod 10 arithmetic.
In the Philippines, Visa and Mastercard are the dominant
credit cards in the market, normally having 16-digit numbers
except for some Visa cards that have 13 digits only.
The Luhn Algorithm
To validate credit card numbers, double every other
digit starting from the first (leaving the last digit as
the check digit).
Then, sum all the resulting numbers.
If any of the doubled digits produce a two-digit
number, separate those two digits and add them
individually.
It is a valid credit card number if the sum is divisible
by 10.
EXAMPLE
Determine which credit card number is valid and
which is not.
a. 5234 8213 3410 1298
b. 6011 0123 9145 2317
EXAMPLE
Solution:
a. 5234 8213 3410 1298
Sum = 1+0+2+6+4+1+6+2+2+3+6+4+2+0+2+2+1+8+8
= 60 0 (mod 10)
The indicated credit card number is valid.
b. 6011 0123 9145 2317
Sum = 53 3 (mod 10)
Not Valid
Exercise
Determine whether
5234 8213 3410 1298
is a valid credit card number.
References
■Mathematical Excursions, Third Edition Richard
N. Aufmann, Joanne S. Lockwood, Richard D.
Nation, Daniel K. Clegg
■Mathematics in the Modern World, 2nd Edition,
Richard Earnhart, Edgar Adina