GE 4 MMW Week 8 9 (Revised)

UNIVERSITY OF MINDANAO
College of Arts and Sciences Education

General Education - Mathematics
Physically Distanced but Academically Engaged
Self-Instructional Manual (SIM) for Self-Directed Learning (SDL)
Course/Subject: GE 4 – Mathematics in the Modern World

(Week 8 – 9)
Name of Teacher: ___________________
SIM Prepared by: Prof. Ronnie O. Alejan
THIS SIM/SDL MANUAL IS A DRAFT VERSION ONLY.

THIS IS INTENDED ONLY FOR THE USE OF THE
STUDENTS WHO ARE OFFICIALLY ENROLLED
IN THE COURSE/SUBJECT.
THIS IS NOT FOR REPRODUCTION, COMMERCIAL, AND

DISTRIBUTION OUTSIDE OF ITS INTENDED USE.
EXPECT REVISIONS OF THE MANUAL.
2nd Floor, DPT Building, Matina Campus, Davao City
Phone No.: (082)300-5456/305-0647 Local 134
Week 8-9: Unit Learning Outcomes (ULO):

At the end of the unit, you are expected to
a. Perform arithmetic operations using modular arithmetic rules;
b. Solve application problems involving modular arithmetic; and
c. Solve problems relating to cryptography.
Big Picture in Focus

ULO-a. Perform arithmetic operations using modular arithmetic rules.
Metalanguage
In this section, the essential terms relevant to the study of modular arithmetic
and to demonstrate ULO-a will be operationally defined to establish a common frame
of reference as to how the texts work. You will encounter these terms as we go through
the study of modular arithmetic. Please refer to these definitions in case you will
encounter difficulty in understanding some concepts.
1. 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. Modular arithmetic is often tied to prime numbers and generally
appears in fields like cryptography, computer science, and computer algebra.
2. Modulus is the diminutive from the Latin word modus meaning measure or
manner or its plural moduli. In mathematics, it has to do with modular
arithmetic, also called clock arithmetic. The word modulus may sounds like
something that is a bit intimidating and complicated. However, believe it or not
you actually deal with this concept on a daily basis! Every time you tell the time,
you are actually dealing with the modulus 12.
3. Leap Year is a year containing an extra day. It has 366 days instead of the
normal 365 days. The extra day is added in February, which has 29 days
instead of the normal 28 days. Leap years occur every 4 years.
4. Linear Congruence is the problem of finding an integer x satisfying

ax ≡ b (mod m) for specified integers a, b, and m.
2
Phone No.: (082)300-5456/305-0647 Local 134
Essential Knowledge
To perform the aforesaid big picture (unit learning outcomes) for the eight and
ninth weeks of the course, you need to fully understand the following essential
knowledge that will be laid down in the succeeding pages. Please note that you are not
limited to refer to these resources exclusively. Thus, you are expected to utilize other
books, research articles, and other resources that are available in the university’s library
e.g., ebrary, search.proquest.com, etc.
1. Introduction to Modular Arithmetic

In determining time using the clock, we consider the use of a normal
(regular) time, 12-hour format and a military time, 24-hour format.
Regular Clock Military Clock

Most of the clocks have the familiar 12-hour design. We designate
whether the time is before noon or afternoon by using the abbreviations a.m.
and p.m. These abbreviations are both from Latin words, “ante meridiem” and
“post meridiem”, meaning “before midday” and “after midday”, respectively.
For example, when we say 9:00 a.m. means 9 hours after 12:00
midnight; while 9:00 p.m. means 9 hours after 12:00 noon. In both cases, once
12 is reached in the clock, we begin again with 1.
To determine a time in the future or in the past, we need to
consider whether we have passed 12 o’clock. For instance, to
determine the time 7 hours after 4 o’clock, we add 4 and 7. The
time is 11 o’clock because we did not pass 12 o’clock.
On the other hand, to determine the time 7 hours after 8 o’clock, we need
to consider that once we have passed 12 o’clock, we begin again with 1.
Therefore, 7 hours after 8 o’clock is 3 o’clock. The symbol ⊕ is used to
denote addition in a 12-hour clock. Using this notation, 4 ⊕ 7 = 11 and
8 ⊕ 7 = 3 on a 12-hour clock.
We can also use subtraction on a 12-hour clock. For instance, if the time
now is 8 o’clock, then 6 hours ago the time was 2
o’clock, which is the difference between 8 and 6 (8 – 6
= 2). If the time now is 4 o’clock, noticed that 7 hours
ago it was 9 o’clock. Using the symbol ⊝ to denote
subtraction on a 12-hour clock, we can write 8 ⊝6=2
and 4 ⊝ 7 = 9.
3
Phone No.: (082)300-5456/305-0647 Local 134
Example. Evaluate each of the following using a 12-hour clock.
a. 6 ⊕ 10 b. 5 ⊕ 9 c. 7 ⊝ 11 d. 5 ⊝ 10
Solution: Using a 12-hour clock, we have
a. 6 ⊕ 10 = 4 b. 5 ⊕ 9 = 2 c. 8 ⊝ 11 = 3 d. 2 ⊝ 8 = 6
Day-Of-The-Week Arithmetic
In solving day-of-the-week arithmetic is similar to clock arithmetic. In
this case, we assign each day of the week with a number such as
Monday - 1 Friday - 5
Tuesday - 2 Saturday - 6
Wednesday - 3 Sunday - 7
Thursday - 4
Example:
Six days after Thursday is Wednesday and 12 days after Sunday is Friday. In
symbol, we write
4⊞6=3 and 7 ⊞ 12 = 5
Note: The use of the ⊞ symbol for days-of-the-week arithmetic to differentiate from
the ⊕ symbol for clock arithmetic.
Another way to determine the day of the week is to note that when the
sum 4 + 6 = 10 is divided by 7, the number of days in a week, the remainder is
3, the number associated with Wednesday. When 7 + 12 = 19 is divided by 7,
the remainder is 5, the number associated with Friday. This works because the
days of the week repeat every 7 days.
The repeating of cycles can be represented mathematically by using
modular arithmetic, or arithmetic modulo n.
2. Modulo n
Two integers a and b are said to be congruent modulo n, where n is a
a−b
natural number, if is an integer. In this case, we write a ≡ b mod n. The
n
number n is called the modulus. The statement a ≡ b mod n is called a
congruence.
Example: Determine whether each of the following congruences is true.
a. 33 ≡ 8 mod 5
b. 26 ≡ 4 mod 7
c. 12 ≡ -3 mod 15
Solution:
33 − 8 25
a. By definition, = = 5 . Since 5 is an integer, thus, 33 ≡ 8 mod 5 is
5 5
a true congruence.
4
Phone No.: (082)300-5456/305-0647 Local 134
26 − 4 22
b. By definition, = . Since 22/7 is not an integer, thus, 26 ≡ 4 mod
7 7
7 is NOT a true congruence
12 − ( −3) 15
c. By definition, = = 1 . Since 1 is an integer, thus, 12 ≡ -3 mod
15 15
15 is a true congruence.
The Leap Year

