Illuminations: Check That Digit

# Check That Digit

 This lesson introduces students to a common and practical use of modular arithmetic. First the barcode system is examined, specifically UPC and ISBN bar coding. Then, students will discover the applications of modular arithmetic as applied to credit card numbers.

### Learning Objectives

 Students will: Determine the check digit for barcodes and credit card numbers. Test and confirm the validity of barcodes and credit card numbers using appropriate algorithms. Discover the importance of a check digit and explain its strengths and weaknesses. Compare and contrast different check-digit equations.

### Materials

 Check That Digit Activity Sheet Credit cards from mail advertising or other sources Examples of barcodes, ISBN, and UPC labels

### Instructional Plan

 Prior to the lesson, collect samples of barcodes, ISBN, UPC, and sample credit cards (from mail advertisements or from local financial institutions). Not only will these examples provide students with a visual, but they can also be used as part of the lesson when verifying the accuracy of the number. Begin by providing a background for the creation of barcoding systems and how these systems are used today. The first patent for barcodes was issued to Bernard Silver and Norman Woodland in 1952. Since then these coding systems have expanded, been modified, and applied to a variety of areas. One of the most common uses is in retail and grocery stores. Although the barcode is not the price of the item, it does allow for the item to be registered with an associated price. When the bar code is scanned, the associated price will be read by the cash register. Other uses are found in monitoring blood supplies, identification on prescription drugs, book checkout at libraries, tracking luggage, and express shipping services. Another advantage to the barcode system is that when an additional digit is included, known as the check digit, many errors that occur during data entry can be detected. These errors occur when passing information over the phone or internet. It is quite easy for people to transpose numbers (45 when it should be 54), replace a single digit with another, omit digits, or double an incorrect digit (799 is entered as 779). Using a check digit within a check equation helps to catch these errors and verify the validity of the number. As students will see in the ISBN barcode, the number is also used for identification purposes. Begin by taking samples of barcodes that you have collected from items that are sold in stores. This type of barcode is referred to as the Universal Product Code, or UPC. Students will be instructed as to the algorithm and then determine the validity of the number. Next, students should be challenged to determine a check digit for a barcode. The UPC system uses a mod 10 congruence. This system uses a weighting factor of 3 for the digits in the even positions. This means that even-positioned digits will be multiplied by three. For the first example, use the given UPC symbol 7-86936-24425-0 from the movie "The Incredibles." To verify this number, follow the steps: Every even-positioned digit, counting from the right to left, will be multiplied by 3. All odd-positioned digits will be multiplied by 1. 3(7) + 1(8) + 3(6) + 1(9) + 3(3) + 1(6) + 3(2) + 1(4) + 3(4) + 1(2) + 3(5) + 1(0) Sum the products. 0 + 15 + 2 + 12 + 4 + 6 + 6 + 9 + 9 + 18 + 8 + 21 = 110 Determine the validity by dividing the sum by 10. 110 ÷ 10 = 11 remainder 0. Therefore 110 mod 10 = 0. This is a valid UPC number. Students may decide to apply the distributive property and multiply 3 by the sum of the even digits and multiply 1 by the sum of the odd digits. Next provide students with the UPC number 7-96714-78601-y, where y is the check digit. Using the process from above, students should determine the check digit. The sum of the products is 112. The check digit must be 8, because (112+8) mod 10 = 0. On Question 1 of the Check That Digit activity sheet, students will verify the check digit for two UPC numbers. Another barcode system is the International Standard Book Number, or ISBN. This system was developed in the late 1960’s and early 1970’s. It became apparent that there needed to be a uniform system that would identify books that were published throughout the world. Now every book could have a special identification number. The ISBN is a ten‑digit number composed of blocks of numbers that have different meaning. There are four parts to the number, which are separated by hyphens or spaces. The first part of the number identifies the language or country (referred to as the group identifier) and is at most five digits. The second part of the number identifies the publisher and may be at most seven digits. The third part of the number represents the item number or edition for that publisher. It may consist of no more than six digits. The final part is the check digit. Part of the flexibility of this system is the fact that there are many numbers available to be used. Recall that there are a maximum of 10 digits with the 10th being reserved for the check digit. Therefore, the first three parts of the number must have a combined total of nine digits. Leading zeroes are used as place fillers in the event there would not be enough digits in a particular section to ensure there are an appropriate number of digits. The diagram below shows an example of an ISBN number. The check digit is calculated differently than that of the UPC system. Begin by multiplying the first digit by 10, the second by 9, the third by 8, and continue in this fashion until the ninth digit is multiplied by 2. Next, determine the sum of these products. This is a modulus‑11 system, which means that the sum of the products of the first nine digits plus the check digit must be a multiple of 11. One problem that arises in this process is that the check digit might need to be a 10. Because we only have digits 0‑9, an X is written in the check‑digit place. (The X is reflective of the Roman numeral for 10.) Questions 3‑6 on the Check That Digit activity sheet deal specifically with the ISBN. Note: Beginning January 1, 2007, the current ISBN system will be replaced with the ISBN-13 system (for further information, see the ISO Web Site). It is a 13-digit number beginning with 978, followed by the current nine digits of the ISBN, and it will have a new check digit. The check digit will be found using a method different from the current one. When all old ISBN’s have been used, the next series will begin with 979. Credit cards use a system of blocked numbers similar to the ISBN. One obvious difference is that the maximum length for the number is 19 digits, although many numbers range from 13‑16 digits. The first digit of a credit card number is the Major Industry Identifier (MII) and identifies which group issued the card, as shown below. For instance, a number beginning with a 3 would be representative of the travel and entertainment category. The American Express card falls into this category. Cards issued by gas companies are given the beginning digit 7. The popular Visa and MasterCard fall under the banking and financial category (4, 5). The next block of numbers is the Issue Identifier. Including the MII digit, the Issue Identifier is six digits long. The account number begins with the seventh digit and ends with the next‑to‑last digit. The final digit is the check digit.             The process used to determine the check digit is the Luhn algorithm (mod 10), named after IBM scientist Hans Peter Luhn. This algorithm works as follows: Begin by doubling all even-positioned digits when counting from right to left. If doubling results in a two‑digit number, add the digits. For instance, if the original digit were a 6, doubling it would give 12, so use 1 + 2 = 3. Determine the sum of the results from Step 1 and each of the unaffected (odd‑positioned) digits in the original number. Verify the account number by determining if the sum from Step 2 is a multiple of 10. Before proceeding to the questions on the activity sheet pertaining to this topic, have students become more familiar with the Luhn algorithm by determining the validity of the check digit for the following account number: 5314 7726 8593 2112. The sum produced by the algorithm is 65, found as follows: Double the even-positioned digits when counting from left to right (5, 1, 7, 2, 8, 9, 2, 1). This results in 10, 1, 14, 4, 16, 18, 4, 2. Three of these results are two-digit numbers; in those cases, add the digits. Then, the eight numbers to be included in the sum are 1 (= 1 + 0), 1, 5 (= 1 + 4), 4, 7 (= 1 + 6), 9 ( = 1 + 8), 4, 2. Add the results from Step 1 to the unaffected digits from the original number: 1 + 3 + 2 + 4 + 5 + 7 + 4 + 6 + 7 + 5 + 9 + 3 + 4 + 1 + 2 + 2 = 65 The sum is not a multiple of 10. To be a valid account number, this sum must be evenly divisible by 10. If the check digit were 7, the result would be congruent to 0 mod 10; but because the check digit is 2, the sum is not divisible by 10. Therefore, this account number is not valid. The Luhn algorithm is able to detect single data entry errors and most transpositions. Students should proceed to the worksheet and determine how this happens. Prior to beginning the lesson, you may wish to review the solutions.

