Casting Out Nines and Check Digits

This article has three layers:

1. The intuition: casting out nines, casting out elevens, and the errors they can and can't catch
2. Real-world use: ISBNs, EAN/UPC barcodes, bank card Luhn, ID numbers and IBANs, with brief extensions to CRC and Verhoeff
3. The mathematics: $\mathbb{Z}/n\mathbb{Z}$, ring homomorphisms, kernels and why "modulo a prime" catches more, with a worked example for each method

Layer 1: The Intuition

1.1 Casting out nines: checking arithmetic with "digit sums"

In primary school you compute $3847\times 526$ and get $2023522$. How can you quickly check it?

Casting out nines goes like this:

1. Add up the digits of each number, repeating until one digit remains (you can also throw away any $9$ along the way, which is what "casting out nines" means):
   • $3847$: $3+8+4+7=22$, $2+2=4$
   • $526$: $5+2+6=13$, $1+3=4$
2. Do the same operation on these two "representatives": $4\times 4=16$, $1+6=7$
3. Compute the digit sum of the answer: for $2023522$, $2+0+2+3+5+2+2=16$, $1+6=7$
4. Both sides are $7$, so it passes the check.

Addition and subtraction work the same way:

• $3847+526=4373$. The left side is $4+4=8$, and the right side is $4+3+7+3=17$, $1+7=8$. They agree.
• $3847-526=3321$. The left side is $4-4=0$, and the right side is $3+3+2+1=9$, which is $0$ after casting out nines. They agree.

Why can a digit sum represent a number? Because "the sum of the digits" and the original number have the same remainder when divided by $9$. For example $3847\div 9=427$ remainder $4$, exactly the digit sum $22\to 4$. The reason is that $10$ leaves remainder $1$ when divided by $9$, so $100,1000,\dots$ also leave remainder $1$, and each digit contributes to the remainder only by "its own size". Layer 3 makes this rigorous.

And "remainders" have a nice property: compute then reduce equals reduce then compute. So if the true answer leaves remainder $7$ when divided by $9$ but yours leaves $5$, your answer must be wrong.

1.2 What casting out nines can and can't catch

What it catches: most single-digit mistakes. For example, writing $2023522$ as $2023532$ changes the digit sum to $17\to 8\ne 7$, which shows up at once.

What it misses:

To sum up: whenever the difference between the wrong and right answers is a multiple of $9$, casting out nines can't see it. "Swapping" in the first row is the most common slip, and it falls exactly in this class: swapping adjacent digits $a,b$ gives a difference of $9\times(a-b)\times 10^k$.

1.3 Casting out elevens: using "alternating sums" to fill the gaps

Using the remainder modulo $11$ instead fixes the swap problem. Because $10$ leaves remainder $-1$ modulo $11$ (that is, remainder $10$),

The remainder of a number modulo $11$ $=$ the alternating sum, starting from the units digit, adding then subtracting

For example:

• $3847$: $7-4+8-3=8$
• $526$: $6-2+5=9$
• $8\times 9=72$, and $72$ leaves remainder $6$ modulo $11$
• $2023522$: $2-2+5-3+2-0+2=6$, which agrees ✓

Now look at the two errors casting out nines just missed:

• The swap error $2203522$: alternating sum $2-2+5-3+0-2+2=2\ne 6$, caught
• The $9000$-too-many error $2032522$: remainder $8\ne 6$ modulo $11$, caught too

But casting out elevens has blind spots as well: it can't catch errors whose difference is a multiple of $11$, such as swapping two digits one position apart (both have the same sign, so the alternating sum is unchanged). So in practice the two are often used together. An error slips past both checks only if its difference is a multiple of both $9$ and $11$, that is, a multiple of $99$.

1.4 From "checking arithmetic" to "checking numbers"

Check digits use this idea in reverse. Casting out nines checks "the result of a computation"; check digits check "a number being copied or typed":

1. Define a "fingerprint function", such as "a weighted sum, reduced modulo $11$"
2. When issuing a number, add one digit (the check digit) so that the whole number's fingerprint equals some fixed value, such as $0$
3. When someone copies or scans the number, recompute the fingerprint. If it is wrong, the number is wrong

The two most common errors in human copying are:

• Single-digit errors: $\dots 4\dots \to \dots 7\dots$, about $60\%$–$80\%$ of manual input errors
• Adjacent swaps: $\dots 45\dots \to \dots 54\dots$, about $10\%$–$20\%$

Designing a check digit means choosing the "modulus" and "weights" so that all of these two classes are caught. Below we look at how each scheme does on these two points.