Our ordinary year has 365 days. However, there are years in which one
extra day is added to the calendar that makes 366 days. This year is called
a leap year. Note that the extra day is added to the month of February. How
can we determine if the given year is a leap year or not? To answer this
question, here is the table for our guide.
A year will be a leap year if it is divisible by 4 but not by 100. If a year is divisible
by 4 and by 100, it is not a leap year unless it is also divisible by 400.
Divisible by 4 Divisible by 100 Divisible by 400
Leap Year ✓ x x
Not a Leap Year ✓ ✓ x
Leap Year ✓ ✓ ✓
Example 1: The years such as 1992 and 2016 are divisible by 4, but not by 100. Thus,
they are leap years.
Example 2: The years such as 1800 and 2100 are called century years. Since they
are evenly divisible by both 4 and 100, but not by 400, therefore, they are
not considered as leap years. (Note that the “400 rule” is important for
century years.)
Example 3: The years such as 2000 and 2400 are also century years. However, they
are evenly divisible by both 100 and 400, thus, they are leap years.
Leap Year Formula Based on Modular Arithmetic

Rule:
Let y be the year. If y ≡ 0 (mod 4), then y is a leap year unless
y ≡ 0 (mod 100). In that case, y is not a leap year unless y ≡
0 (mod 400). Then y is a leap year.
Example 1: The year 2012 is a leap year because 2012 ≡ 0 (mod 4) while the year
2018 is not a leap year because 2018 ≢ 0 (mod 4).
Example 2: The year 2200 is not a leap year because 2200 ≡ 0 (mod 100), but 2200
≢ 0 (mod 400).
Example 3: The year 2800 is a leap year because 2800 ≡ 0 (mod 100) and 2800 ≡ 0
(mod 400).
Computing the Day of the Week

A function that is related to the modulo function is called the Greatest
Integer Function. It is the greatest integer less than or equal to the real number
5
Phone No.: (082)300-5456/305-0647 Local 134
x. This function is also known as floor function. The greatest integer of any
real number x is represented by symbol  x  or x . Here are some examples.
19   28  3  3 5 
 36  = 6 ;
 4 =4 ;  4 =7 ; 5  = 0 ; π  = 3 ;    =3
       2 
Remember that in the modulo function, we determine the remainder

when one number is divided by another number. On the other hand, in the floor
function, we determine the quotient (ignoring the remainder) when one number
is divided by another number.
Using the floor function, Christian Zeller devised a formula to help us

determine the day of the week for any date on the Gregorian calendar. The
formula is known as Zeller’s congruence. It is given by
 13m − 1  y   c  
x ≡   +   +   + d + y − 2c  mod7
 5  4 4 
where m is the month using 1 for March, 2 for April, ... , 10 for December; January
and February are assigned the values 11 and 12, respectively
d is the day of the month
c 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, y is the last two digits of the year
minus 1
x is the day of the week (Sunday = 0, Monday = 1, Tuesday = 2, ... ,
Saturday = 6)
Example 1. Robert was born in April 29, 1980. What day of the week he was born?
Solution:
Using the formula for April 29, 1980, we have m = 2, d = 29, c = 19, and y
= 80. Let’s use these values to solve for x.
  13(2) − 1  80  19  
x ≡   +   +   + 29 + 80 − 2(19)  mod7
 5  4 4 
≡ ( 5 + 20 + 4 + 29 + 80 − 38 ) mod7
x ≡ 100mod7
Solving the congruence x ≡ 100 mod 7 for x, we get x = 2. Since 2 corresponds

to the second day of the week, therefore, Robert was born on Tuesday, April
29, 1980.
Example 2. The “Independence Day” of the Republic of the Philippines was

declared on June 12, 1898. What day of the week it was declared?
Solution:
Identifying first the required values, we have m = 4, d = 12, c = 18, and y = 98.
Using these values in the formula, we have
6
Phone No.: (082)300-5456/305-0647 Local 134
  13(4) − 1  98  18  
x ≡   +   +   + 12 + 98 − 2(18)  mod7
 5  4 4 
≡ (10 + 24 + 4 + 12 + 98 − 36 ) mod7
x ≡ 112mod7
Now, solving x ≡ 100 mod 7 for x, we get x = 0. Thus, the “independence day”
was declared on Sunday, June 12, 1898.
3. Arithmetic Operations Modulo n

To solve arithmetic operations, perform its operation and then divide by
the modulus, n. Note that the remainder is the answer. Thus, the result of an
arithmetic operation mod n is always a whole number less than n.
Example 1. Addition Modulo n
Evaluate each of the following:
a. (27 + 34) mod 8 b. (39 + 84) mod 7

Solutions:
a. Get the sum of 27 and 34 which is 61, then divide it by 8, the modulus. The
remainder is the answer, that is 5. In symbol, 61 mod 8 = 5.
b. Similarly, the sum of 39 and 84 is 123. Dividing this by the modulus, 7, we

get a remainder of 4. In symbol, 123 mod 7 = 4.
Example 2. Subtraction Modulo n
Evaluate each of the following.
a. (43 – 18) mod 7 b. (27 – 36) mod 6
Solutions:
a. Subtract 43 – 18 = 25. The result is positive. Divide the difference by the
modulus, 7. The answer is the remainder, that is 4.
b. Subtract 27 – 36 = – 9. Since, the result is negative, we must find the value

−9 − x −(9 + x )
of x so that – 9 ≡ x mod 6. By definition, = must be an
6 6
integer. To find the value of x, try to substitute the whole number values of
x less than 6, the modulus. In this case, we find that when x = 3,
−(9 + 3) −12
= = −1 . Note that – 1 is an integer.
6 12
Example 3. Calculating Times
Disregarding a.m. or p.m., if it is 8 o’clock now, what time was it 55 hours

ago?
Solution:
The time can be determined by calculating (8 – 55) mod 12.
7
Phone No.: (082)300-5456/305-0647 Local 134
Since 8 – 55 = – 47 is a negative number, find a whole number x less than

−47 − x −( 47 + x )
the modulus 12, so that – 47 ≡ x (mod 12). By definition, =
12 12
must be an integer. Evaluating the expression for whole number values of x
−( 47 + 1) −48
less than 12, we have, when x = 1, = = −4 , an integer.
12 12
Thus, (8 – 55) mod 12 ≡ 1. Therefore, if it is 8 o’clock now, 55 hours ago, it was
1 o’clock.
Example 4. If today is Tuesday, what day of the week will it be 93 days from now?
Solution:
Tuesday corresponds to 2, so the day of the week 93 days from now is
represented by (2 + 93) mod 7. Solving this addition modulo 7, we have 95
mod 7 ≡ 4, which corresponds to Thursday.
Example 5. Multiplication Modulo n
Evaluate each of the following:
a. (18 • 27) mod 10 b. (21 • 32) mod 13

