Credit Card Checks
On your credit/debit card you have a 16 digit number. When you enter it into an online shop their website needs an easy way to check whether your card is a possibly valid one. This is useful because humans are so error prone and so the final digit is used as a check sum and it can be worked out from the other 15 digits.
Before I go into the actual algorithm let's talk about a simpler one and build it up. If we simply added up the first 15 numbers we could look at the final digit of that sum and have that as the 16th digit. That way if a single digit was incorrect then we could tell. It wouldn't tell you where the error was, but it would be enough to decline your card number and get you to reenter. This sort of checksum is called a parity check.
However after misstyping a single digit, the second most common error is transposing the order of two digits. Since every digit counts equally for a parity check this type of error would not be spotted. Instead credit cards use a different check sum called Luhn's Algorithm. Start by taking all the digits in an odd position and summing them. Next take all the numbers in an even position, double them (and take away 9 if they become 2 digit) and then sum them. The last digit should be the number that when added to this sum gives a total which is a multiple of 10.
For example let's try a number 4277 3852 9102 372x. The sum of the odd placed numbers is 4+7+3+5+9+0+3+2=33. The even placed numbers were originally 2, 7, 8, 2, 1, 2 and 7 which we double to get 4, 14, 16, 4, 2, 4 and 14, which we then take 9 from the 2 digit numbers (or add up the digits (the so called digital sum) if you prefer) to get 4+5+7+4+2+4+5=31. Adding the odd and even parts we get 64, so the final digit must be 6 to make this a multiple of 10.
This algorithm still finds any single digit error, but it also finds any two digit swapping except for 09 into 90 or vice versa and so it has a 98% success rate on such errors. The third most common type of human error is twin digits being exchanged for a different twin such as 44 into 55. Luhn's Algorithm finds all twin swaps apart from 22 with 55, 33 with 66 and 44 with 77.
Other check sums in common use are for ISBN numbers on books although that uses a slightly different algorithm. Of course all randomly picked card numbers have a 10% chance of being accepted. Using more than 1 digit lowers this by an order of magnitude per digit.
