The Luhn Algorithm: How Credit Card Validation Works

The Luhn algorithm is a simple checksum formula used to validate credit card numbers, IMEI codes, and various identification numbers worldwide. Understanding how it works helps developers implement proper validation and users understand why typos are caught instantly.

The algorithm's primary purpose is error detection—catching accidental mistakes when someone types or transcribes a number. It's remarkably effective at detecting:

• Single-digit errors: Typing 4111111111111112 instead of 4111111111111111
• Transposition errors: Typing 4111111111111 instead of 4111111111111 (most adjacent swaps)
• Random typos: Any change that affects the checksum

1. Start from the rightmost digit (the check digit) and move left
2. Double every second digit (positions 2, 4, 6, 8... from the right)
3. If doubling results in a number > 9, subtract 9 (equivalent to adding the digits)
4. Sum all the digits (both doubled and non-doubled)
5. If the total modulo 10 equals 0, the number is valid

The Formula

For a number with digits d₁d₂d₃...dₙ (right to left):

sum = d₁ + f(d₂) + d₃ + f(d₄) + d₅ + f(d₆) + ...
where f(x) = 2x if 2x ≤ 9, else 2x - 9
Valid if: sum mod 10 = 0

Example with Doubling > 9

When doubling produces a result greater than 9, subtract 9. For example, with digit 7:

7 × 2 = 14
14 > 9, so: 14 - 9 = 5

(This is equivalent to: 1 + 4 = 5)

1. Take your number without the check digit
2. Append a zero (0) as a placeholder
3. Run the Luhn algorithm
4. The check digit is: (10 - (sum mod 10)) mod 10

Example: Generate Check Digit

Base number: 411111111111111 (15 digits, need to find the 16th)

Append 0: 4111111111111110
Run Luhn: sum = 29
29 mod 10 = 9
Check digit = (10 - 9) mod 10 = 1

Complete number: 4111111111111111 ✓

JavaScript

function luhnValidate(number) {
const digits = String(number).replace(/\D/g, '');
let sum = 0;
let isSecond = false;

for (let i = digits.length - 1; i >= 0; i--) {
let digit = parseInt(digits[i], 10);
if (isSecond) {
digit *= 2;
if (digit > 9) digit -= 9;
}
sum += digit;
isSecond = !isSecond;
}
return sum % 10 === 0;
}
function generateCheckDigit(number) {
const digits = String(number).replace(/\D/g, '') + '0';
let sum = 0;
let isSecond = true;
for (let i = digits.length - 1; i >= 0; i--) {
let digit = parseInt(digits[i], 10);
if (isSecond) {
digit *= 2;
if (digit > 9) digit -= 9;
}
sum += digit;
isSecond = !isSecond;
}
return (10 - (sum % 10)) % 10;
}

Python

def luhn_validate(number: str) -> bool:
digits = [int(d) for d in str(number) if d.isdigit()]
checksum = 0

for i, digit in enumerate(reversed(digits)):
if i % 2 == 1:
digit *= 2
if digit > 9:
digit -= 9
checksum += digit
return checksum % 10 == 0
def generate_check_digit(number: str) -> int:
digits = [int(d) for d in str(number) if d.isdigit()] + [0]
checksum = 0
for i, digit in enumerate(reversed(digits)):
if i % 2 == 1:
digit *= 2
if digit > 9:
digit -= 9
checksum += digit
return (10 - (checksum % 10)) % 10

PHP

function luhnValidate($number) {
$digits = preg_replace('/\D/', '', $number);
$sum = 0;
$length = strlen($digits);

for ($i = 0; $i < $length; $i++) {
$digit = (int) $digits[$length - 1 - $i];
if ($i % 2 === 1) {
$digit *= 2;
if ($digit > 9) $digit -= 9;
}
$sum += $digit;
}
return $sum % 10 === 0;
}

Credit Card Numbers

All major credit card networks use Luhn validation:

• Visa: Starts with 4, 16 digits
• Mastercard: Starts with 51-55 or 2221-2720, 16 digits
• American Express: Starts with 34 or 37, 15 digits
• Discover: Starts with 6011 or 65, 16 digits

The standard is defined in ISO/IEC 7812-1.

IMEI Numbers

Every mobile phone has a 15-digit IMEI (International Mobile Equipment Identity) validated by Luhn. The last digit is the check digit. You can find your IMEI by dialing *#06#.

National ID Numbers

• Canadian Social Insurance Number (SIN)
• Greek Social Security Number (AMKA)
• Israeli ID Number
• South African ID Number

Other Uses

• National Provider Identifier (NPI) for US healthcare
• Container shipping codes
• Various loyalty card programs

What Luhn Can't Detect

• 09 ↔ 90 transpositions: These produce the same doubled value
• Intentional fraud: Anyone can generate valid Luhn numbers
• Non-existent accounts: Validation doesn't check if the account exists

Not a Security Measure

Historical Note

Hans Peter Luhn developed the algorithm in 1954 before the digital age. Its simplicity was intentional—it needed to work with mechanical systems. Today, more sophisticated checksums exist, but Luhn remains the standard due to its effectiveness and backward compatibility.

Key takeaways:

• Luhn is for error detection, not security
• It catches single-digit errors and most transpositions
• Used by credit cards, IMEI numbers, and various IDs worldwide
• Simple to implement in any programming language
• Still the industry standard after 70 years