Mathematical Systems

GE 112
Mathematics in the Modern World
 Modular Arithmetic
Clock Arithmetic

Many clocks have the familiar 12-hour design.

We designate whether the time is before noon
or after noon by using the abbreviation 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.

1 Topic 1 Page 2
 Modular Arithmetic
We will use the symbol ⊕ to denote addition
and the symbol ⊖ to denote subtraction on a
12-hour clock.

Examples
1. Determine the time 8 hours after 3 o’clock.
Solution: Because we did not pass 12 o’clock,
we add 3 and 8. Thus, the time is 11 o’clock.
That is, 3 ⊕ 8 = 11.

1 Topic 1 Page 3
 Modular Arithmetic
2. Determine the time 8 hours after 9 o’clock.
Solution: Since we passed 12 o’clock, we begin
again with 1. Therefore, the time is 5 o’clock.

Another Method: When 9 + 8 = 17 is divided by

12 the remainder is 5. Therefore, 9 ⊕ 8 = 5.

3. If the time now is 10 o’clock, then 7 hours ago

the time was 3 o’clock. That is, 10 ⊝ 7 = 3.

4. If the time now is 3 o’clock, then 7 hours ago

the time was 8 o’clock. That is, 3 ⊝ 7 = 8
1 Topic 1 Page 4
 Modular Arithmetic
Day-of-the-Week Arithmetic

A similar example involves day-of-the week

arithmetic. If we associate each day of the
week with a number,

Monday=1 Tuesday=2 Wednesday=3

Thursday=4 Friday=5 Saturday=6
Sunday=7

1 Topic 1 Page 5
 Modular Arithmetic
Examples

1. 6 days after Friday is Thursday

Solution: When 5 + 6 = 11 is divided by 7 the
remainder is 4, the number associated with
Thursday. Thus, 5 ⊞ 6 = 4.

2. 16 days after Monday is Wednesday

Solution: When 1 + 16 = 17 is divided by 7 the
remainder is 3, the number associated with
Wednesday. Thus, 1 ⊞ 16 = 3.

1 Topic 1 Page 6
 Modular Arithmetic
Arithmetic Modulo n
Modulo n
Two integers a and b are said to be congruent
modulo 𝑛, where 𝑛 is a natural number, if
𝑎−𝑏
is an integer.
𝑛
In this case, we write 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛. The number 𝑛
is called the modulus. The statement
𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑛
is called a congruence.
1 Topic 1 Page 7
 Modular Arithmetic
Examples. Determine whether the
congruence is true.
1. 29 ≡ 8 𝑚𝑜𝑑 3
29−8
Solution: Since = 7 and 7 is an integer,
3
29 ≡ 8 𝑚𝑜𝑑 3 is a true congruence.

2. 15 ≡ 4 𝑚𝑜𝑑 6
15−4 11
Solution: Since = is not an integer,
6 6
15 ≡ 4 𝑚𝑜𝑑 6 is not a true congruence.
1 Topic 1 Page 8
 Modular Arithmetic
3. July 4, 2010, was a Sunday. What day of the week is
July 4, 2015?
Solution: There are 5 years between the two dates. Each
year has 365 days except 2012, which has extra day
because it is a leap year. So the total number of days
between the two dates is
5 365 + 1 = 1826.
Because 1826 ÷ 7 = 260 remainder 6,
1826 ≡ 6 𝑚𝑜𝑑 7.

Any multiple of 7 days past a given day will be the same

day of the week. So the day of the week 1826 days after
July 4, 2010, will be the same as the day 6 days after July
4, 2010. Thus, July 4, 2015 will be a Saturday.

1 Topic 1 Page 9
 Modular Arithmetic
Solution:
2008, 2012, and 2016 are leap years

3(366) + 6(365) = 3288

So,
3288 ≡ 5 𝑚𝑜𝑑 7
The day of the week 3288 days after
Tuesday, February 12, 2008 will be the same
as the day 5 days later, a Sunday.

1 Topic 1 Page 10
 Modular Arithmetic

1 Topic 1 Page 11
 Modular Arithmetic