Layer 2: Real-World Use

First a summary table, with each row explained afterwards:

The pattern is obvious: schemes with a prime modulus ($11$, $97$) do best. Layer 3 explains why.

2.1 ISBN-10: modulo $11$, where the check digit can be X

Book numbers before 2007 had $10$ digits $a_1a_2\cdots a_{10}$, with the rule

$$10a_1+9a_2+8a_3+\cdots+2a_9+1\cdot a_{10}\equiv 0 \pmod{11}.$$

Because there are $11$ remainders modulo $11$, from $0$ to $10$, the check digit $a_{10}$ sometimes has to equal $10$, which is written as the Roman numeral X. That is why some older books have numbers ending in X.

Example: ISBN 0-306-40615-2 (an example commonly used by Wikipedia and other sources)

The total is $=132=12\times 11\equiv 0\pmod{11}$ ✓

An example with X: 0-8044-2957-X. The weighted sum of the first $9$ digits is $0+72+0+28+24+10+36+15+14=199$, and $199\equiv 1\pmod{11}$. The check digit $c$ must satisfy $1+c\equiv 0$, so $c=10$, written X.

Error detection: all single-digit errors and all swaps (not just adjacent ones) are caught.

• Writing the 8th digit $1$ as $7$: the total becomes $132+3\times 6=150\equiv 7\not\equiv 0$, caught
• Writing 40615 as 46015 (swapping $0$ and $6$): the total is $\equiv 6\not\equiv 0$, caught

2.2 ISBN-13, EAN-13, UPC: modulo $10$, weights $1$ and $3$

Supermarket barcodes and today's book numbers use this scheme. Reading left to right, the weights alternate $1,3,1,3,\dots$:

$$a_1+3a_2+a_3+3a_4+\cdots+a_{13}\equiv 0\pmod{10}.$$

(The $12$-digit UPC-A has weights $3,1,3,1,\dots$ from the left, on the same principle.)

Example: ISBN-13 978-0-306-40615-7

The total is $=100\equiv 0\pmod{10}$ ✓. The UPC example 036000291452 passes the same way.

Error detection:

• Single-digit errors: all caught, because multiplying by $1$ or $3$ never turns a nonzero difference into a multiple of $10$.
• Adjacent swaps: swapping $a,b$ changes the total by $\pm 2(a-b)$. When $|a-b|=5$, the change is $\pm 10\equiv 0$, and it can't be caught.
  • Example: writing 40615 as 40165 (swapping $6$ and $1$) gives 978-0-306-40165-7, which still passes.
  • The $5$ missed pairs are $0\leftrightarrow5$, $1\leftrightarrow6$, $2\leftrightarrow7$, $3\leftrightarrow8$ and $4\leftrightarrow9$.

To stay compatible with barcode systems, ISBN-13 gave up ISBN-10's modulus $11$, so its error detection actually got weaker.

2.3 Bank card numbers: the Luhn algorithm

The last digit of Visa, Mastercard, UnionPay and other card numbers is a Luhn check digit (proposed by Hans Peter Luhn of IBM in 1954). The rule:

1. From right to left, multiply the $2,4,6,\dots$th digits by $2$
2. If the result has two digits, add them (equivalent to subtracting $9$), for example $7\times 2=14\to 1+4=5$
3. Add all the digits; the total must be $\equiv 0\pmod{10}$