Solutions:
a. Find the product of 18 and 27 which is 486, and then divide by the modulus,
10. The remainder is the answer, that is 6.
b. Find the product of 21 and 32 which is 672, and then divide by the modulus,
13. The remainder is the answer, that is 9.
4. Solving Congruence Equations

Solving a congruence equation means finding all whole number values
of the variable for which the congruence is true.
For instance, 3x + 4 ≡ 5 (mod 8), what values of x in such a way that the
congruence makes true? To solve the equation, we will get an initial solution(s)
which is(are) coming from the set of whole numbers x less than the modulus n.
Substituting the x values in the congruence equation, we have
Let x=0 3 (0) + 4 ≢ 5 (mod 8)

x=1 3 (1) + 4 ≢ 5 (mod 8)
x=2 3 (2) + 4 ≢ 5 (mod 8)
x=3 3 (3) + 4 ≡ 5 (mod 8)  x = 3 is a solution
x=4 3 (4) + 4 ≢ 5 (mod 8)
x=5 3 (5) + 4 ≢ 5 (mod 8)
x=6 3 (6) + 4 ≢ 5 (mod 8)
x=7 3 (7) + 4 ≢ 5 (mod 8)
It shows that one of the solutions is 3.
In general, once an initial solution is determined, additional solutions can

be found by repeatedly adding the modulus to the original (initial) solution.
8
Phone No.: (082)300-5456/305-0647 Local 134
Thus, the solutions of 3x + 4 ≡ 5 (mod 8) are 3, 11, 19, 27, 35, 43, 51, and so
on. There are infinite solutions to this equation.
A congruence equation can have more than one solution among the
whole numbers less than the modulus n. The next example illustrates that you
must check all whole numbers less than the modulus.
Example 1. Solve the congruence equation, 4x + 7 ≡ 3 (mod 10).

Solution:
Beginning with 0, substitute each whole number less than 10 into the
congruence equation.
Let x=0 4 (0) + 7 ≢ 3 (mod 10)

x=1 4 (1) + 7 ≢ 3 (mod 10)
x=2 4 (2) + 7 ≢ 3 (mod 10)
x=3 4 (3) + 7 ≢ 3 (mod 10)
x=5 4 (5) + 7 ≢ 3 (mod 10)
x=6 4 (6) + 7 ≢ 3 (mod 10)
x=7 4 (7) + 7 ≢ 3 (mod 10)
x=8 4 (8) + 7 ≢ 3 (mod 10)
The initial solutions between 0 and 9 are 4 and 9. From these values, we can
determine the remaining solutions by repeatedly adding the modulus, 10, to
these solutions. Thus, the solutions are 4, 9, 14, 19, 24, 29, 34, 39, 44, 40, and
so on.
Example 2: Not all congruence equations have a solution. For instance, 3x + 2 ≡ 4

(mod 6) has no solution, as shown below.
Let x=0 3 (0) + 2 ≢ 4 (mod 6)

x=1 3 (1) + 2 ≢ 4 (mod 6)
x=2 3 (2) + 2 ≢ 4 (mod 6)
x=3 3 (3) + 2 ≢ 4 (mod 6)
x=4 3 (4) + 2 ≢ 4 (mod 6)
x=5 3 (5) + 2 ≢ 4 (mod 6)
There is no solution to the congruence equation because no whole number

value of x less than the modulus 6 is a solution.
5. Additive Inverses in Modular Arithmetic

If the sum of two real numbers is 0, then the numbers are additive
inverses of each other. For example, 12 + (-12) = 0, that is the sum of twelve
and its opposite is zero (0). This means that 12 is the additive inverse of -12,
and -12 is the additive inverse of 12.
This concept applies in modular arithmetic. For example, (5 + 7) ≡ 0 mod
12, thus, in mod 12 arithmetic, 5 is the additive inverse of 7, and 7 is the additive
inverse of 5. Here we consider only those whole numbers less than the
modulus. In our example, 5 + 7 = 12, that is the sum of a number and its additive
9
Phone No.: (082)300-5456/305-0647 Local 134
inverse equals the modulus. Considering this concept, we can easily find the
additive inverse of a number for any modulus.
Example 1. Find the additive inverse of 7 in mod 15 arithmetic.
Solution:
In mod 15 arithmetic, 7 + 8 = 15, so the additive inverse of 7 is 8.
Example 2. Find the additive inverse of 11 in mod 17 arithmetic.
Solution:
In mod 17 arithmetic, 11 + 6 = 17, so the additive inverse of 11 is 6.
6. Multiplicative Inverses in Modular Arithmetic

If the product of two real numbers is 1, then the numbers are
1
multiplicative inverses of each other. For example, 5 i = 1 , that is the
5
product of five and its reciprocal is one (1). Thus, 5 is the multiplicative inverse
1 1
of , and is the multiplicative inverse of 5.
5 5
In modular arithmetic, this concept is also applicable. For example, in
mod 9 arithmetic, 4 is the multiplicative inverse of 7, and 7 is the multiplicative
inverse of 4 because 4 • 7 ≡ 1 mod 9. Here we will focus ourselves only with
natural numbers less than the modulus. To find the multiplicative inverse of a
mod m, solve the modular equation ax ≡ 1 mod m for x.
Example 1. Find the multiplicative inverse of 5 in mod 7 arithmetic.
Solution:
To find the multiplicative inverse of 5, solve the equation 5x ≡ 1 mod 7 by trying
different natural number values of x less than 7, the modulus.
In the equation, 5x ≡ 1 mod 7,
Let x=1 5(1) ≢ 1 mod 7 , x=4 5(4) ≢ 1 mod 7,

x=2 5(2) ≢ 1 mod 7 , x=5 5(5) ≢ 1 mod 7,
x=3 5(3) ≡ 1 mod 7 , x=6 5(6) ≢ 1 mod 7
Since x = 3 satisfies the congruence 5x ≡ 1 mod 7, thus, the multiplicative

inverse of 5 in mod 7 arithmetic is 3.
Example 2. Find the multiplicative inverse of 7 in mod 11 arithmetic.
Solution:
Solve the equation 7x ≡ 1 mod 11 by letting natural number values of x less
than the modulus, 11.
In the equation, 7x ≡ 1 mod 11,
Let x=1 7(1) ≢ 1 mod 11, x=6 7(6) ≢ 1 mod 11,
10
Phone No.: (082)300-5456/305-0647 Local 134
x=2 7(2) ≢ 1 mod 11, x=7 7(7) ≢ 1 mod 11,

x=3 7(3) ≢ 1 mod 11, x=8 7(8) ≡ 1 mod 11,
x=4 7(4) ≢ 1 mod 11, x=9 7(9) ≢ 1 mod 11,
x=5 7(5) ≢ 1 mod 11, x = 10 7(10) ≢ 1 mod 11
Since x = 8 satisfies the congruence 7x ≡ 1 mod 11, thus, the multiplicative

