Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Module 5: Mathematical Systems

It’s a dark, rainy night as you pull up to the drive at your home. You press a remote in your car that
opens your garage door and you drive in. You press the remote again and the garage door closes. Unbeknownst
to you, there is a crook lurking on the street with a radio scanner who picks up the signal from your remote. The
next time you’re not home, the crook plans on using the saved signal to open your garage door and burglarize
your home. However, when the crook arrives and sends the signal, the door doesn’t open.
Now suppose you want to make a purchase on the Internet using a credit card. You may have noticed that the
typical http:// that precedes a web address is replaced by https://. The “s” at the end indicates a secure website.
This means that someone who may be trying to steal credit card information cannot intercept the information
you send. Although a garage door opener and a secure website may seem to be quite different, the mathematics
behind each of these is similar. Both are based on modular arithmetic, one of the topics of this chapter.

Learning Outcomes: At the end of the lesson, the students are expected to:
1. perform modular arithmetic
2. perform arithmetic operation modulo n
3. solve linear congruence equations
4. affirm honesty and integrity in the application of modular arithmetic to various human endeavors
5. support the use of mathematics in various aspects and endeavors in life

Lesson 1: Modular Arithmetic

Modular arithmetic, in turn, is part of a branch of mathematics called group theory. Group theory is
used in a variety of many seemingly unrelated subjects such as the structure of a diamond, wallpaper patterns,
quantum physics, and the 12-tone chromatic scale in music.

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, for instance, in Wilson's
theorem, Lucas's theorem, and Hensel's lemma, and generally appears in fields like cryptography, computer
science, and computer algebra. 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. A
number 𝓍 mod N is the equivalent of asking for the remainder of x when divided by N. Two integers a and b are
said to be congruent (or in the same equivalence class) modulo N if they have the same remainder upon division
by N. In such a case, we say that 𝑎 ≡ 𝑏 (mod 𝑁) (Kesa, Williams, and Chattopadhyay, 2020)
Many of us grow up with the idea that 1 + 1 = 2. Since math is commonly perceived as having
everything right or wrong, people will immediately reject the idea of 1+1 = 0. We misunderstand the meaning
of this equation. Most of would never accept the idea that 3*2 = 0. In fact, they should not accept 1+1 = 0 or
even 3*2 = 0 if 1, 2, and 3 are actually natural numbers and + and * are the usual addition and multiplication
operations on natural numbers. What we do not realize is their familiarity with “clock arithmetic.” We
subconsciously accept that 9 + 4 = 1, and 12 + 12 = 12 in 12 hr and that 12 + 12 = 0 in 24 hr. We also accept 30
+ 2 = 1 or 30 + 1 =1, and even 28 + 1 =1 when they think about days in a month. We never take the time to
notice that a more general idea is behind all of these “strange” results when adding times together. These ideas
are used in computer science, and have other applications. Without an understanding of modulo arithmetic,
people won’t appreciate the many things that come as a result of it, such as programs, calendars, time, and the
many tricks and theorems found in Number Theory.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Modular Arithmetic
Many clocks have the familiar 12-hour design. We designate whether the time is before noon or after noon
by using the abbreviations a.m. and p.m. A reference to 7:00 a.m. means 7 hours after 12:00 midnight; a reference
to 7:00 p.m. means 7 hours after 12:00 noon. In both cases, once 12 is reached on the clock, we begin again with
1.
If we want to determine a time in the future or in the past, it is necessary to consider whether we have
passed 12 o’clock. To determine the time 8 hours after 3 o’clock, we add 3 and 8. Because we did not pass 12
o’clock, the time is 11 o’clock (Figure 1). However, to determine the time 8 hours after 9 o’clock, we must take
into consideration that once we have passed 12 o’clock, we begin again with 1. Therefore, 8 hours after 9 o’clock
is 5 o’clock as shown in Figure 2.

Figure 1 Figure 2
Figure 3
We will use the symbol ⊕ to denote addition on a 12-hour clock. Using this notation, 3 ⊕ 8 = 11 and 9
⊕ 8 = 5 on a 12-hour clock. We can also perform subtraction on a 12-hour clock. If the time now is 10 o’clock,
then 7 hours ago the time was 3 o’clock, which is the difference between 10 and 7 (10 – 7) = 3. However, if the
time now is 3 o’clock, then, using Figure 3, we see that 7 hours ago it was 8 o’clock. If we use the symbol ⊖ to
denote subtraction on a 12-hour clock, we can write 10 ⊖ 7 = 3 and 3 ⊖ 7 = 8.
The same method can be applied to 12-hour-clock arithmetic. From the example, when 8 + 7 = 15 is
divided by 12, the number of hours on a 12-hour clock, the remainder is 3, the time 7 hours after 8 o’clock.
Situations such as these that repeat in cycles are represented mathematically by using modular arithmetic, or
arithmetic modulo n.
A similar example involves day-of-the-week arithmetic. If we associate each day of the week with a
number, as shown at the left, then 6 days after Friday is Thursday and 16 days after Monday is Wednesday.
Symbolically, we write 5 ⊞ 6 = 4 and 1 ⊞ 16 = 3.
Note: We are using 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 5 + 6 = 11 is divided by 7, the
number of days in a week, the remainder is 4, the number associated
with Thursday. When 1 + 16 = 17 is divided by 7, the remainder is 3, the number associated
with Wednesday. This works because the days of the week repeat every 7 days.
Monday = 1 Friday = 5
Tuesday = 2 Saturday = 6
Wednesday = 3 Sunday = 7
Thursday = 4
Situations such as these that repeat in cycles are represented mathematically by using modular arithmetic,
or arithmetic modulo n.
Situations such as these that repeat in cycles are represented mathematically by using modular
arithmetic, or arithmetic modulo n. The congruent symbol consisting of three horizontal bars was introduced
in print in 1801 by Carl Friedrich Gauss (1777 – 1855).

