Luhn Checksum

The Luhn checksum is often used in analog to digital systems such as
many countries ID cards, credit cards and more.

The purpose is NOT to encrypt the number but prevent simple errors
such as digit misplacement and (usually) single digit errors.

Take the following non-existant Visa credit card number:
 

4580 4580 4580 4580
                      

Select all Open in new window

This number is correct using the Luhn checksum method, this doesn't mean
you can use it to shop but programmers often use it to perform a preliminary
check prior to sending it on to be approved.

How is the number checked, let's start:

 

4580 4580 4580 4580
                                                                X
                      2121 2121 2121 2121
                      

Select all Open in new window

[for checking always start on the right from the digit 1]
 

----------------------------
                      8570 8570 8570 8570
                      

Select all Open in new window

Note that we perform single digit multiplication, top line by bottom line, right to left:
 

0 X 1 = 0
                      8 X 2 = 16 -> 1+6 = 7
                      5 X 1 = 5
                      4 X 2 = 8
                      

Select all Open in new window

etc...

As you can see 8 X 2 is written as 7, if the multiplication gives a value of 10
and above always combine the two digits together (e.g. 10 -> 1+0 = 1)

 

8+5+7+0+8+5+7+0+8+5+7+0+8+5+7+0 = 80
                      

Select all Open in new window

Since the right digit is 0 the number is correct!
Or in programmers language, 80 mod 10 = 0 means the number is correct, that is why Luhn is
also sometimes called MOD 10 checking.

Lets take a look at an invalid credit card number:

 

4580 1234 5678 9012
                                                                X
                      2121 2121 2121 2121
                      ----------------------------
                      8570 2264 1658 9022
                      

Select all Open in new window

Again from the right column

2X1=2, 1X2=2, 0X1=0, 9X2=18=>1+8=9, 8X1=8 
                      

Select all Open in new window

etc...

 

8+5+7+0+2+2+6+4+1+6+5+8+9+0+2+2 = 67
                      

Select all Open in new window

---> INVALID!! right digit needs to be 0 to be valid!

So, how do you generate a valid number ?!
The right most digit is the check digit which is why we always begin from the right
as described in the check above.
To generate the number we will begin with the digit 2 instead of 1:

 

1234
                                X
                      1212
                      ------
                      1438
                      
                      1+4+3+8 = 16 -> 10-[right digit] -> 10-6=4
                      

Select all Open in new window

THIS IS THE CHECKDIGIT
NOTE! If the right digit at this stage was 0, then that would be the checkdigit.

Lets check it:

 

12344
                                 X
                      12121
                      --------
                      14384
                      
                      1+4+3+8+4 = 20
                      

Select all Open in new window

YUP! CORRECT!!