Modular Arithmetic and Check Digits

(1/Person) NAME_________________________________



Modular Arithmetic
Recall that a mod b is the whole number remainder of a/b. So, 9 mod 6 = 3, because 3 is the whole number remainder when 9 is divided by 6. You can also do this on your calculator. 9/6=1.5, so we take the decimal part (.5) and multiply by 6 to get back 3.
  • To calculate 5^7 mod 8, first do 5^7 on your calculator, and then divide by 8. What do you get? (Including the decimal)

  • Now, take just the decimal part (include the decimal point), and multiply by 8. What do you get?

  • This is the whole number remainder of 5^7 when divided by 8. Excel can also do this. If you type in
    =MOD(5^7,8)
    into Excel, you will get the same answer.

    Check digits A small bit of data, such as a credit card, UPC code, part of the number on a check has hidden modular arithmetic structure encoded into it.

    Credit Cards
    Many VISA credit cards are 16 digits long. For example,
    4408 0412 3456 7893
    The last number on the right, in this case a 3, is the check digit. The algorithm used for credit card check digits is called the
    Luhn algorithm:
  • The top row in the chart below is the original number.
  • In the second row, starting from the left we multiply alternate digits by 2. We don't multiply the check digit by 2.
  • In the third row, we subtract 9 from every number that is larger than or equal to 9. (For example, we would leave 8 alone, but 10 would change to 10-9=1). We'll end up with a row containing numbers ranging between 0 and 9.
  • We now add ALL of the digits in the 3rd row together to see if we get that this number mod 10 = 0. If we do (ie if 10 evenly divides the sum of the bottom row), then it is a valid credit card number.

    4 4 0 8 0 4 1 2 3 4 5 6 7 8 9 3
    4 x 2 = 8 4 0 x 2 = 0 8 0 x 2 = 0 4 1 x 2 = 2 2 3 x 2 = 6 4 5 x 2 = 10 6 7 x 2 = 14 8 9 x 2 = 18 3
    8 4 0 8 0 4 2 2 6 4 10 - 9 = 1 6 14 - 9 = 5 8 18 - 9 = 9 3
    If we add ALL of the digits in the bottom row together (8 + 4 + 0 + 8 + 0 + 4 + 2 + 2 + 6 + 4 + 1 + 6 + 5 + 8 + 9 + 3), we get 70. Since 70 mod 10 = 0 (because 70/10 has a 0 remainder) we conclude that the number 4408 0412 3456 7893 is a valid credit card number.

  • Use the Luhn algorithm to show that 4417 1234 5678 9112 is NOT a valid credit card number. SHOW WORK.
    4 4 1 7 1 2 3 4 5 6 7 8 9 1 1 2
      4   7   2   4   6   8   1   2
                        4                     7                    2                    4                     6                     8                     1                     2
  • Add ALL of the digits in the bottom row together. What do you get?

  • Explain why this shows that this is not a valid credit card number.


  • WORTH MORE What would you have to change the check digit to (the last 2) in order to make this a possible credit card number. Explain using your previous two answers and your knowledge of how this method works. Note that even if a credit card number does check out, this does not mean that it is a valid active credit card number. But, this method does enable people to verify that numbers on the credit card were not transposed or misread or mistyped.










    UPC Codes
    A UPC code is 12 digits long, and the check digit is the last digit. For example,
    0       5   1   0   0   0       0   2   5   2   6      5
    has check digit 5. The way the check digit for UPC codes works is that you take it off the last number (the check digit)
    0       5   1   0   0   0       0   2   5   2   6     
    and then you multiply every other number by 3 (starting from the left) and then take mod 10 of the sum. For example,
    3*0     + 5  + 3*1   + 0   +3*0   +0       +3*0   +2   +3*5   +2   +3*6
  • What is this sum?
  • What is mod 10 of this sum (the whole number remainder of the sum when divided by 10)?
    This should match the check digit - does it?

    When a product is scanned in, one wants to be sure that the right number makes it into the computer so that you get charged the correct amount of money. The check digit provides a means for detecting incorrect UPC numbers.
  • How would the check digit detect that the following is not a valid UPC code (the 6 and 2 were transposed - a very easy mistake to make in typing). SHOW WORK!
    0       5   1   0   0   0       0   2   5   6   2      5





  • But, a check digit is not foolproof, so it is not used for security. Explain why the check digit would not detect this misread version of the original UPC code. SHOW WORK and Explain!
    0       5   1   0   0   0       0   2   6   2   5      5






    Suggestion Try this out yourself with a UPC code from an item at the grocery store.
    My UPC/Purchase Seal from Quaker Oats has the number
    0       3   0   0   0   0       0   1   2   0   0      0
    When I perform the calculation above, we get 10, which does yield the correct check digit of 0 (since 10 mod 10 is 0). Note that not all of the numbers on products are actually UPC codes.