inverse of 7 in mod 11 arithmetic is 8.
You can refer to the source below to help

you further understand the lesson:
Ondaro et al. (2018). Mathematics in the modern world, e-book. Mutya Publishing
House, Inc.
Chapter 3 Lesson 7 - Mathematical Systems

http://124.105.95.237/index.php/s/XY6BGsTi3NfWQnC
Chapter 3 Lesson 7.1

http://124.105.95.237/index.php/s/sLTgYFzK79mGr5i
11
Phone No.: (082)300-5456/305-0647 Local 134
Activity 1. Now that you know the most essential concepts in the study of
mathematical system, let us try to check your understanding of these
concepts. You are directed to answer nos. 1 to 4 of exercises from
MMW Practice Set 9 – A

on pages 89.
Activity 1. Getting acquainted with the essential concepts in the study of

geometry, what also matters is you should also be able to apply
these concepts. You are directed to do nos. 5 to 10 of exercises
from
MMW Practice Set 9 – A

on page 90.
12
Phone No.: (082)300-5456/305-0647 Local 134
Activity 1. Based from the most essential concepts in the study mathematical
system and the learning exercises that you have done, please feel
free to write your arguments or lessons learned below.
1.
2.
3.
13
Phone No.: (082)300-5456/305-0647 Local 134
Do you have any question for clarification?
Questions / Issues Answers
1.
2.
3.
4.
5.
Modulo n Congruence Modular arithmetic

Leap year modular Day of the week
Additive inverse
arithmetic arithmetic
Multiplicative
Congruence equation Addition modulo
inverse
14
Phone No.: (082)300-5456/305-0647 Local 134

ULO-b. Solve application problems involving modular arithmetic.
Metalanguage
In this section, the essential terms relevant to the study of modular arithmetic
and to demonstrate ULO-b will be operationally defined to establish a common frame
of reference as to how the texts work. You will encounter these terms as we go through
this topic. Please refer to these definitions in case you will encounter difficulty in
understanding some concepts.
1. International Standard Book Number (ISBN) is a numeric

commercial book identifier which is intended to be unique. Publishers purchase
ISBNs from an affiliate of the International ISBN Agency. An ISBN is assigned
to each separate edition and variation (except reprintings) of a publication. For
example, an e-book, a paperback and a hardcover edition of the same book
will each have a different ISBN. The ISBN is ten digits long if assigned before
2007, and thirteen digits long if assigned on or after 1 January 2007 (though in
practice a book may have both, as it is possible to convert between them). The
method of assigning an ISBN is nation-specific and varies between countries,
often depending on how large the publishing industry is within a country.
2. Check Digit is a form of redundancy check used for error detection on

identification numbers, such as bank account numbers, which are used in an
application where they will at least sometimes be input manually. It is
analogous to a binary parity bit used to check for errors in computer-generated
data. It consists of one or more digits computed by an algorithm from the other
digits (or letters) in the sequence input.
3. Universal Product Code (UPC) is a type of code printed on retail product

packaging to aid in identifying a particular item. It consists of two parts – the
machine-readable barcode, which is a series of unique black bars, and the
unique 12-digit number beneath it. The purpose of UPCs is to make it easy to
identify product features, such as the brand name, item, size, and color, when
an item is scanned at checkout.
4. Luhn algorithm is an algorithm used to validate a credit card number or other

identifying numbers, such as Social Security numbers. The Luhn algorithm,
also called the Luhn formula or modulus 10, checks the sum of the digits in the
card number and indicates whether the sums equal what is expected or if there
is an error in the number sequence.
15
Phone No.: (082)300-5456/305-0647 Local 134
Essential Knowledge
knowledge that will be laid down in the succeeding pages. Please note that you are
not limited to refer to these resources exclusively. Thus, you are expected to utilize
other books, research articles, and other resources that are available in the
university’s library e.g., ebrary, search.proquest.com, etc.
Applications of Modular Arithmetic

Modular arithmetic is used extensively in pure mathematics, where it is
a cornerstone of number theory. But it also has many practical applications. It
is used to calculate checksums for international standard book numbers
(ISBNs), universal product code (UPCs), and credit card numbers and to spot
errors in them.
1. International Standard Book Number (ISBN)

Every book that catalogs at the Library of Congress must have an
International Standard Book Number (ISBN). This is a 13-digit number and was
developed to help ensure that orders for books are filled accurately and that
books are catalogued correctly.
https://www.wikidata.org/wiki/Q33057
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 (the 13th one) is
called a check digit.
1.1 Formula for the ISBN-13 Check Digit

The 13 digits of an ISBN are labelled from left to right as d1, d2, d3 , . . . ,
d12 and x as the last digit (13th). The check digit x, that is the 13th digit can be
verified using the congruence formula below.
Formula:
x ≡ 10 – (d1 + 3d2 + d3 + 3d4 + d5 + 3d6 + d7 + 3d8 + d9 + 3d10 + d11 + 3d12) mod 10
If x = 10, then the check digit is 0.
Note that the check digit is used to ensure accuracy. For example, the
ISBN for the sixth edition of the Elementary Geometry for College Students
16
Phone No.: (082)300-5456/305-0647 Local 134
by Alexander, D. and Koeberlien G. is 978-1-285-19569-8. Suppose, a

bookstore clerk sends an order for that book, and inadvertently enters the
number as 978-1-285-91569-8, where she transposed the digits 1 and 9 in the
five numbers that identify the book. The receiving clerk verifies the check digit
as follows.
x ≡ 10 – [9 + 3(7) + 8 + 3(1) + 2 + 3(8) + 5 + 3(9) + 1 + 3(5) + 6 + 3(9)] mod 10

≡ 10 – 148 mod 10
= 10 – 8
x = 2
Since the computed check digit, x = 2 does not conform to 8 as it should

be, the receiving clerk knows that an incorrect ISBN has been sent. This type
of error is the most frequent errors called transposition errors. The ISBN
coding system will catch most of them.
Example 1. Determine the ISBN check digit for the book How Mathematicians Think
by Byers, William (2007). The first 12 digits of the ISBN are 978-0-691-12738-
x.
Solution:
Using the formula, we have
x ≡ 10 – [9 + 3(7) + 8 + 3(0) + 6 + 3(9) + 1 + 3(1) + 2 + 3(7) + 3 + 3(8)] mod 10

≡ 10 – 125 mod 10
= 10 – 5
x = 5, thus, the check digit is 5.
Example 2. A purchase order for the book The Mathematical Tourist by Ivars Peterson
with the ISBN 978-0-760-73261-6. Verify if the ISBN is valid.
Solution:
Using the formula, we have
x ≡ 10 – [9 + 3(7) + 8 + 3(0) + 7 + 3(6) + 0 + 3(7) + 3 + 3(2) + 6 + 3(1)] mod 10

