Step 8

The Luhn Algorithm is widely used to validate the authenticity of credit card numbers. In web applications, it can be employed to identify misentered credit card numbers rapidly.

The algorithm is simple: sum all odd digits (calculating from right to left) plus the sum of all even digits multiplied by 2 (if the product of multiplication is greater than 9, you must subtract 9). If the last digit of the sum is zero, the whole sequence is valid.

By odd and even digit, we mean the placement of the digit, not its value.

Let's see an example for a Visa number: $4003600000000014$.

From right to left, odd digits (those placed in first, third, fifth, ..., positions) are added up

$$ 4 + 0 + 0 + 0 + 0 + 0 + 3 + 0 = 7 $$

From right to left, even digits are multiplied by two, then added up. If the multiplication product is greater than 9, you must subtract 9

$$ (1 \times 2) + (0 \times 2) + (0 \times 2) + (0 \times 2) + (0 \times 2) + (6 \times 2) + (0 \times 2) + (4 \times 2) $$

which is equal to

$$ 2 + 0 + 0 + 0 + 0 + 12 + 0 + 8 $$

but notice $12 > 9$ so we must replace it with $12 - 9 = 3$

$$ 2 + 0 + 0 + 0 + 0 + 3 + 0 + 8 = 13 $$

Now we add up the result of the sums

$$ 7 + 13 = 20 $$

Since the last digit of the sum ($20$) is zero (i.e., it is a multiple of $10$), the whole sequence is valid.