Arithmetic Operations Modulo n
Procedure: Perform the arithmetic operation and then
divide by the modulus. The answer is the remainder.

Addition Modulo n
Examples:
1. Evaluate: 23 + 38 𝑚𝑜𝑑 12.
Solution: Note that 𝑚 𝑚𝑜𝑑 𝑛 means the remainder
when m is divided by n. Thus, we must find the
remainder of the sum of 23+38 when divided by 12.
Since 23 + 38 = 61 and the remainder when 61
divided by 12 is 1. The answer is 1.

1 Topic 1 Page 12
 Modular Arithmetic
2. Evaluate: 51 + 72 𝑚𝑜𝑑 3.
Answer: 0

3. Evaluate: 65 + 82 𝑚𝑜𝑑 10.

Answer: 7

1 Topic 1 Page 13
 Modular Arithmetic
Subtraction Modulo n
Examples:
1. Evaluate: 33 − 16 𝑚𝑜𝑑 6
Solution: Subtract 33 − 16 = 17. The result is
positive. Divide the difference by the modulus,
6. The answer is the remainder which is equal
to 5.

1 Topic 1 Page 14
 Modular Arithmetic
2. Evaluate: 14 − 27 𝑚𝑜𝑑 5
Solution: Subtract 14 − 27 = −13. Because the
answer is negative, we must find 𝑥 so that
−13 ≡ 𝑥 𝑚𝑜𝑑 5.
Thus we must find x so that the value of
−13−𝑥 −(13+𝑥)
= is an integer.
5 5
Trying the whole number values of 𝑥 less than 5,
the modulus, we find that when
−(13+2)
𝑥 = 2, = −3.
5
Therefore, 14 − 27 𝑚𝑜𝑑 5 = 2.

1 Topic 1 Page 15
 Modular Arithmetic
3. 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 𝑚𝑜𝑑 12. Because 5 − 57 = −52 is a negative
−52−𝑥
number, find a whole number 𝑥 so that is an
12
integer. Evaluating the expression for whole number
values of 𝑥 less than 12, when
−(52 + 8)
𝑥 = 8, = −5,
12
is an integer. Thus, 5 − 57 𝑚𝑜𝑑 12 = 8. Therefore, if
it is 5 o’clock now, 57 hours ago it was 8 o’clock.

1 Topic 1 Page 16
 Modular Arithmetic
Multiplication Modulo n

Example:
1. Evaluate: 15 ∙ 23 𝑚𝑜𝑑 11
Solution: Find the product 15 ∙ 23 and then
divide by the modulus, 11. The answer is the
remainder which is equal to 4.

1 Topic 1 Page 17
 Modular Arithmetic
Solving Congruence Equations
Solving a congruence equation means finding
all whole number values of the variable for
which the congruence is true.
Examples:
1. Solve: 3𝑥 + 5 ≡ 3 𝑚𝑜𝑑 4.
Solution: We search for whole number values
of x for which the congruence is true.

1 Topic 1 Page 18
 Modular Arithmetic

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.

1 Topic 1 Page 19
 Modular Arithmetic
In general, once a solution is determined,
additional solution can be found by repeatedly
adding the modulus to the original solution.
Thus the solution of 3𝑥 + 5 ≡ 3 𝑚𝑜𝑑 4 are
2,6,10,14,18,…

2. Solve: 2𝑥 + 1 ≡ 3 𝑚𝑜𝑑 10

Answer: The solutions are 1,6,11,16,21,26,…

1 Topic 1 Page 20
 Modular Arithmetic
Additive Inverse in Modular Arithmetic
The sum of a number and its additive inverse equals
the modulus.

Example:
1. Find the additive inverse of 7 in mod 16 arithmetic.
Solution: In mod 16 arithmetic, 7 + 9 = 16, so the
additive inverse of 7 is 9.

Note: In mod 16 arithmetic, the additive inverse of 9 is

7.

1 Topic 1 Page 21
 Modular Arithmetic