≡ 10 – 102 mod 10
= 10 – 2
x = 8
It shows that the correct check digit is 8 not 6, therefore, the ISBN is not valid.
1.2 Formula for the ISBN-10 Check Digit

There are books with ISBN-13 and ISBN-10. The check digit for ISBN-
10 can be verified using the congruence formula below.
Formula:
x ≡ 11 – [(10d1 + 9d2 + 8d3 + 7d4 + 6d5 + 5d6 + 4d7 + 3d8 + 2d9) mod 11]
Example. The ISBN-10 for the “Math World” is 0-8493-9640-9. Verify if the ISBN is
valid.
17
Phone No.: (082)300-5456/305-0647 Local 134
Solution:
Using the above formula, we have
x ≡ 11 – [10(0) + 9(8) + 8(4) + 7(9) + 6(3) + 5(9) + 4(6) + 3(4) + 2(0) mod 11]
≡ 11 – [266 mod 11]
= 11 – 2
x = 9
Since we have x = 9 and it conforms with last digit (check digit) of the ISBN,
thus, it is valid.
2. Universal Product Code (UPC)

The groceries and department stores in the different malls use a coding
scheme in their products called the Universal Product Code (UPC). This is
also closely related to the ISBN. A cashier or checkout clerk passes the product
by a scanner, which reads the number from a bar code and records the price
on the cash register. The price of the item is updated in the computer if there
are changes for a promotional sale (discounts and clearance sale). This is to
save time because there is no need to reprice each item. Aside from pricing
items, the UPC gives the store manager or owner accurate information about
inventory and the buying habits of the customers. From there, the manager
could make better decisions in running the business.
http://www.hellmanproduction.com/cd/dvd-replication/what-is-upc-barcode.html
The UPC is a 12-digit number that satisfies a congruence equation. The

last digit is the check digit. The 12 digits of the UPC are labelled from left to
right as d1, d2, ... , d11, and x as the last digit (12th). We can verify the UPC
check digit x, the last digit using the congruence formula below.
Formula for the UPC Check Digit
x ≡ 10 – [(3d1 + d2 + 3d3 + d4 + 3d5 + d6 + 3d7 + d8 + 3d9 + d10 + 3d11) mod 10]
If x = 10, then the check digit is 0.
Example 1. The first 11 digits of the UPC of the film “Alice in Wonderland” are 7-
86936-79798-x. Find its check digit.
Solution:
Using the above formula, we have
x ≡ 10 – [3(7) + 8 + 3(6) + 9 + 3(3) + 6 + 3(7) + 9 + 3(7) + 9 + 3(8)] mod

10
≡ 10 – 155 mod 10
= 10 – 5
x = 5
18
Phone No.: (082)300-5456/305-0647 Local 134
The check digit of the UPC of the film is 5.
Example 2. Is 1-32342-65933-9 a valid UPC?
Solution:
Using the formula above, we have
x ≡ 10 – [3(1) + 3 + 3(2) + 3 + 3(4) + 2 + 3(6) + 5 + 3(9) + 3 + 3(3)] mod

10
≡ 10 – 91 mod 10
= 10 – 1
x = 9
Since we have x = 9 as the check digit, thus, the UPC is valid.
The common errors in the ISBN and UPC coding systems are
transposition errors. This happens if any other two digits were transposed
(exchanged positions).
Suppose the UPC of the product is 0-51500-24275-9. However, that the

product code is written as 0-51500-24725-9, where the digits 7 and 2 have been
transposed. By calculating the check digit, we have
x ≡ 10 – [3(0) + 5 + 3(1) + 5 + 3(0) + 0 + 3(2) + 4 + 3(7) + 2 + 3(5)] mod 10

≡ 10 – 61 mod 10
= 10 – 1
x = 9
Notice that the check digit is the same, in fact, the UPC has been entered
incorrectly. This was an unfortunate coincidence; if any other two digits were
transposed, the result would have given a different check digit, and the error
would have been detected. It can be shown that the ISBN and UPC coding
methods will not catch a transposition error of adjacent digits a and b if a − b = 5
, that is, the absolute value of the difference between the digits a and b is 5. In
our example, 7 − 2 = 5 .
3. Credit Card Numbers

Many financial institutions, issuing credit cards, which allow the holders
to borrow funds. Normally, credit card numbers are 13 to 16 digits long,
depending on the card issuer. The first one to four digits are used to identify the
card issuer. The last digit is the check digit.
https://www.freewebmentor.com/2017/04/detect-credit-card-type-based-card-number.html
19
Phone No.: (082)300-5456/305-0647 Local 134
How sure are we, that the credit cards are valid? Note that verification
is very important, especially in e-commerce, where credit card information is
frequently sent over the Internet. To determine if the credit cards are valid, the
companies use the modular arithmetic. The primary coding method is based on
the Luhn algorithm, which uses mod 10 arithmetic.
The Luhn Algorithm

The Luhn algorithm is calculated as follows:
1. Beginning with the second-to-last digit and reading from right to left, double
every other digit.
2. If ever a digit becomes a two-digit number after being doubled, treat that
number as two single digits.
3. Find the sum of the new list of digits. If the final sum is equal to 0 mod 10,
then the credit card is valid.
Example 1. Recently, Dexter received his credit card with a number, 5234-
8213-3410-1496. Verify if his credit card is valid.
Solution:
Step 1. Beginning with the second-to-last digit, and reading from right to left,
highlight every other digit,
5 2 3 4 8 2 1 3 3 4 1 0 1 4 9 6
Step 2. Next, double each of the highlighted digits.
10 2 6 4 16 2 2 3 6 4 2 0 2 4 18 6
Step 3. Finally, add all digits, treating two-digit numbers as two single digits.
(1+0) + 2 + 6 + 4 + (1+6) + 2 + 2 + 3 + 6 + 4 + 2 + 0 + 2 + 4 + (1+8) + 6
= 60, Since 60 ≡ 0 mod 10, therefore, Dexter’s credit card number has
been valid.
Example 2: Is 6011-0123- 9541- 2713 a valid credit card?
Solution:
Step 1. Beginning with the second-to-last digit, and reading from right to left,
highlight every other digit,
6 0 1 1 0 1 2 3 9 5 4 1 2 7 1 3
Step 2. Next, double each of the highlighted digits.
12 0 2 1 0 1 4 3 18 5 8 1 4 7 2 3
Step 3. Finally, add all digits, treating two-digit numbers as two single digits.
(1+2) + 0 + 2 + 1 + 0 + 1 + 4 + 3 + (1+8) + 5 + 8 + 1 + 4 + 7 + 2 + 3
= 53
Since 53 ≢ 0 mod 10, thus, the credit card is not valid.
20
Phone No.: (082)300-5456/305-0647 Local 134

House, Inc.