Example: 4111 1111 1111 1111 (Visa's public test card number, commonly used in payment development, not a real card)

From right to left, the even positions (positions $1,3,5,\dots,15$ from the left) are doubled:

• The leftmost $4$ is in a doubled position: $4\to 8$
• The other $7$ doubled positions are all $1$: $1\to 2$, totaling $7\times 2=14$
• The $8$ undoubled $1$s: totaling $8$

The total is $=8+14+8=30\equiv 0\pmod{10}$ ✓

If you mistakenly write the second-to-last digit as $2$ (...1121), this digit is doubled and becomes $4$. The total becomes $32\not\equiv 0$, and it is caught.

Error detection:

• Single-digit errors: all caught, because "double and take the digit sum" maps $0,1,\dots,9$ one-to-one to $0,2,4,6,8,1,3,5,7,9$, a permutation
• Adjacent swaps: only one kind is missed, $09\leftrightarrow 90$. For example, the made-up numbers 4090 0000 0000 0003 and 4900 0000 0000 0003, both pass Luhn
• For why only this pair is missed, see section 3.6 in Layer 3

2.4 Digit 18 of the Chinese resident ID: ISO 7064 MOD 11-2

In the $18$-digit ID number $a_1a_2\cdots a_{18}$, the first $6$ digits are a region code, the next $8$ are the date of birth, the next $3$ are a sequence code, and the last, $a_{18}$, is the check digit. The rule is

$$\sum_{i=1}^{18} a_i\cdot 2^{18-i}\equiv 1\pmod{11},$$

where $a_{18}$ is written as X if it needs to equal $10$. This is why some people's ID numbers end in X, for exactly the same reason as ISBN-10.

Reducing $2^{18-i}$ modulo $11$, the weights of the first $17$ digits are

$$7,\ 9,\ 10,\ 5,\ 8,\ 4,\ 2,\ 1,\ 6,\ 3,\ 7,\ 9,\ 10,\ 5,\ 8,\ 4,\ 2,$$

and the last digit has weight $2^0=1$. In practice, first compute the weighted sum $S$ of the first $17$ digits, then look it up:

(This table is the result of solving $S+c\equiv 1\pmod{11}$.)

Example: 11010519491231002X. This is the example number from the national standard GB 11643—1999, and doesn't correspond to a real person.

$S=167=15\times 11+2$, so $S\equiv 2$, and the table gives check digit X ✓. Verification: $167+10=177=16\times 11+1\equiv 1$ ✓.

If the birthday 1231 is copied as 1213 (swapping the adjacent $3,1$), the computed check digit becomes $9$, which doesn't match X, and it is caught.

Error detection: all single-digit errors and all adjacent swaps are caught.

2.5 IBAN: modulo $97$

International bank account numbers (IBANs, used in Europe, the Middle East and elsewhere) have two check digits, under the rule ISO 7064 MOD 97-10:

1. Move the first $4$ characters (the country code and two check digits) to the end
2. Replace letters with two-digit numbers: $\mathrm{A}=10,\ \mathrm{B}=11,\ \dots,\ \mathrm{Z}=35$
3. The resulting large integer must be $\equiv 1\pmod{97}$

Example: GB82 WEST 1234 5698 7654 32. This is a fictional example account commonly used in IBAN standards documents.

• Move: WEST12345698765432GB82
• Replace letters ($\mathrm{W}=32,\ \mathrm{E}=14,\ \mathrm{S}=28,\ \mathrm{T}=29,\ \mathrm{G}=16,\ \mathrm{B}=11$):

$$N=3214282912345698765432161182$$

• To compute $N\bmod 97$ by hand, work in segments: take a segment, reduce it, attach the remainder to the front of the following digits, and reduce again:

$$\begin{aligned} 321428291 &\equiv 70 \pmod{97}\\ 702345698 &\equiv 29 \pmod{97}\\ 297654321 &\equiv 24 \pmod{97}\\ 2461182 &\equiv 1 \pmod{97}\ \checkmark \end{aligned}$$

This segmented method also works because reduction is a ring homomorphism, as Layer 3 explains.

To generate the check digits, first compute $N_0$ with the check digits set to 00; the check digits are then $98-(N_0\bmod 97)$. In this example the result is exactly $82$.

Why $97$: $97$ is the largest prime below $100$. Two check digits can represent at most $100$ values, $97$ uses nearly all of them, and being prime it detects the most errors. IBAN catches all single-character errors and all adjacent digit swaps, with an actual miss rate of about $1/97\approx 1\%$.

2.6 Extensions: CRC and Verhoeff

Layer 3: The Mathematics

3.1 Congruence and $\mathbb{Z}/n\mathbb{Z}$

Fix a positive integer $n$. If $n\mid a-b$, we say $a\equiv b\pmod n$. This is an equivalence relation, and the equivalence class of $a$ is written

$$\bar a = a+n\mathbb{Z}=\{\dots,a-n,\ a,\ a+n,\ \dots\}.$$

All the classes form $\mathbb{Z}/n\mathbb{Z}=\{\bar 0,\bar 1,\dots,\overline{n-1}\}$, with operations defined by

$$\bar a+\bar b=\overline{a+b},\qquad \bar a\,\bar b=\overline{ab}.$$

3.2 The reduction map is a ring homomorphism

Define

$$\pi:\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z},\qquad \pi(a)=\bar a.$$

The operations defined in 3.1 give directly

$$\pi(a+b)=\pi(a)+\pi(b),\qquad \pi(ab)=\pi(a)\,\pi(b),\qquad \pi(1)=\bar 1,$$

so $\pi$ is a (surjective) ring homomorphism. In words, "compute then reduce $=$ reduce then compute", that is,

