CHAPTE

8
Mathematical
Systems

Copyright © Cengage Learning. All rights reserved.

1
Section 8.1 Modular Arithmetic

Copyright © Cengage Learning. All rights reserved.

2
Introduction to Modular Arithmetic

3
Introduction to Modular Arithmetic
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 8.1A).

Figure 8.1A

4
Introduction to Modular Arithmetic
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 8.1B

Figure 8.1B

5
Introduction to Modular Arithmetic
We will use the symbol to denote addition on a 12-hour
clock. Using this notation,
and
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).

6
Introduction to Modular Arithmetic
However, if the time now is 3 o’clock, then, using Figure
8.2, 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
and

Figure 8.2

7
Example 1 – Perform Clock Arithmetic
Evaluate each of the following, where and indicate
addition and subtraction, respectively, on a 12-hour clock.
a. b. b. c. c. d.
Solution:
Calculate using a 12-hour clock.
a.

b.

c.

d.
8
Introduction to Modular Arithmetic
A similar example involves day-of-the-week arithmetic. If
we associate each day of the week with a number, as
shown below, then 6 days after Friday is Thursday and 16
days after Monday is Wednesday.

Symbolically, we write
and

9
Introduction to Modular Arithmetic
Note: We are using the symbol for days-of-the-week
arithmetic to differentiate from the symbol for clock
arithmetic.

10
Introduction to Modular Arithmetic
Situations such as these that repeat in cycles are
represented mathematically by using modular arithmetic,
or arithmetic modulo n.

11
Example 2 – Determine Whether a Congruence Is True

Determine whether the congruence is true.

a. 29  8 mod 3
b. 15  4 mod 6

Solution:
a. Find Because 7 is an integer,
29  8 mod 3 is a true congruence.

b. Find Because is not an integer,

15  4 mod 6 is not a true congruence.

12
Introduction to Modular Arithmetic
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.

13
Example 3 – A Day of the Week
July 4, 2017, was a Tuesday. What day of the week is
July 4, 2022?

Solution:
There are 5 years between the two dates. Each year has
365 days except 2020, which has one extra day because it
is a leap year.

So the total number of days between the two dates is

5  365 + 1 = 1826.

14
Example 3 – Solution cont’d

Because 1826 ÷ 7 = 260 remainder 6, 1826  6 mod 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, 2017, will be
the same as the day 6 days after July 4, 2017. Thus July 4,
2022, will be a Monday.

15
Arithmetic Operations Modulo n

16
Arithmetic Operations Modulo n
Arithmetic modulo n (where n is a natural number) requires
us to evaluate a modular expression after using the
standard rules of arithmetic.

Thus we perform the arithmetic operation and then divide

by the modulus. The answer is the remainder.

The result of an arithmetic operation mod n is always a

whole number less than n.

17
Example 4 – 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.

The answer is 1.
18
Example 5 – Subtraction Modulo n
Evaluate each of the following.
a. (33 – 16) mod 6
b. (14 – 27) mod 5

Solution:
a. Subtract The result is positive. Divide the
difference by the modulus, 6. The answer is the
remainder.

(33 – 16) mod 6 = 5

19
Example 5 – Solution cont’d

b. Subtract Because the answer is negative,

we must find x so that –13  x mod 5. Thus we
must find x so that the value of is an
integer.

Trying the whole number values of x less than 5, the

modulus, we find that when x = 2,

(14 – 27) mod 5 = 2

20
Arithmetic Operations Modulo n
The methods of adding and subtracting in modular
arithmetic can be used for clock arithmetic and
days-of-the-week arithmetic.

21
Example 6 – 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 a negative
number, find a whole number x less than the modulus 12,
so that –52  x mod 12.

This means to find x so that is an integer.

22
Example 6 – Solution cont’d

Evaluating the expression for whole number values of x

less than 12, we have, when
an integer.

Thus (5 – 57) mod 12 = 8.

Therefore, if it is 5 o’clock now, 57 hours ago it was 8

o’clock.

23
Arithmetic Operations Modulo n
Problems involving multiplication can also be performed
modulo n.

24
Example 7 – 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.

The answer is 4.
25
Solving Congruence Equations

26
Solving Congruence Equations
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.

27
Solving Congruence Equations

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.

28
Example 8 – Solve a Congruence Equation

Solve: 2x + 1  3 mod 10

Solution:
Beginning with 0, substitute each whole number less than
10 into the congruence equation.

29
Example 8 – Solution cont’d

The solutions between 0 and 9 are 1 and 6; the remaining

solutions are determined by repeatedly adding the
modulus, 10, to these solutions. The solutions are 1, 6, 11,
16, 21, 26, … .
30
Additive and Multiplicative Inverses
in Modular Arithmetic

31
Additive and Multiplicative Inverses in Modular Arithmetic

We have known that if the sum of two numbers is 0, then

the numbers are additive inverses of each other. For
instance, 8 + (–8) = 0, so 8 is the additive inverse of –8,
and –8 is the additive inverse of 8.

The same concept applies in modular arithmetic. For

example, (3 + 5)  0 mod 8. Thus, in mod 8 arithmetic, 3 is
the additive inverse of 5, and 5 is the additive inverse of 3.
Here we consider only those whole numbers smaller
than the modulus.

32
Example 9 – Find the Additive Inverse
Find the additive inverse of 7 in mod 16 arithmetic.

Solution:
In mod 16 arithmetic, so the additive inverse of
7 is 9.