Multiplicative Inverse in Modular Arithmetic
To find the multiplicative inverse of
𝑎 𝑚𝑜𝑑 𝑚, solve the modular equation
𝑎𝑥 ≡ 1 𝑚𝑜𝑑 𝑚 for 𝑥.
Consider only natural numbers less than the
modulus.
Example:
1. In mod 7 arithmetic, find the multiplicative
inverse of 2.

1 Topic 1 Page 22
 Modular Arithmetic
Solution:
To find the multiplicative inverse of 2, solve the
equation 2𝑥 ≡ 1 𝑚𝑜𝑑 7 by trying different natural
number values of 𝑥 less than the modulus.

In mod 7 arithmetic, the multiplicative inverse of

2 is 4.

1 Topic 1 Page 23
 Modular Arithmetic
Computing the Day of the Week
A function that is related to the modulo function
is called the floor function. In modulo function,
we determine the remainder when one number is
divided by another. In the floor function, we
determine the quotient (ignore the remainder)
when one is divided by another.
Examples:
2 10 17 2
= 0, = 5, = 8, =1
3 2 2 2
1 Topic 1 Page 24
 Modular Arithmetic

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

1 Topic 1 Page 25
 Modular Arithmetic
Zeller’s Congruence:

where
d is the day of the month
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
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
c is the first two digits of the year
x is the day of the week (using 0 for Sunday, 1 for Monday, …,
6 for Saturday)

1 Topic 1 Page 26
 Modular Arithmetic
Example:
1. Determine the day of the week on July 4,
1776.
Solution: We have 𝑐 = 17, 𝑦 = 76, 𝑑 = 4, 𝑚 =
5. Thus,
13 5 − 1 76 17
𝑥≡ + + + 4 + 76 − 2 17 𝑚𝑜𝑑 7
5 4 4
≡ 12 + 19 + 4 + 4 + 76 − 34 𝑚𝑜𝑑 7
≡ 81 𝑚𝑜𝑑 7
Solving 𝑥 ≡ 81 𝑚𝑜𝑑 7 for x, we get 𝑥=
4. Therefore, July 4, 1776, was a Thursday.

1 Topic 1 Page 27
 Modular Arithmetic

Example:
1. Determine the day of the week on
February 18, 2017.

1 Topic 1 Page 28
 Applications of Modular Arithmetic

ISBN

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 cataloged correctly.

1 Topic 1 Page 29
 Applications of Modular Arithmetic

ISBN

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 the
check digit.

1 Topic 1 Page 30
 Applications of Modular Arithmetic

The check digit is used to ensure accuracy.

1 Topic 1 Page 31
 Applications of Modular Arithmetic
Examples.
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: From the formula,

𝑑13 ≡ 10 − [9 + 3 7 + 8 + 3 0 + 7 + 3 4 +
3 + 3 2 + 5 + 3 8 + 2 + 3(0)] 𝑚𝑜𝑑 10
≡ 10 − 97 𝑚𝑜𝑑 10
≡ 10 − 7 = 3

The check digit is 3.

1 Topic 1 Page 32
 Applications of Modular Arithmetic

2. Suppose that a bookstore clerk sends an

order for the American Heritage Dictionary
and inadvertently enters the number 978-0-
395-28517-4, where the clerk transposed 8
and 2 in the five numbers that identify the
book.
Correct ISBN: 978-0-395-82517-4
Incorrect ISBN: 978-0-395-28517-4
Calculating the check digit,

1 Topic 1 Page 33
 Applications of Modular Arithmetic

𝑑13 ≡ 10 − [9 + 3 7 + 8 + 3 0 + 3 + 3 9 +
5 + 3 2 + 8 + 3 5 + 1 + 3(7)] 𝑚𝑜𝑑 10
≡ 10 − 124 𝑚𝑜𝑑 10
≡ 10 − 4 = 6

Because the check digit is 6 and not 4 as it

should be, the receiving clerk knows that an
incorrect ISBN has been sent.

1 Topic 1 Page 34
1. Is 978-0-395-28517-4 a correct ISBN?