When we divide two integers, we will have an equation that looks like the following:

𝐴
= 𝑄 𝑅𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 𝑅
𝐵
where: A is the dividend
B is the divisor
Q is the quotient
R is the remainder
Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

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.
𝑎−𝑏
Modulo n: Two integers a and b are said to be congruent modulo n, where n is a natural number, if is
𝑛
an integer. In this case, we write a ≡ b mod n. The number n is called the modulus. The statement a ≡ b mod n is
called a congruence.
If a ≡ b mod n and a and b are whole numbers, then a and b have the same remainder when divided by n.

Example 1. Find 13 mod 5.

13
Solution: 5 = 2 remainder 3 Hence, 13 mod 5 = 3

Example 2. Determine whether the congruence is true. 29 ≡ 8 mod 3

29−8 21
Solution: Find 3 = 3 = 7. Because 7 is an integer, 29 ≡ 8 mod 3 is a true congruence.

Example 3. Determine whether the congruence is true. 15 ≡ 4 mod 6

15−4 11 11
Solution: Find 6 = 6 . Because 6 is not an integer, 15 ≡ 4 mod 6 is not a true congruence.

Example 4: Now suppose today is Friday. To determine the day of the week 16 days from now, we observe that
14 days from now the day will be Friday, so 16 days from now the day will be Sunday. Note that the remainder
when 16 is divided by 7 is 2, or, using modular notation, 16 ≡ 2 mod 7. The 2 signifies 2 days after Friday, which
is Sunday.

Arithmetic Operations Modulo 𝒏

In modular arithmetic, the numbers we are dealing with are just integers and the operations used are
addition, subtraction, multiplication and division. The only difference between modular arithmetic and the
arithmetic you learned in your primary school is that in modular arithmetic all operations are performed regarding
a positive integer, i.e. the modulus. We will see strange ideas like, “1 + 1 = 0” and “3 * 2 = 0.”
Arithmetic modulo n, where n is a natural number, uses a variation of the standard rules of arithmetic we
have used before. Perform the arithmetic operation and then divide by the modulus. The answer is the remainder.
Thus, the result of an arithmetic operation mod n is always a whole number less than n.
Notice how the only numbers to appear in the tables below are 0, 1, 2, 3, 4, and 5. Any natural number,
when divided by 6, will produce one of these 6 remainders.

Notice from the table 5 + 5 = 4. This seems strange in the usual sense of addition we are used to, but notice
that in mod 6 this is true. In fact, 5 + 5 = 10, and we know that 10 is congruent to 4 (mod 6). So, it is true 5 + 5
does actually equal 4. Similarly, the table above tells us 5 * 5 = 1. Now this no longer comes as a surprise because
we know 5 * 5 = 25, but 25 is actually congruent to 1 (mod 6). Therefore, 5 * 5 = 1. The tables above are accurate
for addition and multiplication... in mod 6 of course!
Modular arithmetic is the application of the usual arithmetic operations – namely addition, subtraction,
multiplication and division – for congruence. Addition, subtraction and multiplication are often simpler to carry
out in modular arithmetic than they are normally, because you can use congruence to reduce large numbers to
small numbers.
Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

A method for finding remainders where all the possible numbers (the numbers less than the divisor) are
put in a circle, and then by counting around the circle the number of times of the number being divided, the
remainder will be the final number landed on.
After dividing one number by another, if any amount is left that does not divide evenly, that amount is
called the remainder. For example, when 8 is divided by 3, three goes in to eight twice (making 6), and the
remainder is 2. When dividing 9 by 3, there is no remainder, because 3 goes in to 9 exactly 3 times, with nothing
left over.

Example 5. Addition Modulo n

Evaluate: (23 + 38) mod 12
Solution: Add 23 + 38 to produce 61. To evaluate 61 mod 12, divide 61 by the modulus, 12. The answer is the
remainder. Hence, the answer is 1.

Example 6. Subtraction Modulo n

Evaluate each of the following.
a. (33 – 16) mod 6
b. (14 – 27) mod 5
Solution:
a. Subtract 33 – 16 = 17. The result is positive. Divide the difference by the modulus, 6. The answer
is the remainder. Hence, (33 – 16) mod 6 ≡ 5.

b. Subtract 14 – 27 = −13. Because the answer is negative, we must find x so that –13  x
−13−𝑥 −(13+𝑥)
mod 5. Thus, we must find x so that the value of = is an integer.
5 5
Trying the whole number values of x less than 5, the modulus, we find that when
−(13+2) 15
x = 2, 5 = − 5 = −3. Hence, (14 – 27) mod 5 = 2.

