sa-id.com
πŸ“ Algorithm Guide

Luhn Algorithm Complete Guide

The mathematical formula behind SA ID validation - also known as the "Mod 10 Algorithm"

What is the Luhn Algorithm?

The Luhn Algorithm (also called Luhn formula or Mod 10 algorithm) is a simple checksum formula used to validate various identification numbers. It was created by IBM scientist Hans Peter Luhn in 1954.

In South Africa, this algorithm is used to calculate and verify the 13th digit (check digit) of every SA ID number. If the check digit doesn't match the Luhn calculation, the ID is invalid.

πŸ“Œ Where is Luhn Algorithm Used?

  • South African ID Numbers
  • Credit Card Numbers (Visa, MasterCard, Amex)
  • IMEI Numbers (Mobile phones)
  • Canadian Social Insurance Numbers
  • Greek Social Security Numbers (AMKA)

How Luhn Algorithm Works (Step by Step)

1

Start from the RIGHT

Take the number (without the check digit) and start from the rightmost digit.

850101123408?
2

Double Every Second Digit

Moving left, double every second digit (positions 2, 4, 6, etc. from right).

850101123408
3

Handle Two-Digit Numbers

If doubling gives a two-digit number (10-18), add those digits together (or subtract 9).

5Γ—2=10 β†’ 1+0=1
1Γ—2=2 β†’ 2
1Γ—2=2 β†’ 2
2Γ—2=4 β†’ 4
4Γ—2=8 β†’ 8
8Γ—2=16 β†’ 1+6=7
4

Sum All Digits

Add all digits (both doubled and non-doubled) together.

Sum = 8 + 1 + 0 + 2 + 0 + 2 + 1 + 4 + 3 + 8 + 0 + 7 = 36
5

Calculate the Check Digit

The check digit is the number needed to make the total sum divisible by 10.

Sum = 36
Next multiple of 10 = 40
Check Digit = 40 - 36 = 4
Complete ID: 8501011234084

πŸ”’ Live Luhn Calculator

Enter any 12-digit number to calculate its Luhn check digit, or enter a 13-digit number to validate it.

πŸ“– Try These Examples

  • β†’ Check digit 4
  • β†’ Check digit 3
  • β†’ Check digit 6
  • β†’ Valid SA ID

πŸ“ Mathematical Formula

Luhn Algorithm Formula:

For a number with digits d₁ dβ‚‚ d₃ ... dβ‚™ (from right to left):

1. For i = 1 to n:
   if (i % 2 == 0):
     dα΅’ = dα΅’ Γ— 2
     if (dα΅’ > 9): dα΅’ = dα΅’ - 9
   
2. Sum = Ξ£ dα΅’ (for all i)

3. Check Digit = (10 - (Sum % 10)) % 10

Validation: (Sum + Check Digit) % 10 == 0

πŸ’‘ Pro Tip: In programming, the Luhn algorithm can be implemented in just 5-10 lines of code in any language!

πŸ’» Code Examples

JavaScript
function luhnCheckDigit(id) {
  let sum = 0;
  for (let i = id.length - 1; i >= 0; i--) {
    let digit = parseInt(id[i]);
    if ((id.length - 1 - i) % 2 === 1) {
      digit = digit * 2;
      if (digit > 9) digit = digit - 9;
    }
    sum += digit;
  }
  return (10 - (sum % 10)) % 10;
}
Python
def luhn_check_digit(id_num):
    total = 0
    for i, digit in enumerate(reversed(id_num)):
        n = int(digit)
        if i % 2 == 1:
            n = n * 2
            if n > 9:
                n = n - 9
        total += n
    return (10 - (total % 10)) % 10
PHP
function luhnCheckDigit($id) {
    $sum = 0;
    $len = strlen($id);
    for ($i = $len - 1; $i >= 0; $i--) {
        $digit = (int)$id[$i];
        if (($len - 1 - $i) % 2 == 1) {
            $digit = $digit * 2;
            if ($digit > 9) $digit = $digit - 9;
        }
        $sum += $digit;
    }
    return (10 - ($sum % 10)) % 10;
}
Java
public static int luhnCheckDigit(String id) {
    int sum = 0;
    for (int i = id.length() - 1; i >= 0; i--) {
        int digit = id.charAt(i) - '0';
        if ((id.length() - 1 - i) % 2 == 1) {
            digit = digit * 2;
            if (digit > 9) digit = digit - 9;
        }
        sum += digit;
    }
    return (10 - (sum % 10)) % 10;
}

πŸ‡ΏπŸ‡¦ Luhn Algorithm in SA ID Numbers

In South African ID numbers, the Luhn algorithm validates the 13th digit. Here's the complete breakdown:

SA ID Structure: 8501011234084

  • 85 = Year (1985)
  • 01 = Month (January)
  • 01 = Day (1st)
  • 1234 = Gender (Female)
  • 0 = Citizen
  • 8 = Race (Historical)
  • 4 = Luhn Check Digit βœ“

Validation Process:

  1. Take first 12 digits: 850101123408
  2. Apply Luhn algorithm
  3. Calculated check digit = 4
  4. Matches provided digit β†’ Valid βœ“

Frequently Asked Questions

Why is it called "Mod 10 Algorithm"?

Because the check digit makes the total sum divisible by 10 (modulo 10 equals 0).

Can the Luhn algorithm detect all errors?

No. It catches single-digit errors and most adjacent transpositions, but not all errors. About 98% of common errors are detected.

Is Luhn algorithm secure?

No. It's not a cryptographic hash. It's only for catching typing errors, not for security or encryption.

Who invented the Luhn algorithm?

Hans Peter Luhn, an IBM scientist, created it in 1954. It was patented in 1960.

Where can I test Luhn validation?

Use our SA ID Validator tool, or try the live calculator on this page!

Disclaimer: This page is for educational purposes. The Luhn algorithm is publicly available and used worldwide for checksum validation.