$$\overline{ab}=\bar a\,\bar b .$$

Casting out nines is the case $n=9$: to check $c\stackrel{?}{=}ab$, just check whether $\bar c\stackrel{?}{=}\bar a\,\bar b$ holds in $\mathbb{Z}/9\mathbb{Z}$. $\mathbb{Z}/9\mathbb{Z}$ has only $9$ elements, so very little computation is needed.

Mind the direction of the logic:

$$c=ab\ \Longrightarrow\ \pi(c)=\pi(a)\pi(b),$$

but the converse fails. So casting out nines can only refute, never confirm.

The segmented reduction for IBANs is also an application of the homomorphism property. Let $N=A\cdot 10^k+B$. Then

$$\pi(N)=\pi(A)\,\pi(10)^k+\pi(B),$$

so you can first replace $A$ with its remainder $r$ and then reduce $r\cdot 10^k+B$, and the result is unchanged.

3.3 Why "$10\equiv 1$" gives the digit sum

Let $N=\sum_{k=0}^{m} d_k\,10^k$, where $d_k\in\{0,\dots,9\}$ are the digits. With the homomorphism $\pi:\mathbb{Z}\to\mathbb{Z}/9\mathbb{Z}$,

$$\pi(N)=\sum_{k=0}^{m}\pi(d_k)\,\pi(10)^k=\sum_{k=0}^{m}\bar d_k\cdot\bar 1^{\,k}=\overline{\textstyle\sum_k d_k},$$

because $10=9+1$, so $\pi(10)=\bar 1$. In other words,

$$N\equiv d_0+d_1+\cdots+d_m\pmod 9 .$$

The same goes modulo $3$, because $10\equiv 1\pmod 3$. This is why "a number is divisible by $3$ if its digit sum is".

Modulo $11$: $10=11-1$, so $\pi(10)=\overline{-1}$, and then

$$N\equiv\sum_{k=0}^{m}(-1)^k d_k = d_0-d_1+d_2-\cdots\pmod{11},$$

which is the alternating sum.

3.4 The kernel is $9\mathbb{Z}$: which errors go undetected

$$\ker\pi=\{a\in\mathbb{Z}:\ \pi(a)=\bar 0\}=9\mathbb{Z}.$$

Let the correct answer be $c$, the written answer $c'$, and the error $e=c'-c$. Then