Example 7. Calculating Times: Disregarding a.m. or p.m., if it is 5 o’clock now, what time was it 57 hours ago?
Solution: The time can be determined by calculating (5 – 57) mod 12. Because 5 – 57 = −52 is negative, find a
−52−𝑥 −(52+𝑥)
whole number 𝑥 less than the modulus 12, so that −52 = 𝑥 mod 12. This means to find 𝑥 so that 12
=
12
is
−(52+𝑥) 60
an integer. Evaluating the expression for whole number values of 𝑥 less than 12, we have, when 𝑥 = 8, =− =
12 12
−5, an integer. Thus, (5 – 57) mod 12 ≡ 8. Therefore, if it is 5’oclock now, 57 hours ago it was 8 o’clock.

Example 8. Multiplication Modulo n:

Evaluate: (15 ∙ 23) mod 11
Solution: Find the product 15 ∙ 23 and then divide by the modulus, 11. The answer is the remainder. Hence, the
answer is 4.

Example 9. Division Modulo n: Modular division can be performed by considering the related multiplication
problem. For instance, if 5 ÷ 7 = 𝑥, then 𝑥 ∗ 7 = 5. Similarly, the quotient (5 ÷ 7) mod 8 is the solution to
the congruence equation 𝑥 ∗ 7 ≡ 5 𝑚𝑜𝑑 8 which is 3.
Solution:
Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

7𝑥 ≡ 5 mod 8
𝑥=0 7(0) ≢ 5 mod 8
𝑥=1 7(1) ≢ 5 mod 8
𝑥=2 7(2) ≢ 5 mod 8
𝑥=3 7(3) ≢ 5 mod 8 is the answer.
𝑥=4 7(4) ≢ 5 mod 8
𝑥=5 7(5) ≢ 5 mod 8
𝑥=6 7(6) ≢ 5 mod 8
𝑥=7 7(7) ≢ 5 mod 8

Therefore, (5 ÷ 7) mod 8 = 3

Solving Congruence Equations

In this lesson we will solve linear congruences such as 5𝑥 ≡ 2 (mod 12), where 𝑥 is an unknown. A
linear congruence is a congruence of the form 𝑎𝑥 ≡ 𝑏 (mod 𝑛), where 𝑎 and 𝑏 are known, and 𝑥 is unknown.
The process of finding the values of 𝑥 for which a linear congruence is true is called solving the linear
congruence. Any number 𝑥 for which the linear congruence is true is a solution of the linear congruence. If 𝑥 is
a solution of a linear congruence, then any number in the same residue class as 𝑥 modulo 𝑛 is also a solution. So,
the solutions are given by linear congruences of the form 𝑥 ≡ 𝑐 (mod 𝑛).
Solving a congruence equation means finding all whole number values of the variable for which the
congruence is true.

For example, to solve 3x + 5 = 3 mod 4, we search for whole number values of x for
which the congruence is true.
3(0) + 5 ≠ 3 mod 4
3(1) + 5 ≠ 3 mod 4
3(2) + 5 = 3 mod 4 2 is a solution.
3(3) + 5 ≠ 3 mod 4
3(4) + 5 ≠ 3 mod 4
3(5) + 5 ≠ 3 mod 4
3(6) + 5 = 3 mod 4 6 is a solution.

If we continued trying values, we would find that 10 and 14 are also solutions. Note that the solutions 6,
10, and 14 are all congruent to 2 modulo 4. In general, once a solution is determined, additional solutions can be
found by repeatedly adding the modulus to the original solution. Thus, the solutions of 3x + 5 = 3 mod 4 are 2, 6,
10, 14, 18, .... When solving a congruence equation, it is necessary to check only the whole numbers less than the
modulus. For the congruence equation 3x + 5 = 3 mod 4, we needed to check only 0, 1, 2, and 3. Each time a
solution is found, additional solutions can be found by repeatedly adding the modulus to it. A congruence equation
can have more than one solution among the whole numbers less than the modulus. The next example illustrates
that you must check all whole numbers less than the modulus.

Example 10. Solve: (2𝑥 + 1) ≡ 3 mod 10

Solution:
𝑥 = 0 2(0) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 1 2(1) + 1 ≡ 3 𝑚𝑜𝑑 10 is a solution
𝑥 = 2 2(2) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 3 2(3) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 4 2(4) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 5 2(5) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 6 2(6) + 1 ≡ 3 𝑚𝑜𝑑 10 is a solution
𝑥 = 7 2(7) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 8 2(8) + 1 ≢ 3 𝑚𝑜𝑑 10
𝑥 = 9 2(9) + 1 ≢ 3 𝑚𝑜𝑑 10
The solutions are 1 and 6.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Example 11. (4𝑥 + 1) ≡ 5 mod 12

