CHAPTER

8
Mathematical
Systems

Copyright © Cengage Learning. All rights reserved.

Section 8.2 Applications of Modular
Arithmetic

Copyright © Cengage Learning. All rights reserved.

ISBN and UPC

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

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

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

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

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

8
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.
9
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.

10
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. 11

Credit Card Numbers

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

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

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

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

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

17
Cryptology

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

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

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

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

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

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

24
Example 4 – Solution cont’d

The results for CATHERINE are shown below.

Continuing, the plaintext would be coded as NLESPCTYP

ESP RCPLE.
25
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.

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

27
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

28
Example 5 – Solution cont’d

The results for LASER are shown below.

Continuing, the plaintext is coded in ciphertext as JGSAN

DNUTXAN.

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

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

31