Page 312 - Discrete Mathematics and Its Applications

4.5 Applications of Congruences 291

EXAMPLE 6 ISBNs All books are identified by an International Standard Book Number (ISBN-10),a
10-digit code x 1 x 2 ...x 10 , assigned by the publisher. (Recently, a 13-digit code known as ISBN-
Remember that the check
13 was introduced to identify a larger number of published works; see the preamble to Exercise
digit of an ISBN-10 can
be an X! 42 in the Supplementary Exercises.) An ISBN-10 consists of blocks identifying the language,
the publisher, the number assigned to the book by its publishing company, and finally, a check
digit that is either a digit or the letter X (used to represent 10). This check digit is selected so
that

9

x 10 ≡ ix i (mod 11),
i=1

or equivalently, so that

10

ix i ≡ 0 (mod 11).
i=1
Answer these questions about ISBN-10s:

(a) The first nine digits of the ISBN-10 of the sixth edition of this book are 007288008. What is
the check digit?

(b) Is 084930149X a valid ISBN-10?

10
Solution: (a) The check digit is determined by the congruence i=1 ix i ≡ 0 (mod 11). Inserting
the digits 007288008 gives x 10 ≡ 1 · 0 + 2 · 0 + 3 · 7 + 4 · 2 + 5 · 8 + 6 · 8 + 7 · 0 + 8 · 0 +
9 · 8 (mod 11). This means that x 10 ≡ 0 + 0 + 21 + 8 + 40 + 48 + 0 + 0 + 72 (mod 11), so
x 10 ≡ 189 ≡ 2 (mod 11). Hence, x 10 = 2.

10
(b) To see whether 084930149X is a valid ISBN-10, we see if i=1 ix i ≡ 0 (mod 11). We
see that 1 · 0 + 2 · 8 + 3 · 4 + 4 · 9 + 5 · 3 + 6 · 0 + 7 · 1 + 8 · 4 + 9 · 9 + 10 · 10 = 0 + 16 +
12 + 36 + 15 + 0 + 7 + 32 + 81 + 100 = 299 ≡ 2 ≡ 0 (mod 11). Hence, 084930149X is not
a valid ISBN-10. ▲

Several kinds of errors often arise in identification numbers. A single error, an error in one
digit of an identification number, is perhaps the most common type of error. Another common
kind of error is a transposition error, which occurs when two digits are accidentally inter-
changed. For each type of identification number, including a check digit, we would like to be
able to detect these common types of errors, as well as other types of errors. We will investigate
Publishers sometimes do
not calculate ISBNs whether the check digit for ISBNs can detect single errors and transposition errors. Whether
correctly for their books, check digits for UPCs can detect these kinds of errors is left as Exercises 26 and 27.
10
as was done for an earlier Suppose that x 1 x 2 ...x 10 is a valid ISBN (so that i=1 i ≡ 0 (mod 10)).We will show that
x
edition of this text. we can detect a single error and a transposition of two digits (where we include the possibility
that one of the two digits is the check digit X, representing 10). Suppose that this ISBN has been
printed with a single error as y 1 y 2 ...y 10 . If there is a single error, then, for some integer j,
y i = x i for i = j and y j = x j + a where −10 ≤ a ≤ 10 and a = 0. Note that a = y j − x j is
the error in the jth place. It then follows that

10 10

iy i = ix i + ja ≡ ja ≡ 0 (mod 11).
i=1 i=1