Why a typo in your card number gets caught
Tonight's idea
The last digit of an ISBN, a barcode or a card number carries no information. It is a check digit, computed from the others, so a scanner or website can tell at once whether the number is damaged.
The simplest check makes the digits add to a multiple of 10. That catches one wrong digit, but the commonest slip is swapping two neighbours, 61 for 16, and a plain sum cannot see that. The fix is to weight each position differently.
Ten-digit ISBNs (books printed before 2007) weight the positions 10, 9, 8, …, 1 from the left and demand a multiple of 11:
\(10d_1 + 9d_2 + 8d_3 + \cdots + 2d_9 + 1d_{10}\) is a multiple of 11. Here \(d_1, \dots, d_{10}\) are the digits.
Why 11? Suppose one digit is wrong by \(e\) (1 to 9) at a position of weight \(i\) (1 to 10). The sum shifts by \(i \times e\). Since 11 is prime and divides neither \(i\) nor \(e\), it cannot divide \(i \times e\) (clock arithmetic), so the total stops being a multiple of 11 and the error is caught. Every single-digit error, every time. The price: the check digit is sometimes 10, written X.
Watch one: the Luhn check on a card number
Credit cards use the Luhn algorithm, which works modulo 10 so the check is always a digit. Starting with the digit just left of the check digit and moving left, double every second digit; if doubling gives two digits, subtract 9. Add everything up. The number is valid when the total ends in 0. Take the test number 4539 1488 0343 6467 (not anyone's card):
Type the last two digits the wrong way round, 6476, and the bottom row ends 5, 6 instead of 3, 7: total 81. Rejected before the shop ever contacts the bank.
Your turn
- Find the check digit of the ISBN 1-86197-271-?. (Weights 10 down to 2 for the nine known digits; choose the last digit so the total is a multiple of 11.)
- Run the Luhn check on 4539 1488 0433 6467, which is the test number with one pair of neighbours swapped. Is it caught?
- The ISBN 0-306-40615-2 is valid: its weighted sum is 132. (a) The 4 is mistyped as 7. What is the new sum, and is the slip caught? (b) The neighbours 6 and 1 are swapped to give 0-306-40165-2. Find the new sum. Then explain why swapping any two neighbouring digits \(a\) and \(b\) in an ISBN is always caught. (Hint: their weights differ by 1.)
- The Luhn check misses one kind of neighbour swap. (a) Show that a doubled 0 next to an undoubled 9 contributes the same total as a doubled 9 next to an undoubled 0. (b) Write \(f(a)\) for "double \(a\), subtract 9 if needed". Swapping neighbours \(a, b\) changes the total by \(f(a) + b - f(b) - a\). Show this is a multiple of 10 only for \(\{a, b\} = \{0, 9\}\).
Stretch: barcodes
The 13-digit barcode on groceries uses weights 1, 3, 1, 3, … and demands a total that is a multiple of 10. (a) Explain why one wrong digit is always caught. (b) Which pairs of neighbouring digits can be swapped without the check noticing? Find all of them.
Answers
- \(10 \cdot 1 + 9 \cdot 8 + 8 \cdot 6 + 7 \cdot 1 + 6 \cdot 9 + 5 \cdot 7 + 4 \cdot 2 + 3 \cdot 7 + 2 \cdot 1 = 257\). The next multiple of 11 is 264, so the check digit is 7.
- Only the third group changes: the digits 0, 4, 3, 3 give \(0, 4, 6, 3\) (the 4 is now in an undoubled place and the 3 in a doubled one) instead of \(0, 3, 8, 3\). The total drops from 80 to 79. Caught.
- (a) The 4 had weight 6; replacing it by 7 adds \(6 \times 3 = 18\), giving 150, which is \(13 \times 11 + 7\). Caught. (b) The 6 (weight 4) and 1 (weight 3) become 1 and 6: the sum changes by \(4 \cdot 1 + 3 \cdot 6 - 4 \cdot 6 - 3 \cdot 1 = -5\), giving 127, not a multiple of 11. In general, swapping neighbours \(a, b\) with weights \(w, w - 1\) changes the sum by \(wb + (w-1)a - wa - (w-1)b = b - a\), which is between \(-9\) and 9 and not zero. It cannot be a multiple of 11.
- (a) \(f(0) + 9 = 0 + 9 = 9\) and \(f(9) + 0 = 9 + 0 = 9\). Same total, so 09 and 90 look alike. (b) \(f(a) - a = a\) when \(a \le 4\) and \(f(a) - a = a - 9\) when \(a \ge 5\). The change is \((f(a) - a) - (f(b) - b)\). If both digits are at most 4, or both at least 5, this is \(a - b\), which is between \(-4\) and 4, so a multiple of 10 only when \(a = b\). If \(a \ge 5\) and \(b \le 4\), it is \(a - 9 - b\), which lies between \(-8\) and 0 and equals 0 only when \(a = 9\), \(b = 0\). (The case \(a \le 4\), \(b \ge 5\) is the same swap read backwards.) The 0–9 swap is the one blind spot.
Stretch. (a) A wrong digit shifts the total by \(e\) or \(3e\) with \(e\) from 1 to 9. Neither is a multiple of 10: \(3e\) would need \(e\) itself to be a multiple of 10. (b) Swapping neighbours \(a, b\) changes the total from \(a + 3b\) to \(3a + b\), a shift of \(2(a - b)\). That is a multiple of 10 exactly when \(a - b = \pm 5\): the pairs 05, 16, 27, 38 and 49, in either order. ISBN's prime 11 has no such blind spot, but it needs the awkward X.