Solution:
𝑥 = 0 4(0) + 1 ≢ 5 𝑚𝑜𝑑 12
𝑥 = 1 4(1) + 1 ≡ 5 𝑚𝑜𝑑 12 is a solution
𝑥 = 2 4(2) + 1 ≢ 5 𝑚𝑜𝑑 12
𝑥 = 3 4(3) + 1 ≢ 5 𝑚𝑜𝑑 12
𝑥 = 4 4(4) + 1 ≡ 5 𝑚𝑜𝑑 12 is a solution
𝑥 = 5 4(5) + 1 ≢ 5 𝑚𝑜𝑑 12
𝑥 = 6 4(6) + 1 ≡ 5 𝑚𝑜𝑑 12
𝑥 = 7 4(7) + 1 ≢ 5 𝑚𝑜𝑑 12 is a solution
𝑥 = 8 4(8) + 1 ≢ 5 𝑚𝑜𝑑 12
𝑥 = 9 4(9) + 1 ≢ 5 𝑚𝑜𝑑 12
𝑥 = 10 4(10) + 1 ≡ 5 𝑚𝑜𝑑 12 is a solution
𝑥 = 11 4(11) + 1 ≢ 5 𝑚𝑜𝑑 12
The solutions are 1, 4, 7, and 10.

Example 12. (4𝑥 + 6) ≡ 5 𝑚𝑜𝑑 8

Solution:
𝑥 = 0 4(0) + 6 ≢ 5 𝑚𝑜𝑑 8
𝑥 = 1 4(1) + 6 ≡ 5 𝑚𝑜𝑑 8
𝑥 = 2 4(2) + 6 ≢ 5 𝑚𝑜𝑑 8
𝑥 = 3 4(3) + 6 ≢ 5 𝑚𝑜𝑑 8
𝑥 = 4 4(4) + 6 ≡ 5 𝑚𝑜𝑑 8
𝑥 = 5 4(5) + 6 ≢ 5 𝑚𝑜𝑑 8
𝑥 = 6 4(6) + 6 ≡ 5 𝑚𝑜𝑑 8
𝑥 = 7 4(7) + 6 ≢ 5 𝑚𝑜𝑑 8
There is no solution.

Activity.
Solve the following problems and show complete solution.
1. Evaluate each of the following, where ⊕ and ⊖ indicate addition and subtraction, respectively, on a 12-hour
clock.
a) 8 ⊕ 7
b) 7 ⊕ 12
c) 3 ⊕ 5
d) 2 ⊖ 14
e) 5 ⊖ 10

2. Evaluate each expression, where ⊞ and ⊟ indicate addition and subtraction, respectively, using days-of-the-
week arithmetic.
a) 6 ⊞ 4
b) 3 ⊞ 5
c) 2 ⊞ 3
d) 3 ⊞ 6
e) 2 ⊞ 14

3. Use the notation A mod B = R to mean that A has remainder R when divided by B.
a) 8 mod 3
b) 17 mod 8
c) 8 mod 4
d) 7 mod 5
e) 6 mod 5

4. Determine whether the congruence is true or false. Show necessary solutions

a) 5 ≡ 8 mod 3
b) 5 ≡ 20 mod 4
c) 21 ≡ 45 mod 6
d) 88 ≡ 5 mod 9
Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

5. List five different natural numbers that are congruent to 10 modulo 4.

6. Evaluate each expression, where ⊕ and Θ indicate addition and subtraction, respectively, using military time.
(Military time uses a 24-hour clock, where 2:00 a.m. is equivalent to 0200 hours and 10 p.m. is equivalent to
22 hours)
a) 1800 ⊕ 0900
b) 0800 ⊕ 2000
c) 1000 Θ 1400
d) 0200 Θ 0500

7. Find all whole number solutions of the congruence equation:

a) (2𝑥 + 2) ≡ 6 𝑚𝑜𝑑 4
b) (5𝑥 + 4) ≡ 2 𝑚𝑜𝑑 8
c) (3𝑥 + 12) ≡ 7 𝑚𝑜𝑑 10
d) (2𝑥 + 3) ≡ 8 𝑚𝑜𝑑 12
e) 3𝑥 ≡ 8 𝑚𝑜𝑑 11

8. Perform the modular arithmetic.

a) (9 + 15) mod 7
b) (5 + 22) mod 8
c) (42 + 35) mod 3
d) (37 + 45) mod 12
e) (48 − 21) mod 6

9. Pretend that it's 3:00 now. Answer the following questions, but don't worry about AM/PM.
a) In 17 hours, what time will the clock show?
b) In 33 hours, what time will the clock show?
c) What time did the clock show 15 hours ago?
d) What time will the clock read 17 hours after the time it shows 19 hours before 4:00?

10. Find all whole number solutions of the congruence equation:

a) 𝑥 ≡ 10 mod 3
b) (2𝑥 + 1) ≡ 5 mod 4
c) (4𝑥 + 3) ≡ 3 mod 4
d) 5𝑥 ≡ 21 mod 9
e) 11𝑥 ≡ 6 mod 38

11. Determine a whole number solution between 0 and 11 of the congruence equation: (𝑥 2 + 3𝑥 + 7) ≡
2 𝑚𝑜𝑑 11.

Lesson 2: Applications of Modular Arithmetic

In the previous lesson, the basic modular arithmetic such as performing operations and solving congruence
equations was presented. This lesson includes the applications of modular arithmetic such as ISBN, UPC, Credit
card numbers, Money orders, Banking, Bar codes and cryptology.

