When we type, write, or say long numbers like credit card numbers or serial numbers, it’s pretty common to make mistakes. In order to help catch these mistakes, redundancies are built into these numbers. It makes the numbers a little longer than they would otherwise be but helps alert us to problems like entering a wrong credit card number so you don’t have to learn about the mistake after your card is declined.

Check digits

Error detection methods can be simple or complicated depending on what sorts of issues you’re trying to avoid. Here are a couple simple check digit systems:

Version 1

Suppose you have a set of 9-digit numbers that you want to reinforce with some error detection redundancies. For each of these numbers, you can add up its digits. For example, with \(738024409\), adding the digits gives

\[ 7+3+8+0+2+4+4+0+9 = 37 \]

If we take the ones digit of the sum, we could tack that onto the end of our 9-digit number as a new tenth “check” digit. In our example, we would use \(738024409\underline{7}\) instead of \(738024409\).

While these new numbers are longer, their advantage is that if a single digit is entered incorrectly, we can tell. For example, if we were given the number \(6495493025\), we could add its first nine digits to get

\[ 6+4+9+5+4+9+3+0+2 = 42 \]

Since the last digit of \(42\) is not a \(5\), there is a mistake somewhere in \(6495493025\).

Version 2

We could instead make the tenth digit what it would need to be to make the sum of all ten digits a multiple of \(10\). In that case, \(738024409\) would become \(738024409\underline{3}\) because

\[ 7+3+8+0+2+4+4+0+9+\underline{3} = 40 \]

and \(649549302\) would become \(649549302\underline{8}\) because

\[ 6+4+9+5+4+9+3+0+2+\underline{8} = 50 \]

While only subtly different, this is really nice because each digit has equal weight in the sense that every digit is what you would add to the other nine to get a multiple of \(10\), so many check digit systems use this sort of trick.

Checking for transposition errors

The systems above are great for when a single digit is incorrect, but errors like accidentally transposing two digits (like when writing \(12\underline{43}5\) instead of \(12345\)) wouldn’t be detected. Those same numbers would all be added up in a different order to compare with the check digit, but addition is commutative, so the sum will be the same for any order. To also detect errors like these, we need to somehow treat neighboring digits differently.

If we alternate colors of the digits of a number like \(\color{red}{7}\color{blue}{3}\color{red}{8}\color{blue}{0}\color{red}{2}\color{blue}{4}\color{red}{4}\color{blue}{0}\color{red}{9}\), then instead of just summing the digits we could sum the blue ones and triple the red ones:

\[ \color{red}{(3 \cdot 7)}\color{black}{+}\color{blue}{3}\color{black}{+}\color{red}{(3 \cdot 8)}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{(3 \cdot 2)}\color{black}{+}\color{blue}{4}\color{black}{+}\color{red}{(3 \cdot 4)}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{(3 \cdot 9)} \color{black}{= 97} \]

We could then make our last check digit what we’d need to add to this sum to make it a multiple of \(10\) — in this case, \(3\).

The idea is that if two neighboring digits accidentally swapped, the one that gets tripled will swap, likely also changing the sum. I specifically chose to triple because \(3\) is relatively prime to \(10\), so no two different digits have the same ones-digit after being tripled.