𝑑13 ≡ 10 − [9 + 3 7 + 8 + 3 0 + 3 + 3 9 +
5 + 3 2 + 8 + 3 5 + 1 + 3(7)] 𝑚𝑜𝑑 10
≡ 10 − 124 𝑚𝑜𝑑 10
≡ 10 − 4 = 6

The check digit is 6 and not 4 as it should be,

so this is incorrect ISBN.

1 Topic 1 Page 35
 Applications of Modular Arithmetic

UPC

Another coding scheme 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.

1 Topic 1 Page 36
 Applications of Modular Arithmetic

UPC

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 costumers.

1 Topic 1 Page 37
 Applications of Modular Arithmetic

1 Topic 1 Page 38
 Applications of Modular Arithmetic
Example. Find the check digit for the DVD
release of the film Alice in Wonderland. The first
11 digits are 7-86936-79798-?

Solution: From the formula,

𝑑12 ≡ 10 − [3 7 + 8 + 3 6 + 9 + 3 3 +
6 + 3 7 + 9 + 3 7 + 9 + 3 8 ] 𝑚𝑜𝑑 10
≡ 10 − 155 𝑚𝑜𝑑 10
≡ 10 − 5 = 5

The check digit is 5.

1 Topic 1 Page 39
 Applications of Modular Arithmetic

Credit Card Numbers

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.

1 Topic 1 Page 40
 Applications of Modular Arithmetic

Credit Card Numbers

The Luhn algorithm is used to determine whether a
credit card number is valid and is calculated as
follows:
1. Beginning with the next-to-last digit (the last digit
is the check digit) and reading from right to left,
double every other digit.
2. If the digit becomes a two-digit number after
being doubled, treat the number as two
individual digits.
3. Find the sum of the new list of digits; the final
sum must equal 0 mod 10.
1 Topic 1 Page 41
 Applications of Modular Arithmetic
Example. Determine whether 5234 8213 3410 1298
is 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 𝑚𝑜𝑑 10, this is a valid credit
card number.
1 Topic 1 Page 42
 Applications of Modular Arithmetic

2. Is 6011 0123 9145 2317 a valid credit card

number?
Solution: Highlight every other digit, reading
from right to left:
6 0 1 1 0 1 2 3 9 1 4 5 2 3 1 7
Double the highlighted digits:
12 0 2 1 0 1 4 3 18 1 8 5 4 3 2 7
Add all the digits, treating two-digit numbers
as two single digits, we get 53. Since
53 ≢ 0 𝑚𝑜𝑑 10,
this is not a valid credit card number. Page 43
1 Topic 1
 Applications of Modular Arithmetic

Cryptology

Cryptology is the study of making and

breaking secret codes.
Plaintext is a message before it is coded.
Ciphertext is the message after it has been
written in code.
The method of changing from plaintext to
ciphertext is called encryption.
To decrypt a message means to take the
ciphertext message and write it in plaintext.
1 Topic 1 Page 44
 Applications of Modular Arithmetic
Example.
Plaintext: SHE WALKS IN BEAUTY LIKE THE
NIGHT
Ciphertext: ODA SWHGO EJ XAWQPU HEGA PDA
JECDP
(Each letter in the plaintext was encrypted by
substituting the letter that is 22 letters after that letter in
the alphabet and continue from the beginning when the
end of the alphabet is reached. This is called cyclical
coding scheme.)

1 Topic 1 Page 45
 Applications of Modular Arithmetic

How to decrypt the message: Take a word from the

message (usually one with the longer word) and
continue the alphabet for each letter of the word.
When the recognizable word appears, the key can
be determined.

1 Topic 1 Page 46
 Applications of Modular Arithmetic

Once a recognizable word has been found

(BEAUTY), count the number of positions that the
letters have been shifted (four, in this case). To
decode the message, substitute the letter of the
normal alphabet that comes four positions after the
letter in the ciphertext.

1 Topic 1 Page 47
 Applications of Modular Arithmetic

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
1 Topic 1 Page 48
 Applications of Modular Arithmetic

𝑐 ≡ 𝑝 + 𝑚 𝑚𝑜𝑑 26
where,
p - the numerical equivalent of the
plaintext letter

