Check digit

Check digit is a digit computed from other digits in a number sequence and appended to detect transcription errors. Hans Peter Luhn, a researcher at IBM, invented the most widely used check digit algorithm in 1954^[1]. Check digits appear in credit card numbers, identification codes, product barcodes, and book identifiers. They catch common mistakes like single-digit errors and adjacent digit transpositions.

Purpose and function

Check digits serve error detection rather than error correction. When someone enters a number incorrectly, the check digit calculation produces a mismatch, indicating an error occurred. The system cannot determine which digit was wrong or what the correct value should be. Manual verification then resolves the discrepancy.

Single-digit substitution errors are the most common data entry mistake. Typing 4 instead of 7, for instance, happens frequently. Transposition errors, where adjacent digits are swapped (typing 54 instead of 45), represent the second most frequent error type.

Human error rates in manual data entry range from 0.5% to 2% without verification procedures^[2]. Check digits dramatically reduce undetected errors reaching downstream systems.

The Luhn algorithm

Hans Peter Luhn filed his patent application on January 6, 1954, while working at IBM^[1]. U.S. Patent 2,950,048 was granted on August 23, 1960. The algorithm is now in the public domain and specified in ISO/IEC 7812-1.

How the algorithm works

The Luhn algorithm (also called modulus 10 or mod 10) processes a number from right to left:

Starting from the rightmost digit and moving left, double every second digit
If doubling produces a number greater than 9, subtract 9 from the result
Sum all digits (both doubled and undoubled)
The check digit is the amount needed to make the total a multiple of 10

For example, validating credit card number 4539578763621486:

The sum of processed digits equals 70
Since 70 is divisible by 10, the number is valid

Detection capabilities

The Luhn algorithm detects:

All single-digit errors
Most transpositions of adjacent digits
Most twin errors (11 becoming 22)

It fails to detect:

Transposition of 09 to 90 (or vice versa)
Some multiple-digit errors

The algorithm was designed for accidental errors, not deliberate fraud. Cryptographic methods address security concerns.

ISBN check digits

International Standard Book Numbers use two different systems.

ISBN-10

The older 10-digit ISBN system employed modulus 11 arithmetic. Each digit position carries a weight from 10 down to 1. The weighted sum must be divisible by 11.

For ISBN 0-201-53082-1:

(0 x 10) + (2 x 9) + (0 x 8) + (1 x 7) + (5 x 6) + (3 x 5) + (0 x 4) + (8 x 3) + (2 x 2) + (1 x 1) = 99
99 mod 11 = 0, confirming validity

When the required check digit equals 10, the letter X substitutes. This occurs in approximately 1 in 11 ISBNs.

ISBN-13

Since 2007, the 13-digit ISBN has been standard. It uses the EAN-13 algorithm (weights alternating 1 and 3). The check digit ensures the weighted sum is divisible by 10.

ISBN-13 never requires a letter character, simplifying barcode and database systems.

Other applications

Check digits protect numerous identification systems:

Credit cards follow the Luhn algorithm per ISO/IEC 7812. Visa, Mastercard, American Express, and most other cards use this standard.

IMEI numbers identify mobile phones using the Luhn algorithm. The 15-digit code uniquely identifies each device globally.

South African identity numbers include a Luhn check digit in position 13^[3].

European Article Numbers (EAN) use weighted sum algorithms for product barcodes. The ubiquitous UPC barcode employs similar verification.

Vehicle Identification Numbers (VIN) in North America include a check digit in position 9, using a modulus 11 calculation with letter substitution.

IBAN bank accounts use modulus 97 verification for international transfers.

Algorithm comparison

Different check digit schemes offer varying protection levels:

Algorithm	Modulus	Single errors	Transpositions	Used by
Luhn	10	All	Most	Credit cards, IMEI
ISBN-10	11	All	All	Books (legacy)
Verhoeff	10	All	All	Various
Damm	10	All	All	Various

The Verhoeff algorithm, developed by Dutch mathematician Jacobus Verhoeff in 1969, detects all single-digit and transposition errors^[4]. Despite superior detection, Luhn remains dominant due to simplicity and historical adoption.

Hans Damm published another algorithm in 2004 detecting all single substitutions and adjacent transpositions while avoiding X as a possible check digit.

Implementation considerations

Programmers implementing check digit validation should consider:

Input cleaning - Remove spaces, hyphens, and formatting characters before calculation
Leading zeros - Preserve leading zeros which affect weighted sums
Case sensitivity - Handle X consistently for ISBN-10
Performance - Simple algorithms like Luhn execute in constant time

Most programming languages include check digit libraries. Custom implementation requires careful testing against known valid and invalid numbers.

Limitations

Check digits cannot detect:

Errors in multiple positions that coincidentally produce valid results
Deliberately constructed false numbers
Completely fabricated numbers that happen to validate

For high-security applications, cryptographic signatures replace or supplement check digits. Credit card processing adds card verification values (CVV) and transaction authentication.

{{{Concept}}} Primary topic {{{list1}}} Related topics {{{list2}}} Methods and techniques {{{list3}}}

References

Luhn, H.P. (1960). Computer for Verifying Numbers. U.S. Patent 2,950,048.
ISO/IEC 7812-1:2017. Identification cards - Identification of issuers.
Verhoeff, J. (1969). Error Detecting Decimal Codes. Mathematical Centre Tracts 29.
Damm, H.M. (2004). Total anti-symmetric quasigroups. PhD dissertation.

Footnotes

Luhn, H.P. (1960). Computer for Verifying Numbers. U.S. Patent 2,950,048. Filed January 6, 1954.
Reddy, D.R. & Newell, A. (1974). Knowledge and its representation in a speech understanding system. In L.W. Gregg (Ed.), Knowledge and Cognition.
South African Department of Home Affairs. Identity Document Specifications.
Verhoeff, J. (1969). Error Detecting Decimal Codes. Mathematical Centre Tracts 29.

Author: Slawomir Wawak