Learning Outcomes: At the end of the lesson, the students are expected to:
1. use coding schemes to encode and decode different types of information for identification, privacy and
security
2. apply modular arithmetic in validating ISBN, UPC, credit card numbers, money order number, banking
number, and bar codes
3. apply mathematical principles and modular arithmetic in cryptography
4. affirm honesty and integrity in the application of modular arithmetic to various human endeavors
5. support the use of mathematics in various aspects and endeavors in life

A function that is related to the modulo function is called the floor function. In the modulo function, we
determine the remainder when one number is divided by another. In the floor function, we determine the quotient

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

(and ignore the remainder) when one number is divided by another. The symbol for the floor function is ⎣ ⎦. Here
are some examples.
2 10 17 2
⌊ ⌋ = 0, ⌊ ⌋ = 5, ⌊ ⌋ = 8, and ⌊ ⌋ = 1
3 2 2 2 √

Using the floor function, we can write a formula that gives the day of the week for any date on the
Gregorian calendar. The formula, known as Zeller’s congruence, is given by
13𝑚 − 1 𝑦 𝑐
𝑥 ≡ (⌊ ⌋ + ⌊ ⌋ + ⌊ ⌋ + 𝑑 + 𝑦−: 2𝑐) mod 7
5 4 4
Where:
𝑑 is the day of the month
𝑚 is the month using 1 for March, 2 for April,…,10 for December; January and February are assigned the values
11 and 12, respectively
𝑦 is the last two digits of the year if the month is March through December; if the month is January or February,
𝑦 is the last two digits of the year 𝑚𝑖𝑛𝑢𝑠 1
𝑐 is the first two digits of the year
𝑥 is the day of the week (using 0 for Sunday, 1 for Monday,…, 6 for Saturday)

For example, to determine the day of the week on July 4, 1776, we have 𝑐 = 17, 𝑦 = 76, 𝑑 = 4, and 𝑚 = 5.
Using these values, we can calculate 𝑥.
13(5) − 1 76 17
𝑥 ≡ (⌊ ⌋ + ⌊ ⌋ + ⌊ ⌋ + 4 + 76 − 2(17)) mod 7
5 4 4
𝑥 ≡ (12 + 19 + 4 + 4 + 76 − 34)mod 7
𝑥 ≡ 81mod 7

Solving 𝑥 ≡ 81mod 7 for 𝑥, we get 𝑥 = 4. Therefore, July 4, 1776, was Thursday.

1. Determine the day of the week on which you were born.
2. Determine the day of the week on which Philippine Independence (June 12, 1898) fell.

Rolling Codes. Some garage door openers are programmed using modular arithmetic. See page 1. The
basic idea is that there is a computer chip in both the transmitter in your car and the receiver in your garage that
are programmed exactly the same way. When the transmitter is pressed, two things happen. First, the transmitter
sends a number to the receiver; second, the computer chip uses the sent number and modular arithmetic to create
a new number that is sent the next time the transmitter is pressed. Here is a simple example
using a modulus of 37. A real transmitter and receiver would use a number with at least 40 digits.
𝑥0 = 23 This number is called the seed.
𝑥1 ≡ (5𝑥0 + 17)mod 37 This is the modular formula.
≡ (5 ∙ 23 + 17)mod 37 Using this formula, a new
≡ 132 mod 37 number, 21, is calculated when
≡ 21 the transmitter is pressed.
𝑥2 ≡ (5𝑥1 + 17)mod 37 When the transmitter is pressed
≡ (5 ∙ 21 + 17)mod 37 again, the last number
≡ 122mod 37 calculated, 21, is used to find the
≡ 11 next number.

This continues each time the transmitter is pressed. A general form for this formula is written as 𝑥𝑛+𝑟 ≡
(5𝑥𝑛 + 17)mod 37 and is called a recursive formula. The next number 𝑥𝑛+1 is calculated using the previous
number 𝑥𝑛 .

1. Use the recursive formula 𝑥𝑛+1 ≡ (2𝑥𝑛 + 13)mod 11 and seed 𝑥0 = 3 to find the numbers 𝑥1 to 𝑥9 .
2. Find 𝑥10 . How is this number related to 𝑥0 ? (Remember: The last number you calculated in part 𝑎 is
𝑥9 .)
3. Why might this recursive formula not be a good one for an actual garage door opener?

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

ISBN (International Standard Book Number)

Every book that is cataloged in the Library of Congress must

have an ISBN (International Standard Book Number). This 13-digit
number was created to help ensure that orders for books are filled
accurately and that books are catalogued correctly.
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. If we label the first digit of an ISBN 𝑑1 , the second digit 𝑑2 , and so on to the 13th
digit 𝑑13, then the check digit is chosen to satisfy the following congruence.
Formula for the ISBN check number

𝑑13 = 10 − (𝑑1 + 3𝑑2 + 𝑑3 + 3𝑑4 + 𝑑5 + 3𝑑6 + 𝑑7 + 3𝑑8 + 𝑑9 + 3𝑑10 + 𝑑11 + 3𝑑12 )mod 10

If 𝑑13 = 10, then the check digit is 0.

It is this check digit that is used to ensure accuracy. For instance, the ISBN for the fourth edition of the American
Heritage Dictionary is 978-0-395-82517-4.