21
Phone No.: (082)300-5456/305-0647 Local 134
Activity 1. Now that you know the most essential concepts of the application of
modular arithmetic, let us try to check your understanding of these
concepts. You are directed to answer nos. 1 to 5 of exercises from
MMW Practice Set 9 – B

on pages 91.
Activity 1. Getting acquainted with the essential concepts of the application of

modular arithmetic, what also matters is you should also be able to
apply these concepts. You are directed to do nos. 6 to 10 of
exercises from
MMW Practice Set 9 – B

on page 92.
22
Phone No.: (082)300-5456/305-0647 Local 134
Activity 1. Based from the most essential concepts of the application of modular
arithmetic and the learning exercises that you have done, please feel
1.
2.
3.
23
Phone No.: (082)300-5456/305-0647 Local 134
1.
2.
3.
4.
5.
Universal Product
ISBN-10 The Luhn Algorithm
Code (UPC)
ISBN-13 Credit card number UPC Check digit
ISBN-10 check digit Valid card number ISBN-13 check digit
24
Phone No.: (082)300-5456/305-0647 Local 134

ULO-c. Solve problems relating to cryptography.
Metalanguage
In this section, the essential terms relevant to the study of cryptography and to
demonstrate ULO-c will be operationally defined to establish a common frame of
reference as to how the texts work. You will encounter these terms as we go through
this topic. Please refer to these definitions in case you will encounter difficulty in
understanding some concepts.
1. Cryptography is a method of protecting information and communications

through the use of codes, so that only those for whom the information is
intended can read and process it. The prefix "crypt-" means "hidden" or "vault"
and the suffix "-graphy" stands for "writing."
2. Ciphertext is the result of encryption performed on plaintext using an

algorithm, called a cipher. Ciphertext is also known as encrypted or encoded
information because it contains a form of the original plaintext that is
unreadable by a human or computer without the proper cipher to decrypt it.
3. Plaintext usually means unencrypted information pending input into

cryptographic algorithms, usually encryption algorithms. Cleartext usually
refers to data that is transmitted or stored unencrypted.
4. Encryption is the process of converting data to an unrecognizable or

"encrypted" form. It is commonly used to protect sensitive information so that
only authorized parties can view it. This includes files and storage devices, as
well as data transferred over wireless networks and the Internet.
5. Decryption is the process of transforming data that has been rendered

unreadable through encryption back to its unencrypted form. In decryption, the
system extracts and converts the garbled data and transforms it to texts and
images that are easily understandable not only by the reader but also by the
system. Decryption may be accomplished manually or automatically. It may
also be performed with a set of keys or passwords.
6. Cyclic Code is a block code, where the circular shifts of each codeword gives
another word that belongs to the code. They are error-correcting codes that
have algebraic properties that are convenient for efficient error detection and
correction.
25
Phone No.: (082)300-5456/305-0647 Local 134
Essential Knowledge
knowledge that will be laid down in the succeeding pages. Please note that you are
not limited to refer to these resources exclusively. Thus, you are expected to utilize
other books, research articles, and other resources that are available in the
university’s library e.g., ebrary, search.proquest.com, etc.
1. Cryptography
Related to codes on books and grocery items are secret codes. These
secret codes are used to send messages between people, companies, nations,
and other parties. It is hoped that by devising a code that is difficult to break,
the sender can prevent the communication from being read if it is intercepted
by an unauthorized person.
Cryptology is the study of making and breaking secret codes. The word
cryptography comes from the two Greek words, “krypto” meaning secret and
“graphein” meaning write. So cryptography means secret writing.
Basic Terminologies:
The Plaintext is a message before it is coded.

Example:
Message in plaintext: MATHEMATICS IN THE MODERN WORLD
The Ciphertext is the message after it has been written in code.

Example:
Message in ciphertext: YMFTQYMFUOE UZ FTQ YAPQDZ IADXP.
http://ehindistudy.com/2015/10/01/cryptography-in-hindi/
The Encryption is the method of changing from plaintext to ciphertext.

The example message above was encrypted by substituting each letter
in plaintext with the letter that is 12 letters after that letter in the English
alphabet. Note that, when the end of the alphabet is reached, start again from
the beginning. This is called a cyclical coding scheme because each letter of
the alphabet shifts in the same number of positions. Here is the example table
of the original alphabet and the substitute alphabet.
26
Phone No.: (082)300-5456/305-0647 Local 134
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕ ↨ ↕
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
The Decryption is the method of changing from the ciphertext message

to plaintext.
If a message has been encrypted using a cyclical substitution code like
the one shown above, the key to the code can be found by taking a word from
the message (usually one of the longer words) and continuing the alphabet for
each letter of the word. For instance, if we take the word YMFTQYMFUOE from
the ciphertext, then we have this table below.
Y M F T Q Y M F U O E
Z N G U R Z N G V P F
A O H V S A O H W Q G
B P I W T B P I X R H
C Q J X U C Q J Y S I
D R K Y V D R K Z T J
E S L Z W E S L A U K
14th positions
F T M A X F T M B V L
G U N B Y G U N C W M
H V O C Z H V O D X N
I W P D A I W P E Y O
J X Q E B J X Q F Z P
K Y R F C K Y R G A Q
L Z S G D L Z S H B R
M A T H E M A T I C S
N B U I F N B U J D T
The key to the code can be determined when a recognizable word

appears in the list. In the table above, notice that the word MATHEMATICS
appears. Now, starting with the letters in the first row, count the number of
positions that the letters have been shifted. In this case, the letters have been
shifted 14 positions.
To decode the message, replace the letter of the normal alphabet that
comes 14 positions after the letter in the ciphertext. For example, starting from
Y of the ciphertext, count 14 positions to the right. Wherever the 14th position
falls, the letter that corresponds to that is the letter of the plaintext.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
2 3 4 5 6 7 8 9 10 11 12 13 14 1
Continue counting for the rest of the letters, until the secret message is
revealed. Here is the message.
Encrypted Message: YMFTQYMFUOE UZ FTQ YAPQDZ IADXP
Decrypted Message: MATHEMATICS IN THE MODERN WORLD
27
Phone No.: (082)300-5456/305-0647 Local 134
2. Cyclical Coding Scheme Using Modular Arithmetic

Modular arithmetic can be used in the cyclical coding scheme. Beginning
with the normal alphabet, we assign each letter with a numerical equivalent as
shown below.
If the encrypting code is to shift each letter of the plaintext message m

positions, then the corresponding letter in the ciphertext message is given by
c ≡ (p + m) mod 26,
where p is the numerical equivalent of the plaintext letter, and

c is the numerical equivalent of the ciphertext letter.
Note that the letter Z is coded as 0 because 26 ≡ 0 mod 26.
Let’s take our previous example, MATHEMATICS IN THE MODERN

WORLD. Each letter in the message was shifted 12 positions (m = 12) to the
right. To code the plaintext letter M in the word MATHEMATICS, we use the
congruence c ≡ (p + m) mod 26.
Let p = 13 (M is the 13th letter in the normal alphabet.) and

