Applications of Modular Arithmetic PDF

Preview

Summary

LESSON 1 - ISBN UPCEvery book that is catalogued 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 a...

Description

APPLICATIONS OF MODULAR ARITHMETIC

LESSON 1 - ISBN UPC Every book that is catalogued 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. If we label the first digit of an ISBN d 1, the second digit d2, and so on to the 13th digit d13, then the check digit is given by the following modular formula. Formula for the ISBN Check Digit d13 = 10 – (d1 + 3d2 + d3 + 3d4 + d5 + 3d6 + d7 + 3d8 + d9 + 3d10 + d11 +3d12) mod 10 Note: If d13 = 10, then the check digit is 0.

It is this check digit that is used to ensure accuracy. For instance, ISBN for the fourth edition of the America Heritage Directory is 978-0-395-82517-4. However, suppose that the bookstore clerk sends and order for the American Heritage Dictionary and inadvertently enters the number Correct ISBN: 978-0395-82517-4 Incorrect ISBN: 978-0395-28517-4

CHECK DIGIT

The receiving clerk calculates the check digit as follows: (from the Incorrect ISBN) d13 = 10 – (d1 + 3d2 + d3 + 3d4 + d5 + 3d6 + d7 + 3d8 + d9 + 3d10 + d11 +3d12) mod 10 = 10 – [9 + 3(7) + 8 + 3(0) + 3 + 3(9) + 5 + 3(2) + 8 + 3(5) + 1 +3(7)] mod 10 = 10 – 124 mod 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. Transposition errors are among the most frequent errors that occur. The ISBN coding system will catch most of them. 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 d13 = 10 – (d1 + 3d2 + d3 + 3d4 + d5 + 3d6 + d7 + 3d8 + d9 + 3d10 + d11 +3d12) mod 10 = 10 – [9 + 3(7) + 8 + 3(0) + 7 + 3(4) + 3 + 3(2) + 5 + 3(8) + 2 +3(0)] mod 10 = 10 – 97 mod 10 = 10 – 7 =3 Thus, the check digit is 3. Check your progress. A purchase order for the book The Mathematical Tourist by Ivars Peterson includes the ISBN 978-0-716-73250-5. Determine whether this is a valid ISBN or not. (valid ISBN means that the value of d13 and the check digit are the same). Your answer should be: not valid because the given check digit is 5 which is not equal to d13 which is 1.

1

College of Arts and Sciences Department of Natural Sciences and Mathematics

Prepared by: Ma. Jennifer E. Matias

APPLICATIONS OF MODULAR ARITHMETIC

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 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, d3,…, d12, we can write a formula for the UPC check digit d12. Formula for the UPC Check Digit d12 = 10 – (3d1 + d2 + 3d3 + d4 + 3d5 + d6 + 3d7 + d8 + 3d9 + d10 + 3d11) mod 10 Note: If d12 = 10, then the check digit is 0.

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 given the first 11 digits are 0-25192-21221-?. Solution d12 = 10 – (3d1 + d2 + 3d3 + d4 + 3d5 + d6 + 3d7 + d8 + 3d9 + d10 + 3d11) mod 10 = 10 – [3(0) + 2 + 3(5) + 1 + 3(9) + 2 + 3(2) + 1 + 3(2) + 2 + 3(1)] mod 10 = 10 – 65 mod 10 = 10 – 5 =5 Thus, the check digit is 5. Check your progress. Is 1-32342-65933-9 a valid UPC or not? (valid UPC means that the value of d12 and the check digit are the same). Your answer should be: valid because the given check digit is 9 which is equal to d12 which is 9. Lesson 2 – 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. The table below shows some of the identification prefixes used by four popular card issuers. Card Issuer MasterCard Visa American Express Discover

Prefix

Number of digits

51 or 55

16

4

13 or 16

34 or 37

15

6011

16

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, find the sum. Now, the sum of the new 2 College of Arts and Sciences

Department of Natural Sciences and Mathematics

Prepared by: Ma. Jennifer E. Matias

APPLICATIONS OF MODULAR ARITHMETIC

list of digits must be congruent to 0 mod 10. The Luhn algorithm is demonstrated in the next example. 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. 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 Then, get the sum of digits from two digits numbers (1+0) 2 6 4 (1+6) 2 2 3 6 4 2 0 2 2 (1+8) 8 Finally, all the digits. 1 + 2 + 6 + 4 + 7 + 2 + 2 + 3 + 6 + 4 + 2 + 0 + 2 + 2 + 9 + 8 = 60 Since, 60 ≡ 0 mod 10, this is a valid credit card number. Check your progress. Is 6011 0123 9145 2317 a valid credit card number? (valid credit card number must be equal to 0 modulo 10). Your answer should be: not valid because the sum of the digits (after getting the sum of the digits) is not congruent to 0 mod 10.

3 College of Arts and Sciences...