\[ \begin{array}{|c|cccccccccc|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 3n & 0 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 & 27 \\ \hline \end{array} \]

In particular, this will continue to detect if a single digit has been misentered, since that will still throw off whether the sum is a multiple of \(10\).

While I was just trying to think of a cute example, it turns out this is exactly how Universal Product Code (UPC) check digits are generated! For example, a 12-pack of granola bars I enjoy has a 12-digit UPC \(016000264601\):

granola_heb.png

granola_upc.png

In our alternating color scheme where we triple the red digits before summing,

\[ \color{red}{(3 \cdot 0)}\color{black}{+}\color{blue}{1}\color{black}{+}\color{red}{(3 \cdot 6)}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{(3 \cdot 0)}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{(3 \cdot 2)}\color{black}{+}\color{blue}{6}\color{black}{+}\color{red}{(3 \cdot 4)}\color{black}{+}\color{blue}{6}\color{black}{+}\color{red}{(3 \cdot 0)}\color{black}{+}\color{blue}{1} \color{black}{= 50} \]

So that last \(1\) is exactly what was needed to make this sum a multiple of \(10\).

This check digit will catch a lot of transpositions of neighboring digits, but not all of them. It can’t tell if you swap \(0\) with \(5\), for example, since \(3 \cdot 0 + 5 = 5\) and \(3 \cdot 5 + 0 = 15\) have the same ones-digit. Similarly, it can’t tell if you swap \(1\) with \(6\), \(2\) with \(7\), \(3\) with \(8\), or \(4\) with \(9\).

The Luhn algorithm

Hans Peter Luhn came up with his own approach to this while he was working at IBM, which he published in 1960. Here’s how his version works:

Start with a number you wish to add a check digit to, say \(12345678\)
Color the digits alternating red-blue starting with red from the right side: \(\color{blue}{1}\color{red}{2}\color{blue}{3}\color{red}{4}\color{blue}{5}\color{red}{6}\color{blue}{7}\color{red}{8}\)
Take each red digit, double it, and then replace the original red digit with (possibly both) digits of this new number: \(\color{blue}{1}\color{red}{4}\color{blue}{3}\color{red}{8}\color{blue}{5}\color{red}{12}\color{blue}{7}\color{red}{16}\)
Add up the digits of this new number:

\[ \color{blue}{1} \color{black}{+} \color{red}{4} \color{black}{+} \color{blue}{3}\color{black}{+}\color{red}{8}\color{black}{+}\color{blue}{5}\color{black}{+}\color{red}{(1+2)}\color{black}{+}\color{blue}{7}\color{black}{+}\color{red}{(1+6)} \color{black}{= 38} \]

The check digit will be what must be added to this to get a multiple of \(10\). In this case, it’s a \(2\)
Append the check digit to the end of the number: \(123456782\)

The UPC folks and I both chose tripling to avoid an issue with doubling. The only ones-digits you can get from doubling are \(0\), \(2\), \(4\), \(6\), and \(8\):

\[ \begin{array}{|c|cccccccccc|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 2n & 0 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 \\ \hline \end{array} \]

In particular, if you mistype \(0\) as \(5\), \(1\) as \(6\), or so on, you can’t detect that for any of the doubled digits. Luhn noticed that if you add the digits when the result of doubling has two digits, you fix this problem:

\[ \begin{array}{|c|cccccccccc|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 2n & 0 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 \\ \hline \textrm{digit sum of } 2n & 0 & 2 & 4 & 6 & 8 & 1 & 3 & 5 & 7 & 9 \\ \hline \end{array} \]

Now we’re back to having different digits contributing differently to the sum, so an any single-digit entry error will be detected by the check digit! While the rest of Luhn’s approach is pretty much exactly like our UPC check digit system, it turns out it’s actually better at detecting common transposition errors. The only neighbor swap it can’t detect is when a \(0\) swaps with a \(9\).

Luhn’s algorithm is the one used to create and check credit card numbers. I’ve been advised against using my own card, so here’s a fake example credit card used by Visa on its website:

*A fake example credit card. (Source:* *visa.com*)

Let’s run Luhn’s algorithm on it.

First, chop off the check digit: \(400012345678901\)
Alternate digit color red-blue starting with red from the right: \(\color{red}{4}\color{blue}{0}\color{red}{0}\color{blue}{0}\color{red}{1}\color{blue}{2}\color{red}{3}\color{blue}{4}\color{red}{5}\color{blue}{6}\color{red}{7}\color{blue}{8}\color{red}{9}\color{blue}{0}\color{red}{1}\)
Replace blue digits with their doubles: \(\color{red}{8}\color{blue}{0}\color{red}{0}\color{blue}{0}\color{red}{2}\color{blue}{2}\color{red}{6}\color{blue}{4}\color{red}{10}\color{blue}{6}\color{red}{14}\color{blue}{8}\color{red}{18}\color{blue}{0}\color{red}{2}\)
Add the digits of this new number: \(\color{red}{8}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{0}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{2}\color{black}{+}\color{blue}{2}\color{black}{+}\color{red}{6}\color{black}{+}\color{blue}{4}\color{black}{+}\color{red}{(1+0)}\color{black}{+}\color{blue}{6}\color{black}{+}\color{red}{(1+4)}\color{black}{+}\color{blue}{8}\color{black}{+}\color{red}{(1+8)}\color{black}{+}\color{blue}{0}\color{black}{+}\color{red}{2} = 53\)
The single digit we’d need to add to \(53\) to get a multiple of \(10\) is \(7\).

Not every 16-digit number that passes Luhn’s test will necessarily correspond to a real credit card, but any number that doesn’t pass this test can’t be a real credit card number. Since the check digit on the card is a \(0\) when we’ve just seen that it should be \(7\), we know this can’t be a real credit card!

What other types of errors might we want to detect? How could you build numbers that give us a way to check for those errors?

Math in… Error Detection