m = 12 (The number of positions the letter is shifted.)
Then, c ≡ (p + m) mod 26
c ≡ (13 + 12) mod 26
c ≡ 25 mod 26
c = 25
Since the 25th letter is Y, thus, M is coded as Y. Similarly, for coding A,

T, and H, we have this process.
Plain Text Coding Process Coded Text

A c ≡ ( 1 + 12) mod 26 ≡ 13 mod 26 ≡ 13 M
T c ≡ (20 + 12) mod 26 ≡ 32 mod 26 ≡ 6 F
H c ≡ ( 8 + 12) mod 26 ≡ 20 mod 26 ≡ 20 T
Once plaintext has been converted to ciphertext, there must be a method

by which the person receiving the message can return the message into
plaintext. For the cyclical code, the congruence is p ≡ (c + n) mod 26, where p
and c are defined as before and n = 26 – m.
Let’s take the word IADXP in the ciphertext. To convert each letter of the
word to plaintext, determine first n = 26 – m. The letter I in the ciphertext is
decoded below using the congruence p ≡ (c + n) mod 26.
28
Phone No.: (082)300-5456/305-0647 Local 134
Let c = 9 (I is the 9th letter) and

n = 14 (n = 26 – 12 = 14)
Then, p ≡ (c + n) mod 26
p ≡ (9 + 14) mod 26
p ≡ (23) mod 26
p ≡ 23
Since the 23rd letter is W, thus, I is decoded as W. Similarly, for decoding

A, D, X, and P, we have this process.
Ciphertext Decoding Process Decoded Text

A p ≡ ( 1 + 14) mod 26 ≡ 15 mod 26 ≡ 15 O
D p ≡ ( 4 + 14) mod 26 ≡ 18 mod 26 ≡ 18 R
X p ≡ (24 + 14) mod 26 ≡ 38 mod 26 ≡ 12 L
P p ≡ (16 + 14) mod 26 ≡ 30 mod 26 ≡ 20 D
Example: Given each message below, use the cyclical alphabetic encrypting code
that shifts each letter 17 positions to
a. code SMILING IS THE KEY TO FRIENDSHIP.

b. decode NV TREEFK TYREXV REPKYZEX LEKZC NV RTTVGKK ZK.
Solution:
a. The encrypting congruence is c ≡ (p + 17) mod 26. Replace p by the
numerical equivalent of each letter of plaintext and determine c. The results
for SMILING are shown below.

S c ≡ (19 + 17) mod 26 ≡ 36 mod 26 ≡ 10 J
M c ≡ (13 + 17) mod 26 ≡ 30 mod 26 ≡ 4 D
I c ≡ ( 9 + 17) mod 26 ≡ 26 mod 26 ≡ 0 Z
L c ≡ (12 + 17) mod 26 ≡ 29 mod 26 ≡ 3 C
I c ≡ ( 9 + 17) mod 26 ≡ 26 mod 26 ≡ 0 Z
N c ≡ (14 + 17) mod 26 ≡ 31 mod 26 ≡ 5 E
G c ≡ ( 7 + 17) mod 26 ≡ 24 mod 26 ≡ 24 X
Continuing the process, the plaintext would be coded as
JDZCZEX ZJ KYV BVP KF WIZVEUJYZG
b. Since m = 17, thus, n = 26 – 17 = 9. The ciphertext is decoded by using the

congruence p ≡ (c + 9) mod 26. The results for the first two words, NV
TREEFK are shown below.
29
Phone No.: (082)300-5456/305-0647 Local 134

N c ≡ (14 + 9) mod 26 ≡ 23 mod 26 ≡ 23 W
V c ≡ (22 + 9) mod 26 ≡ 31 mod 26 ≡ 5 E
T c ≡ (20 + 9) mod 26 ≡ 29 mod 26 ≡ 3 C
R c ≡ (18 + 9) mod 26 ≡ 27 mod 26 ≡ 1 A
E c ≡ ( 5 + 9) mod 26 ≡ 14 mod 26 ≡ 14 N
E c ≡ ( 5 + 9) mod 26 ≡ 14 mod 26 ≡ 14 N
F c ≡ ( 6 + 9) mod 26 ≡ 15 mod 26 ≡ 15 O
K c ≡ (11 + 9) mod 26 ≡ 20 mod 26 ≡ 20 T
If we continue the process for the rest of the letters, the ciphertext would be
decoded as
WE CANNOT CHANGE ANYTHING UNTIL WE ACCEPT IT.

(By: Carl Gustav Jung)
3. Encoding a Message Using the Congruence c ≡ (ap + m) mod 26

A coding scheme that is a little more difficult to break is based on the
congruence c ≡ (ap + m) mod 26, where a and 26 do not have a common factor
or they are relatively prime, i.e. gcd(a, 26) = 1.
Example: Using the congruence c ≡ (3p + 1) mod 26, encode the message STUDY
HARD.
Solution:
The encrypting congruence is c ≡ (3p + 1) mod 26. Replace p by the numerical
equivalent of each letter using the table below and determine c.
The encryption of each letter in the word STUDY is presented below.

S c ≡ (3 • 19 + 1) mod 26 ≡ 58 mod 26 ≡ 6 F
T c ≡ (3 • 20 + 1) mod 26 ≡ 61 mod 26 ≡ 9 I
U c ≡ (3 • 21 + 1) mod 26 ≡ 64 mod 26 ≡ 12 L
D c ≡ (3 • 4 + 1) mod 26 ≡ 13 mod 26 ≡ 13 M
Y c ≡ (3 • 25 + 1) mod 26 ≡ 76 mod 26 ≡ 24 X
Continuing the process, the plaintext is coded in ciphertext as FILMX YDCM.
Decoding a Message Using the Congruence c ≡ (ap + m) mod 26

Decoding a message that was encrypted using the congruence
equation, c ≡ (ap + m) mod n requires solving the congruence for p. In solving
this, we rely on multiplicative inverses.
Remarks:
30
Phone No.: (082)300-5456/305-0647 Local 134
Let a’ be an inverse of a modulo n, so that a • a’ ≡ 1 (mod n). Then, if

ax ≡ b (mod n), we can multiply both sides of the congruence by a’ to find that
a’(ax) ≡ a’(b) (mod n), so that x ≡ a’b (mod n).
Now, let’s use the previous example to solve the congruence c ≡ (ap +
m) mod n for p.
c = 3p + 1
c – 1 = 3p Subtract 1 from each side of the equation
9(c – 1) = 9(3p) Multiply each side of the equation by the