### Questions for Students

 A problem of the UPC system is that if two adjacent digits that were transposed have a difference of 5, the error will not be detected. Explain why this occurs. [When the original digits are multiplied by 1 and 3 and the transposed digits are multiplied by 1 and 3, the difference of the two sums is 10. This is a problem because the sums of both UPC numbers will yield a remainder of zero when divided by 10.] As we have seen on many television commercials, there are many banking institutions that offer credit cards. The first six digits that appear on a credit card are used for the issue identifier. How many possible issuers are there given each digit 0-9 could be used more than once? [There would be 106 or 1,000,000 possible issue identifiers.] This process is also used to detect most digit transpositions. For instance when entering a number 5832403 the data entry error is transposing the second and third digits: 5382403. There are two digits, when transposed, that will go undetected using the Luhn algorithm. What are they? Explain why this error cannot be detected. [The digits that cannot be detected are 0 and 9. These are unique because the value of these two digits will always be a 0 and 9 regardless of their position in the account number. If the 9 is in the even-numbered position it will be doubled resulting in 18 with a sum of 1+8=9 and the 0 in the odd-numbered position would be unaffected. On the other hand, if 0 were in the even-numbered position, its value doubled would still be 0 and when added to the 9 the sum is still 9. Either way the sum of the two is nine.]