33
Additive and Multiplicative Inverses in Modular Arithmetic

If the product of two numbers is 1, then the numbers are

multiplicative inverses of each other.

For instance, , so 2 is the multiplicative inverse of

, and is the multiplicative inverse of 2. The same
concept applies to modular arithmetic (although the
multiplicative inverses will always be natural numbers).

34
Example 10 – Find a Multiplicative Inverse

In mod 7 arithmetic, find the multiplicative inverse of 2.

Solution:
To find the multiplicative inverse of 2, solve the equation 2x
 1 mod 7 by trying different natural number values of x
less than the modulus.

35
Example 10 – Solution cont’d

In mod 7 arithmetic, the multiplicative inverse of 2 is 4.

36
37
38
Section 8.2 Applications of Modular
Arithmetic

Copyright © Cengage Learning. All rights reserved.

39
ISBN and UPC

40
ISBN and UPC
•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 (or 979), followed
by 9 digits that are divided into three groups of various
lengths. These indicate the country or region, the publisher,
and the title of the book. The last digit (the 13th one) is
called a check digit.

41
ISBN and UPC
•If we label the first digit of an ISBN d1, the second digit d2,
and so on to the 13th digit d13, then the check digit is given
by the following modular formula.

•It is this check digit that is used to ensure accuracy.

42
ISBN and UPC
•Suppose, however, 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 the 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

• The receiving clerk calculates the check digit as 6.

43
ISBN and UPC
•Because the check digit is 6 and not 4 as it should be, the
receiving clerk knows that an incorrect ISBN has been
sent.

•Transposition errors are among the most frequent errors

•that occur.

•The ISBN coding system will catch most of them.

44
Example 1 – Determine a Check Digit for an ISBN

•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:

•The check digit is 3.

45
ISBN and UPC
•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.
46
ISBN and UPC
•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 modular

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
d1, d2, ... , d12, we can write a formula for the UPC check
digit d12.

47
Example 2 – Determine the Check Digit of a
UPC
•Find the check digit for the UPC of the Blu-ray Disc
release of the film Jurassic World. The first 11 digits are
0-25192-21221-?

•Solution:

•The check digit is 5.

48
Credit Card Numbers

49
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 six digits are used to identify the card issuer.

50
Credit Card Numbers
•The table below shows some of the identification prefixes
used by four popular card issuers.

51
Credit Card Numbers
•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.

•Now find the sum of the new list of digits; the final sum
must be congruent to 0 mod 10. The Luhn algorithm is
demonstrated in the next example.

52
Example 3 – Determine a Valid Credit Card Number

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

•Next double each of the highlighted digits.

53
Example 3 – Solution cont’d

•Finally, add all digits, treating two-digit numbers as two

single digits.

•Because 60  0 mod 10, this is a valid credit card number.

54
Cryptology

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

56
Cryptology
•Before we discuss how messages are coded, we need to
define a few terms. 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.
57
Cryptology
•The method of changing from plaintext to ciphertext is
called encryption.

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

•(Continue from the beginning when the end of the

alphabet is reached.) This is called a cyclical coding
scheme because each letter of the alphabet is shifted the
same number of positions.

58
Cryptology
•The original alphabet and the substitute alphabet are
shown below.

•To decrypt a message means to take the ciphertext

message and write it in plaintext.

59
Cryptology
•If a cryptologist thinks a message has been encrypted
using a cyclical substitution code like the one shown
previously, 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.

•When a recognizable word appears, the key can be

determined.

60
Example 4 – Write Messages Using Cyclical Coding

•Use the cyclical alphabetic encrypting code that shifts

each letter 11 positions to
•a. code CATHERINE THE GREAT.

•b. decode TGLY ESP EPCCTMWP.

•Solution:
•a. The encrypting congruence is c  (p + 11) mod 26.
Replace p by the numerical equivalent of each letter of
plaintext and determine c.

61
Example 4 – Solution cont’d

•The results for CATHERINE are shown below.

•
Continuing, the plaintext would be coded as NLESPCTYP
ESP RCPLE.
62
Example 4 – Solution cont’d

•b. Because m = 11, n = 26 – 11 = 15. The ciphertext is

decoded by using the congruence p  (c + 15) mod 26.
The results for TGLY are shown below.

•Continuing, the ciphertext would be decoded as IVAN THE

TERRIBLE.

63
Cryptology
•The practicality of a cyclical alphabetic coding scheme is
limited because it is relatively easy for a cryptologist to
determine the coding scheme.

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

64
Example 5 – Encode a Message
•Use the congruence c  (5p + 2) mod 26 to encode the
message LASER PRINTER.
•
Solution:
•The encrypting congruence is c  (5p + 2) mod 26.
Replace p by the numerical equivalent of each letter from
Table 8.1 and determine c.

Numerical Equivalents for the Letters of the Alphabet

Table 8.1

65
Example 5 – Solution cont’d

•The results for LASER are shown below.

•Continuing, the plaintext is coded in ciphertext as JGSAN

DNUTXAN.

66
Example 6 – Decode a Message
•Decode the message ACXUT CXRT, which was encrypted
using the congruence c  (3p + 5) mod 26.
•

Solution:
•Solve the congruence equation for p.

•The decoding congruence is .

67
Example 6 – Solution cont’d

•Using this congruence, we will show the details for

decoding ACXUT.

•Continuing, we would decode the message as PHONE

HOME.

68
69
70