Example 1. Determine the ISBN check digit for the book The Equation that Couldn’t Be Solved by Mario Livio.
The first 12 digits of the ISBN are 978-0-7432-5820-?
Solution:
𝑑13 = 10 − (𝑑1 + 3𝑑2 + 𝑑3 + 3𝑑4 + 𝑑5 + 3𝑑6 + 𝑑7 + 3𝑑8 + 𝑑9 + 3𝑑10 + 𝑑11 + 3𝑑12 )mod 10
𝑑13 = 10 − (9 + 3(7) + 8 + 3(0) + 7 + 3(4) + 3 + 3(2) + 5 + 3(8) + 2 + 3(0))mod 10
𝑑13 = 10 − (9 + 21 + 8 + 0 + 7 + 12 + 3 + 6 + 5 + 24 + 2 + 0)mod 10
𝑑13 = 10 − 97 mod 10
𝑑13 = 10 − 7
𝑑13 = 3
Therefore, the ISBN check digit is 3.

Example 2. 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.
Solution:
𝑑13 = 10 − (9 + 3(7) + 8 + 3(0) + 7 + 3(6) + 0 + 3(7) + 3 + 3(2) + 6 + 3(1))mod 10
𝑑13 = 10 − (9 + 21 + 8 + 0 + 7 + 18 + 0 + 21 + 3 + 6 + 6 + 3)mod 10
𝑑13 = 10 − 102 mod 10
𝑑13 = 10 − 2
𝑑13 = 8 Because the check digit does NOT match, the ISBN is invalid.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

UPC (Universal Product Code)

Another coding scheme that is closely related to the
ISBN is the UPC (Universal Product Code). This number
is placed on many items and is particularly useful in
grocery stores. A check-out clerk passes the product by a
scanner, which reads the number from a bar code and
records the price on the cash register. If the price of an item
changes for a promotional sale, the price is updated in the computer, thereby relieving a clerk of having to reprice
each item.
In addition to pricing items, the UPC gives the store manager accurate information about inventory and
the buying habits of the store’s customers. The UPC is a 12-digit number that satisfies a congruence equation that
is similar to the one for ISBNs. The last digit is the check digit. If we label the 12 digits of the UPC as
𝑑1 , 𝑑2 , … , 𝑑12, we can write a formula for the UPC check digit 𝑑12.

Formula for the UPC Check Digit

𝑑12 = 10 − (3𝑑1 + 𝑑2 + 3𝑑3 + 𝑑4 + 3𝑑5 + 𝑑6 + 3𝑑7 + 𝑑8 + 3𝑑9 + 𝑑10 + 𝑑11)mod 10

If 𝑑12 = 10, then the check digit is 0.

Example 3. Find the check digit for the DVD release of the film Alice in Wonderland. The first 11 digits are 7-
86936-79798-.
Solution:
𝑑12 = 10 − (3(7) + 8 + 3(6) + 9 + 3(3) + 6 + 3(7) + 9 + 3(7) + 9 + 3(8))mod 10
𝑑12 = 10 − (21 + 8 + 18 + 9 + 9 + 6 + 21 + 9 + 21 + 9 + 24)mod 10
𝑑12 = 10 − 155 mod 10
𝑑12 = 10 − 5
𝑑12 = 5 Hence, the check digit is 5.

Example 4. Is 1-32342-65933-9 a valid UPC?

Solution:
Let us prove the equation,
9 = 10 − (3(1) + 3 + 3(2) + 3 + 3(4) + 2 + 3(6) + 5 + 3(9) + 3 + 3(3) + 9)mod 10
9 = 10 − (3 + 3 + 6 + 3 + 12 + 2 + 18 + 5 + 27 + 3 + 9 + 9) mod 10
9 = 10 − 100 mod 10
9 = 10 − 0
9 = 10, since, 9 ≠ 10, hence, the given UPC is invalid.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Credit Card Numbers

Companies that issue credit cards also use modular arithmetic to determine whether a credit card number is
valid. This is especially important in e-commerce, where credit card information is frequently sent over the
Internet. The primary coding method is based on the Luhn algorithm, which uses mod 10 arithmetic.
Credit card numbers are normally 13 to 16 digits long. The first one to four digits are used to identify the card
issuer. The table below shows the identification prefixes used by four popular card issuers.

The Luhn algorithm, used to determine whether a credit card number is valid, is calculated as follows:
Beginning with the next-to-last digit (the last digit is the check digit) and reading from right to left, double
every other digit. If a digit becomes a two-digit number after being doubled, treat the number as two individual
digits.

Example 5. Determine whether 5234 8213 3410 1298 is a valid credit card number.
Solution:
Highlight every other digit, beginning with the next-to-last digit and reading from right to left.
5 2 3 4 8 2 1 3 3 4 1 0 1 2 9 8
Next double each of the highlighted digits
10 2 6 4 16 2 2 3 6 4 2 0 2 2 18 8
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 + 2 + 1 + 8 + 8 = 60
Because 60 ≡ 0 mod 10, this is a valid credit card number.

Money Orders
Some money orders have serial numbers that
consist of a 10-digit number followed by a check digit.
The check digit is chosen to be the sum of the first 10
digits mod 9.
Example 6. Determine the check digit for the given
money order serial number.
a) 0316615498-
b) 5492877463-
c) Determine whether the serial number of the money order on the right is valid.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Solution:

