Luhn Algorithm also known as ‘modulus 10’ or ‘mod 10’ algorithm, was created by Hans Peter Luhn in 1954.
It is widely used in Credit/Debit card numbers, IMEI numbers, and Canadian Social Insurance numbers.
What is Luhn Algorithm?
To understand what Luhn algorithm is, we first need to understand what is ‘modulo’. Modulo or Modulus is the remainder after dividing the number with another number. Consider the example 7 divided by 3 has; quotient 2 and remainder 1.
Therefore, modulo 10 equal 0 means after dividing the number with 10, the remainder should be 0. In simple terms the number (dividend) should be a multiple of 10 (divisor).
The Luhn formula verifies a number against its included check digit (last digit), which is usually appended to a partial account number to generate the full account number. This number must pass the following test:
- From the rightmost digit, which is the check digit, and moving left, double the value of every second digit.
- If the result of this doubling operation is greater than 9 (e.g., 8 × 2 = 16), then add the digits of the product (e.g., 16: 1 + 6 = 7, 18: 1 + 8 = 9) or alternatively subtract 9 from the product (e.g., 16: 16 – 9 = 7, 18: 18 – 9 = 9).
- Take the sum of all the digits in step 2.
- Take the sum of all the digits which are not doubled and add it to the total of step 3.
- If the total modulo 10 is equal to 0 (if the total ends in zero) then the number is valid according to the Luhn formula; else it is not valid.
Consider the following example: 30569309025904 (check digit is 4)
|digits (after doubling)||6||10||18||0||0||10||0||x|
|digits (not doubled)||0||6||3||9||2||9||x|
Sum of doubled digits = 6 + (1+0) + (1+8) + 0 + 0 + (1+0) + 0 = 17
Sum of not doubled digits = 0 + 6 + 3 + 9 + 2 +9 = 29
Total = 17 + 29 = 46
If we add the check digit 4 to above sum, the total comes to 46+4 = 50, whose modulo 10 is 0 (in simple terms 50 is a multiple of 10), therefore the number is valid.
Steps to find Check Digit:
- Multiply 46 by 9, which comes to 414
- The unit digit is check digit, i.e., 4
- Take the unit digit of total sum (46), which is 6
- Subtract unit digit from 10, which is 10 – 6 = 4 (check digit)
In case the sum of digits ends in “0”, then the check digit is “0”.
Application of Luhn Algorithm in Audit
Luhn Algorithm can be used to check the credit card sales. Consider this case, which a friend told me. In a retail store the cashier at the till (cash counter) used to take cash from the customer and swipe his credit card for sales made. Well in this case the employee, was caught while scrutinizing credit card sales, as one particular card appeared more than an unusual number of times in the report and on further checking it was revealed that the card in question belonged to the cashier.
Now consider the scenario, where he changes his credit card number in the sales report with some random credit card numbers to hide his activity. In such a case there would be no credit card number that would be showing unusual usage pattern.
So how do we ensure the credit card numbers on the sales report are genuine or not. In such a scenario we can use Luhn algorithm to check the credit card number validity, as credit/debit card numbers are based on Luhn’s algorithm.
I have created an Excel template to validate numbers based on Luhn algorithm.
To download the template click Lunh Algorithm Template.