c - the numerical equivalent of the

ciphertext letter.

1 Topic 1 Page 49
 Applications of Modular Arithmetic

Example. Each letter in the previous example was

shifted 22 positions (𝑚 = 22) to the right. To code
the plaintext letter S in the word SHE,

𝑐 ≡ 𝑝 + 𝑚 𝑚𝑜𝑑 26
𝑐 ≡ 19 + 22 𝑚𝑜𝑑 26
𝑐 ≡ 41 𝑚𝑜𝑑 26
𝑐 = 15
The 15th letter is O. Thus, S is coded as O.

1 Topic 1 Page 50
 Applications of Modular Arithmetic

Ciphertext to Plaintext
For the cyclical code, the congruence is
𝑝 ≡ 𝑐 + 𝑛 𝑚𝑜𝑑 26
where,
p and c are defined as before

n = 26 - m

1 Topic 1 Page 51
 Applications of Modular Arithmetic

Example. To decode the letter O in the

ciphertext ODA,

𝑝 ≡ 𝑐 + 𝑛 𝑚𝑜𝑑 26
𝑝 ≡ 15 + 4 𝑚𝑜𝑑 26
𝑝 ≡ 19 𝑚𝑜𝑑 26
𝑝 = 19
The 19th letter is S. Thus, O is decoded as S.

1 Topic 1 Page 52
 Applications of Modular Arithmetic

Example. Use cyclical alphabetic encrypting

code that shifts each letter 11 positions to
a. Code CATHERINE THE GREAT

Answer:
a. NLESPCTYP ESP RCPLE

1 Topic 1 Page 53
 Applications of Modular Arithmetic

Example. Use cyclical alphabetic encrypting

code that shifts each letter 11 positions to
b. Decode TGLY ESP EPCCTMWP

1 Topic 1 Page 54
 Applications of Modular Arithmetic

Example. Use cyclical alphabetic encrypting

code that shifts each letter 11 positions to
b. Decode TGLY ESP EPCCTMWP

Answer:
b. IVAN THE TERRIBLE

1 Topic 1 Page 55
 Applications of Modular Arithmetic

Use the congruence 𝑐 ≡ 5𝑝 + 2 𝑚𝑜𝑑𝑒 26 to

encode the message LASER PRINTER.
Solution. Replace p by the numerical
equivalent of each letter and determine c. the
results for LASER are shown below.

Continuing, the ciphertext is JGSAN

DNUTXAN.
1 Topic 1 Page 56
 Applications of Modular Arithmetic

Example. Decode the message ACXUT

CXRT, which was encrypted using the
congruence 𝑐 ≡ 3𝑝 + 5 𝑚𝑜𝑑 26.
Solution. Solve the congruence for p.
𝑐 = 3𝑝 + 5
𝑐 − 5 = 3𝑝
9 𝑐 − 5 = 9 3𝑝
9 𝑐 − 5 𝑚𝑜𝑑 26 = 𝑝
Thus, the decoding congruence is
𝑝 ≡ 9 𝑐 − 5 𝑚𝑜𝑑 26.
1 Topic 1 Page 57
 Applications of Modular Arithmetic

Using this congruence, we have

Continuing, we decode the message as

PHONE HOME.
1 Topic 1 Page 58
 Applications of Modular Arithmetic

Example. Decode the message JGSAN,

which was encrypted using the congruence
𝑐 ≡ 5𝑝 + 2 𝑚𝑜𝑑 26.
Solution. Solve the congruence for p.
𝑐 = 5𝑝 + 2
𝑐 − 2 = 5𝑝
21 𝑐 − 2 = 21 5𝑝
21 𝑐 − 2 𝑚𝑜𝑑 26 = 𝑝
Thus, the decoding congruence is
𝑝 ≡ 21 𝑐 − 2 𝑚𝑜𝑑 26.
1 Topic 1 Page 59
 References

Reference: Aufmann, R., Lockwood, J.,

Nation, R. and Clegg, D. (2013).
Mathematical Excursions (3rd Edition).
Brooks/Coole: Cengage Learning

1 Topic 1 Page 60