multiplicative inverse of 3, which is 9.
Note that 9 • 3 ≡ 1 mod 26.
[9(c – 1)] mod 26 ≡ p Note that 9(3p) ≡ p mod 26 because 9(3) = 27 and
27
= 1 remainder 1.
26
Thus, the decoding congruence is p ≡ [9(c – 1) mod 26.
To decode the ciphertext message FILMX YDCM, we can use the

congruence equation. The decoding process for the word FILMX is presented
below.

F [ 9( 6 – 1) ] mod 26 ≡ 45 mod 26 ≡ 19 S
I [ 9( 9 – 1) ] mod 26 ≡ 72 mod 26 ≡ 20 T
L [ 9(12 – 1) ] mod 26 ≡ 99 mod 26 ≡ 21 U
M [ 9(13 – 1) ] mod 26 ≡ 108 mod 26 ≡ 4 D
X [ 9(24 – 1) ] mod 26 ≡ 207 mod 26 ≡ 25 Y
Example: Decode the message VTONXRT CXRT, which was encrypted using the
congruence c ≡ (3p + 5) mod 26.
Solution:
Solve first the congruence c ≡ (ap + m) mod n for p.
c = 3p + 5
c – 5 = 3p Subtract 5 both sides of the equation
9(c – 5) = 9(3p) Multiply both sides by the multiplicative
inverse of 3 which is 9. [9 • 3 ≡ 1 mod
26]
[9(c – 5] mod 26 ≡ p
The decoding congruence is p ≡ [9(c – 5) mod 26.

Using this congruence, we will show the details for decoding VTONXRT
31
Phone No.: (082)300-5456/305-0647 Local 134

V [9(22 – 5)] mod 26 ≡ 153 mod 26 ≡ 23 W
T [9(20 – 5)] mod 26 ≡ 135 mod 26 ≡ 5 E
O [9(15 – 5)] mod 26 ≡ 90 mod 26 ≡ 12 L
N [9(14 – 5)] mod 26 ≡ 81 mod 26 ≡ 3 C
X [9(24 – 5)] mod 26 ≡ 171 mod 26 ≡ 3 O
R [9(18 – 5)] mod 26 ≡ 117 mod 26 ≡ 13 M
T [9(20 – 5)] mod 26 ≡ 135 mod 26 ≡ 5 E
If we continue the process for the remaining ciphertext, we would decode the
message as WELCOME HOME.

House, Inc.


32
Phone No.: (082)300-5456/305-0647 Local 134
Activity 1. Now that you know the most essential concepts of the application of
modular arithmetic, let us try to check your understanding of these
concepts. You are directed to answer exercises from
MMW Practice Set 9 – F

on pages 97 to 98.
Activity 1. Getting acquainted with the essential concepts of the application of

modular arithmetic, what also matters is you should also be able to
apply these concepts. You are directed to do exercises from
MMW Practice Set 9 – G

on page 99 to 100.
33
Phone No.: (082)300-5456/305-0647 Local 134
Activity 1. Based from the most essential concepts of the application of modular
arithmetic and the learning exercises that you have done, please feel
1.
2.
3.
34
Phone No.: (082)300-5456/305-0647 Local 134
1.
2.
3.
4.
5.
Universal Product
ISBN-10 The Luhn Algorithm
Code (UPC)
ISBN-13 Credit card number UPC Check digit
ISBN-10 check digit Valid card number ISBN-13 check digit
35

GE 4 MMW Week 8 9 (Revised)

Uploaded by

Copyright:

Available Formats

GE 4 MMW Week 8 9 (Revised)

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

GE 4 MMW Week 8 9 (Revised)

Uploaded by

Copyright:

Available Formats

UNIVERSITY OF MINDANAO

College of Arts and Sciences Education

Physically Distanced but Academically Engaged

Self-Instructional Manual (SIM) for Self-Directed Learning (SDL)

Course/Subject: GE 4 – Mathematics in the Modern World

Name of Teacher: ___________________

SIM Prepared by: Prof. Ronnie O. Alejan

THIS SIM/SDL MANUAL IS A DRAFT VERSION ONLY.

THIS IS NOT FOR REPRODUCTION, COMMERCIAL, AND

Week 8-9: Unit Learning Outcomes (ULO):

Big Picture in Focus

1. Modular Arithmetic is a system of arithmetic for integers, which considers

4. Linear Congruence is the problem of finding an integer x satisfying

1. Introduction to Modular Arithmetic

Regular Clock Military Clock

Example. Evaluate each of the following using a 12-hour clock.

Solution: Using a 12-hour clock, we have

Example: Determine whether each of the following congruences is true.

The Leap Year

Leap Year Formula Based on Modular Arithmetic

Computing the Day of the Week

Remember that in the modulo function, we determine the remainder

Using the floor function, Christian Zeller devised a formula to help us

Solving the congruence x ≡ 100 mod 7 for x, we get x = 2. Since 2 corresponds

Example 2. The “Independence Day” of the Republic of the Philippines was

3. Arithmetic Operations Modulo n

Example 1. Addition Modulo n

Evaluate each of the following:

a. (27 + 34) mod 8 b. (39 + 84) mod 7

b. Similarly, the sum of 39 and 84 is 123. Dividing this by the modulus, 7, we

Example 2. Subtraction Modulo n

Evaluate each of the following.

a. (43 – 18) mod 7 b. (27 – 36) mod 6

b. Subtract 27 – 36 = – 9. Since, the result is negative, we must find the value

Disregarding a.m. or p.m., if it is 8 o’clock now, what time was it 55 hours

Since 8 – 55 = – 47 is a negative number, find a whole number x less than

Example 5. Multiplication Modulo n

Evaluate each of the following:

a. (18 • 27) mod 10 b. (21 • 32) mod 13

4. Solving Congruence Equations

Let x=0 3 (0) + 4 ≢ 5 (mod 8)

It shows that one of the solutions is 3.

In general, once an initial solution is determined, additional solutions can

Example 1. Solve the congruence equation, 4x + 7 ≡ 3 (mod 10).

Let x=0 4 (0) + 7 ≢ 3 (mod 10)

Example 2: Not all congruence equations have a solution. For instance, 3x + 2 ≡ 4

Let x=0 3 (0) + 2 ≢ 4 (mod 6)

There is no solution to the congruence equation because no whole number

5. Additive Inverses in Modular Arithmetic

Example 1. Find the additive inverse of 7 in mod 15 arithmetic.

Example 2. Find the additive inverse of 11 in mod 17 arithmetic.

6. Multiplicative Inverses in Modular Arithmetic

Example 1. Find the multiplicative inverse of 5 in mod 7 arithmetic.

In the equation, 5x ≡ 1 mod 7,

Let x=1 5(1) ≢ 1 mod 7 , x=4 5(4) ≢ 1 mod 7,

Since x = 3 satisfies the congruence 5x ≡ 1 mod 7, thus, the multiplicative

Example 2. Find the multiplicative inverse of 7 in mod 11 arithmetic.

In the equation, 7x ≡ 1 mod 11,

Let x=1 7(1) ≢ 1 mod 11, x=6 7(6) ≢ 1 mod 11,

x=2 7(2) ≢ 1 mod 11, x=7 7(7) ≢ 1 mod 11,