$$\pi(c')=\pi(c)\iff \pi(e)=\bar 0\iff e\in\ker\pi=9\mathbb{Z}.$$

So an error goes undetected if and only if it falls in the kernel. This is the most basic property of a homomorphism: $\pi(x)=\pi(y)\iff x-y\in\ker\pi$. By the first isomorphism theorem, $\mathbb{Z}/\ker\pi\cong\mathbb{Z}/9\mathbb{Z}$, and differences in the kernel are completely invisible in the image.

Going through the table in 1.2:

• Single-digit errors: digit $k$ changes from $a$ to $b$, with error $e=(b-a)10^k$. Because $\gcd(10,9)=1$, $e\in 9\mathbb{Z}\iff 9\mid b-a\iff\{a,b\}=\{0,9\}$.
• Adjacent swaps: digits $k+1$ and $k$ are $a,b$. After swapping, the error is $$e=(b-a)10^{k+1}+(a-b)10^k=9\,(b-a)\,10^k\in 9\mathbb{Z},$$ so they are never caught.
• Modulo $11$: the same adjacent swap gives $e=9(b-a)10^k\equiv 9(b-a)(-1)^k\pmod{11}$. Because $11$ is prime, $9\not\equiv 0$, and $b-a\not\equiv 0$ when $0<|b-a|\le 9$, so $e\not\equiv 0$ and it is always caught.
• Swaps one position apart: $e=(b-a)(10^{k+2}-10^k)=99\,(b-a)\,10^k$, which lies in both $9\mathbb{Z}$ and $11\mathbb{Z}$, so neither method catches it.

3.5 The general framework for weighted check digits, and why primes matter

Every "weighted sum" check digit can be written as

$$\varphi(a_1,\dots,a_m)=\sum_{i=1}^{m} w_i\,a_i\ \in\ \mathbb{Z}/n\mathbb{Z},\qquad \text{valid number}\iff\varphi=\bar t .$$

$\varphi$ is a module homomorphism (linear map) from $(\mathbb{Z}/n\mathbb{Z})^m$ to $\mathbb{Z}/n\mathbb{Z}$, so the analysis is the same as in 3.4: an error vector $e$ goes undetected if and only if $e\in\ker\varphi$.

(1) Single-digit errors: digit $i$ changes from $a$ to $b$, and $\varphi$ changes by $w_i(b-a)$.

(2) Swapping digits $i,j$: if they were $a,b$, the change is

$$w_i(b-a)+w_j(a-b)=(w_i-w_j)(b-a).$$

Because digits satisfy $0\le a,b\le 9$, when $a\ne b$ we have $b-a\in\{\pm1,\dots,\pm9\}$.

Checking each in turn:

• ISBN-10 ($p=11$, $w_i=11-i$): $w_i\in\{1,\dots,10\}$ are all nonzero; for any $i\ne j$, $w_i-w_j=j-i\in\{\pm1,\dots,\pm 9\}$ is also nonzero. So single errors and swaps at any positions are caught. A check digit of $10$ must be written as X, the price of using the prime $11$ rather than $10$.
• Chinese ID MOD 11-2 ($p=11$, $w_i=2^{18-i}$): $2$ is invertible in $\mathbb{Z}/11\mathbb{Z}$, so every $w_i\ne 0$. The weight difference of adjacent digits is $$w_i-w_{i+1}=2^{k+1}-2^{k}=2^{k}\ne\bar 0,$$ so adjacent swaps are all caught. Moreover, $2$ is a primitive root modulo $11$, and $2^1,\dots,2^{10}$ run through exactly $\{\bar1,\dots,\overline{10}\}$, so any two digits whose distance isn't a multiple of $10$ have different weights, and their swaps are caught as well.
• IBAN MOD 97-10 ($p=97$, by decimal digit, $w=10^k$): $10^k$ is invertible; the adjacent difference $10^{k+1}-10^k=9\cdot 10^k$ is invertible. $10$ has order $96$ in $\mathbb{Z}/97\mathbb{Z}$, so the weights are all different over a very long stretch.

Counterexamples: when the modulus isn't prime, zero divisors cause misses

• EAN ($n=10$, weights $1,3$):
  • Single errors: $w\in\{1,3\}$ is invertible in $\mathbb{Z}/10\mathbb{Z}$ ($\gcd(3,10)=1$), so all are caught.
  • Adjacent swaps: the change is $(3-1)(b-a)=2(b-a)$. But $\bar 2$ is a zero divisor in $\mathbb{Z}/10\mathbb{Z}$: $\bar 2\cdot\bar 5=\bar 0$. So when $b-a=\pm 5$ the change is $\bar 0$, and it isn't caught. This is exactly why changing 40615 to 40165 in 2.2 still passes: $$(3-1)(1-6)=-10\equiv 0\pmod{10}.$$
• Casting out nines ($n=9$, all weights $1$): for adjacent swaps $w_i-w_j=0$, so no swap is ever caught.

3.6 Why Luhn misses only $09\leftrightarrow 90$

Luhn isn't a pure weighted sum. Let the "double and take digit sum" function be

$$\delta(x)=\begin{cases}2x, & 0\le x\le 4,\\ 2x-9, & 5\le x\le 9,\end{cases}$$

with this table of values:

(Note that $\delta(x)\equiv 2x\pmod 9$, because a digit sum doesn't change the remainder modulo $9$; 3.3 is at work again.)

Single errors: in an undoubled position, the change is $b-a\not\equiv 0\pmod{10}$; in a doubled position, the change is $\delta(b)-\delta(a)$. The table shows $\delta$ is a permutation (injective) of $\{0,\dots,9\}$, so $\delta(a)\ne\delta(b)$ when $a\ne b$, and both lie between $0$ and $9$, so their difference can't be a multiple of $10$. Therefore all single errors are caught.

Adjacent swaps: of two adjacent digits, exactly one is doubled. Say the doubled digit was $a$ and the plain one $b$; after swapping, the doubled digit is $b$ and the plain one $a$. The total changes by

$$\big(\delta(b)+a\big)-\big(\delta(a)+b\big)=f(b)-f(a),\qquad f(x):=\delta(x)-x .$$

Computing $f(x)\bmod 10$:

In $\mathbb{Z}/10\mathbb{Z}$, $f$ has only one "collision": $f(0)=f(9)=0$. So when $a\ne b$,

$$f(a)\equiv f(b)\pmod{10}\iff\{a,b\}=\{0,9\},$$

that is, Luhn misses only the adjacent swap $09\leftrightarrow 90$. Intuitively, $0$ doubled is still $0$, and $9$ doubled is $18\to 9$; both are fixed points of $\delta$, so the total is the same whichever digit is doubled.