# The Luhn Algorithm

Here’s a question I’ve never asked before today but now I know the answer. When you are shopping online and you enter a credit card number into a form, how do they know that it is a valid credit card number? I always imagined that they were immediately checking the number against some database of valid credit card numbers and matching it against my address. That may be true in many cases but is not necessarily so. Most credit card companies employ a method of validating that a credit card number is authentic by method of the Luhn Algorithm, sometime called the modulus 10 algorithm.

In other words, not every 13 or 16 digit number can be a credit card number. I think I had figured out just through inspection that VISA cards start with a 4, Mastercards start with a 5, and Discover cards start with a 6 but the rest of the numbers must satisfy the following test:

1. Take the 1st, 3rd, 5th, 7th, etc. digits from left to right (the odd places). Double each of those numbers. If the value ends up larger than 9, then subtract 9 from it.
2. Then add all of these together with the numbers in the even places.
3. The result must be evenly divisible by 10 (i.e., have a zero in the ones place)

EX: 3205 3211 7082 0010
The odd places are 3, 0, 3, 1, 7, 8, 0, 1 which doubles to 6, 0, 6, 2, 14, 16, 0, 1. The two double digit numbers now need to have 9 subtracted from them resulting in the list 6, 0, 6, 2, 5, 7, 0, 1.
Now we place them back in the odd places resulting in the number: 6205 6221 5072 0020.
Now we sum up these digist 6 + 2 + 0 + 5 + 6 + 2 + 2 + 1 + 5 + 0 + 7 + 2 + 0 + 0 + 2 + 0 = 40.
Thus, this would be a valid credit card number. Note, by the way, that I made that number up and it is not anyone’s credit card number.

EX: Consider the same number with the first digit changed to 2. That is, 2205 3211 7082 0010. After the doubling step we have 4205 6221 5072 0020, which sums to 38 and thus is not a multiple of 10, so it cannot be a valid credit card number.

Problem (from think again!): The number 5439 3201 3232 3209 is not valid. Change the third digit from the left to make it valid.