a) (0 + 3 + 1 + 6 + 6 + 1 + 5 + 4 + 9 + 8) mod 9 = 43mod 9 = 7. Hence, the check digit is 7.

b) (5 + 4 + 9 + 2 + 8 + 7 + 7 + 4 + 6 + 3) mod 9 = 55mod 9 = 1. Hence, the check digit is 1.
c) Since the serial number of the money order number is 88000165023, let us prove that
3 = (8 + 8 + 0 + 0 + 0 + 1 + 6 + 5 + 0 + 2)mod 9
3 = 30mod 9
Since, this is true, hence, the serial number of the money order is valid.

Banking
When banks process an electronic funds transfer (EFT), they assign a nine-digit routing number, where
the ninth digit is a check digit. The check digit is chosen such that when the nine digits are multiplied in turn by
the numbers 3, 7, 1, 3, 7, 1, 3, 7, and 1, the sum of the resulting products is 0 mod 10. For instance, 123456780 is
a valid routing number because 1(3) + 2(7) + 3(1) + 4(3) + 5(7) + 6(1) + 7(3) + 8(7) + 0(1) = 150 and
150 = 0 mod 10.

Example 7. Compute the check digit for the routing number 72859372-.
Solution:
7(3) + 2(7) + 8(1) + 5(3) + 9(7) + 3(1) + 7(3) + 2(7) + 𝑥 (1) = 0mod 10
21 + 14 + 8 + 15 + 63 + 3 + 21 + 14 + 𝑥 = 0mod 10
159 + 𝑥 = 0mod 10
𝑥 = 1, hence, the checking digit for the routing number is 1.

Example 8. Verify that 584926105 is a valid routing number.

Solution: Let us prove that, 5(3) + 8(7) + 4(1) + 9(3) + 2(7) + 6(1) + 1(3) + 0(7) + 5(1) = 0mod 10
15 + 56 + 4 + 27 + 14 + 6 + 3 + 0 + 5 = 0mod 10
130 = 0mod 10, since, this is true, hence, the given routing number is valid.

Example 9. If a bank clerk inadvertently types the routing number in part b as 584962105, will the computer
be able to detect the error?
Solution: Let us check whether the new routing number is valid.

5(3) + 8(7) + 4(1) + 9(3) + 6(7) + 2(1) + 1(3) + 0(7) + 5(1) = 0mod 10

15 + 56 + 4 + 27 + 42 + 2 + 3 + 0 + 5 = 0mod 10
154 = 0mod 10, since, this is NOT true, hence, the given routing number is not valid. Therefore, the computer
will be able to detect the error.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Bar Codes. The Codabar system is a bar code method

developed in 1972 that is commonly used in libraries.

Each bar code contains a 14-digit number, where

the 14th digit is a check digit. The various check digit
schemes discussed in this section are designed to detect
errors, but they cannot catch every possible error. The
Codabar method is more thorough and will detect any single mistyped digit as well as any adjacent digits that
have been transposed, with the exception of 9–0 and 0–9. To determine the check digit, label the first 13 digits
𝑎1 through 𝑎13 .
The check digit is given by
(−2𝑎1 − 𝑎2 − 2𝑎3 − 𝑎4 − 2𝑎5 − 𝑎6 − 2𝑎7 − 𝑎8 − 2𝑎9 − 𝑎10 − 2𝑎11 − 𝑎12 − 2𝑎13 − 𝑟) mod 10
where r is the number of digits from the digits 𝑎1 , 𝑎3 , 𝑎5 , 𝑎7 , 𝑎9 , 𝑎11 , 𝑎𝑛𝑑 𝑎13 that are greater than or equal to
5.

For example, the bar code with the number 3194870254381- has digits 𝑎3 , 𝑎5 , 𝑎𝑛𝑑 𝑎9 that are greater than or
equal to 5. Thus 𝑟 = 3 and
−2(3) − 1 − 2(9) − 4 − 2(8) − 7 − 2(0) − 2 − 2(5) − 4 − 2(3) − 8 − 2(1) − 3 = −87 = 3mod 10 .
Hence, the check digit is 3.

Example 10. Find the check digit for the bar code number 1982273895263-.
Solution: It has digits 𝑎3 𝑎𝑛𝑑 𝑎9 that are greater than or equal to 5, thus, 𝑟 = 2. Then,

−2(1) − 9 − 2(8) − 2 − 2(2) − 7 − 2(3) − 8 − 2(9) − 5 − 2(2) − 6 − 2(3) − 2 = −95 = 5mod 10 ,

hence, the check digit is 5.

Example 11. Find the check digit for the bar code number 6328293856384-.

Solution: It has digit 𝑎1 that is greater than or equal to 5, thus, 𝑟 = 1. Then,

−2(6) − 3 − 2(2) − 8 − 2(2) − 9 − 2(3) − 8 − 2(5) − 6 − 2(3) − 8 − 2(4) − 1 = −91 = 9mod 10 ,
hence, the check digit is 9.
Cryptology
Related to codes on books and grocery items are secret codes. These codes are used to send messages
between people, companies, or nations. 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.

Plaintext is a message before it is coded.