### Assessment Options

 One option is to have the students complete the Activity Sheet for homework. Then over the next week, ask students to find examples of credit card numbers that they see in advertisements or through the mail and verify if the number is valid. It might be a good idea to remind students that unauthorized use of credit card is a form of fraud and is punishable by law. Credit card numbers, like social security numbers, should be protected by their owners to limit identity theft. Another option is to have students develop another type of check equation for an imaginary credit card company. The equation should use a similar system to those discussed in class, but vary the weighting factor, the modulus, and the number of digits. To involve the community, students could interview a professional at a local banking institution and write a short report based on the interview. The report should focus on how the account numbers are coded, how that information is sent/transferred, and what security measures are in place to prevent account number theft.

### Extensions

 Students may research the changing ISBN system from the current 10-digit format to the new 13-digit format. Students should explain the reasons for the new system and determine the benefits and any problems that may occur. They should also determine what types of entities are affected by this major change: businesses, schools, libraries, publishing companies, etc. Students can research other types of codes. Codes are found in the following places: library patron's library cards UPS and Fed Ex to track the shipping of packages zip codes used by the US Postal service supermarket club cards Students should determine the check digit scheme that is used and if the numbers in the code have any specific categorization use.

### Teacher Reflection

 How did the students demonstrate understanding of the materials presented? This lesson shows the importance mathematics plays in something that millions of people use each day. Did the students gain an appreciation for mathematics? Were they interested in learning about how math is used in part of everyday life? What other lessons could be developed that would demonstrate the practically of math? What grouping approach did you choose for this lesson? Partners, groups of 3 or 4? Was this approach effective? Why or why not? What would you change for next time? Were concepts presented too abstractly? Too concretely? How would you change them? Did you find it necessary to make adjustments while teaching the lesson? If so, what adjustments, and were these adjustments effective?

### NCTM Standards and Expectations

 Number & Operations 9-12Use number-theory arguments to justify relationships involving whole numbers. Develop an understanding of permutations and combinations as counting techniques. Develop fluency in operations with real numbers, vectors, and matrices, using mental computation or paper-and-pencil calculations for simple cases and technology for more-complicated cases. Judge the reasonableness of numerical computations and their results.
 This lesson prepared by Doug Schmid.

2 periods

### Web Sites

 More and Better Mathematics for All Students
 © 2000 National Council of Teachers of Mathematics Use of this Web site constitutes acceptance of the Terms of Use The National Council of Teachers of Mathematics is a public voice of mathematics education, providing vision, leadership, and professional development to support teachers in ensuring mathematics learning of the highest quality for all students. The views expressed or implied, unless otherwise noted, should not be interpreted as official positions of the Council.