When you type a payment card number into an online form and an error is flagged before the data is even sent, a check digit has almost always been at work. Many everyday codes, such as card numbers, book ISBNs, IBANs and the Italian tax code, contain one or more characters calculated from the others with modular arithmetic. They are there to catch the most common typing errors.
Which errors we want to catch
People copying a code by hand tend to make two kinds of error:
- single error: one wrong digit, for example 7 instead of 1;
- adjacent transposition: two neighbouring digits swapped, for example 34 instead of 43.
The choice of modulus and weights decides which of these errors get caught.
A simple sum is not enough
The most naive idea is to append the sum of the digits modulo 10 as a check digit. It catches every single error, because changing one digit changes the sum by an amount between 1 and 9, never a multiple of 10. But it catches no transpositions at all: the sum does not depend on order. So different positions need different weights.
The Luhn algorithm
It is used for payment card numbers and various other identifiers. Starting from the rightmost digit (the check digit itself):
- double every other digit, starting with the second from the right;
- if a doubled value exceeds 9, subtract 9 (equivalent to adding its two digits);
- add up all the resulting digits;
- the number is valid if the sum is a multiple of 10.
Example with the test number 79927398713, read from the right:
| Digit | 3 | 1 | 7 | 8 | 9 | 3 | 7 | 2 | 9 | 9 | 7 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| After | 3 | 2 | 7 | 7 | 9 | 6 | 7 | 4 | 9 | 9 | 7 |
The sum is 70, a multiple of 10: the number is valid. Swapping the last two digits (…731) makes the sum 72, and the error is flagged.
Luhn catches every single error and almost every adjacent transposition. The exception is swapping 09 and 90: when doubled, 0 stays 0 and 9 becomes 18 − 9 = 9, so the two sequences contribute the same amount.
ISBN-13: weights 1 and 3 modulo 10
The 13-digit ISBN, the same as the EAN barcode on products, uses alternating weights 1 and 3. The code is valid if
c₁ + 3c₂ + c₃ + 3c₄ + … + c₁₃ ≡ 0 (mod 10)
Example: 978-0-306-40615-7. The weighted sum is 100, a multiple of 10.
Single errors: all caught, because multiplying a change of 1 to 9 by 1 or by 3 never gives a multiple of 10 (3 is invertible modulo 10). Transpositions: swapping two adjacent digits a and b changes the sum by 2(a − b), which is a multiple of 10 when a and b differ by 5. Swapping 1 and 6, for instance, goes unnoticed.
ISBN-10: the advantage of a prime modulus
The old 10-digit ISBN used weights from 10 down to 1 and modulus 11:
10c₁ + 9c₂ + 8c₃ + … + 1 · c₁₀ ≡ 0 (mod 11)
Since the remainder can be 10, the check digit could be the letter X. Example: 0-306-40615-2, with weighted sum 132 = 12 · 11.
Modulus 11 is prime, and this gives a stronger result: all single errors and all adjacent transpositions are caught. A transposition changes the sum by (a − b) times a weight difference of 1, and a number between 1 and 9 is never a multiple of 11.
IBAN: modulo 97
An IBAN contains two check digits right after the country code. Verification follows the ISO 13616 standard:
- move the first four characters to the end;
- replace each letter with a number, A = 10, B = 11, …, Z = 35;
- read the result as a single integer;
- the IBAN is valid if the remainder on division by 97 is 1.
With the standard example GB82 WEST 1234 5698 7654 32 the remainder is indeed 1. To compute them, put 00 in their place and take 98 minus the remainder modulo 97.
def iban_valid(iban):
s = iban.replace(" ", "").upper()
s = s[4:] + s[:4]
number = "".join(str(int(c, 36)) for c in s)
return int(number) % 97 == 1
Two check digits and a prime modulus close to 100 make it possible to catch every single error, every adjacent transposition and the vast majority of more complex errors.
What they don't do
A check digit is not a signature or a cryptographic protection: anyone can compute it, and a number that passes Luhn is not thereby a real or active card. In the systems I develop it is a first validation that gives the user immediate feedback, never a substitute for verification with whoever issued the code.
In short
- Check digits use modular arithmetic to catch typing errors.
- A plain sum of digits does not detect transpositions: different weights are needed.
- Luhn detects all single errors and almost all transpositions, except 09 ↔ 90.
- ISBN-13 misses swaps of digits that differ by 5; ISBN-10 and IBAN, with prime moduli, do not.
- A code with the correct check digit is consistent, not necessarily genuine.