The line SHE WALKS IN BEAUTY LIKE THE NIGHT from Lord Byron’s poem “She Walks in
Beauty” is in plaintext.
Ciphertext is the message after it has been written in code.
The line ODA SWHGO EJ XAWQPU HEGA PDA JECDP is the same line of the poem in
ciphertext.
The line from the poem was encrypted by substituting each letter in plaintext with the letter that is 22
letters after that letter in the alphabet. This is called a cyclical coding scheme because each letter of the alphabet
is shifted the same number of positions. The original alphabet and the substitute alphabet are shown below.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Example 12. Encode the message “MATHEMATICS” by using a cyclical alphabetic encrypting code that shifts
the message in 22 positions
Solution:

The line from the poem was encrypted by substituting each letter in plaintext with the letter that is 22
letters after that letter in the alphabet. This is called a cyclical coding scheme because each letter of the alphabet
is shifted the same number of positions.
Therefore, the corresponding ciphertext of MATHEMATICS is “ IWPDAIWPEYO”.
The method of changing from plaintext to ciphertext is called Encryption.

Example 13. Encode the message “SHE WALKS IN BEAUTY LIKE THE NIGHT” by using a cyclical
alphabetic encrypting code that shifts the message into 22 positions.
Solution:

The corresponding ciphertext is “ODA SWHGO EJ XAWQPU HEGA PDA JECDP”.

To decrypt a message means to take the ciphertext message and write it in plaintext. If a cryptologist
thinks 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 and continuing the alphabet for each letter of the word.

Example 14. Use a cyclical alphabetic encrypting code that shifts the letters the stated number of positions to
decode the encrypted message “XAWQPU”.
Solution:

The decoded message is “BEAUTY”

Cyclical encrypting using the alphabet is related to modular arithmetic. We begin with the normal alphabet and
associate each letter with a number as shown in the illustration below.

Numerical Equivalents for the Letters of the Alphabet

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 𝐜 ≡ (𝒑 + 𝒎) 𝐦𝐨𝐝 𝟐𝟔 ,
Where: p is the numerical equivalent of the plaintext letter and

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

c is the numerical equivalent of the ciphertext letter.

Example 15. Use the cyclical alphabetic encrypting code that shifts each letter 11 positions to
a. encode CATHERINE THE GREAT
b. decode TGLY ESP EPCCTMWP

Solution:
a. The encrypting congruence is c ≡ (𝑝 + 11) mod 26. Replace p by the numerical equivalent of each
letter of plaintext and determine c. The results for CATHERINE THE GREAT are shown below.
C c

Continuing, the plaintext is coded as NLESPCTYP ESP RCPLE.

b. Because 𝑚 = 11, 𝑛 = 26 − 11 = 15. The ciphertext is decoded by using the congruence
𝑐 ≡ (𝑝 + 15) 𝑚𝑜𝑑 26. The results for TGLY are shown below.

Continuing, the ciphertext is decoded as IVAN THE TERRIBLE

Example 16. Use the congruence 𝑐 ≡ (5𝑝 + 2) mod 26 to encode the message LASER PRINTER.
Solution. The encrypting congruence is 𝑐 ≡ (5𝑝 + 2) 𝑚𝑜𝑑 26. Replace p by the numerical equivalent of each
letter and determine c. The results for LASER are shown below.

Continuing, the plaintext is coded in ciphertext as JGSAN DNUTXAN.

Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

Example 17. Decode the message ACXUT CXRT, which was encrypted using the congruence 𝑐 ≡
(3𝑝 + 5) mod 26.
Solution. Solve the congruence equation for p.
𝑐 ≡ (3𝑝 + 5)
𝑐 − 5 = 3𝑝
9(𝑐 − 5) = 9(3𝑝)
[9(𝑐 − 5)] mod 26 ≡ 𝑝
The decoding congruence is 𝒑 ≡ [𝟗(𝒄 − 𝟓)] 𝐦𝐨𝐝 𝟐𝟔.

Using this congruence, we will show the details for decoding ACXUT.

Continuing, we would decode the message as PHONE HOME.

Activity:
Solve the following problems. Show complete solution.
1. Determine whether the given number is a valid ISBN.
a) 978-1-55690-182-9
b) 978-0-143-03943-3
2. Determine the correct check digit for each ISBN.
a) Facebook for Dummies by Leah Pearlman and Carolyn Abram; 978-0-470-87804-?
b) The Girl with the Dragon Tattoo by Stieg Larsson; 978-0-307-47347-?
3. Determine the correct check digit for the UPC.
a) 0-33317-20083-? (TI-84 Silver Edition calculator)
b) 0-71818-02100-? (Guittard real semisweet chocolate chips)
4. Determine whether the given credit card is a valid number.
a) 6011-4988-1002-6487
b)

5. Find the check digit for the bar code number 1982273895263-?.
6. Decode the message LOFT JGMK LBS MNWMK that was encrypted using the congruence 𝑐 ≡
(3𝑝 + 4)mod 26.
Revision 02
Section 3 Mathematics as a Tool (Part 2) GECMAT CHMSU – CAS Mathematics Department

7. Use the encrypting congruence 𝑐 ≡ (5𝑝 + 3)mod 26 to code the message DAYLIGHT SAVINGS
TIME.

Revision 02