Mathematics in action: check digits and ISBNs

International Standard Book Numbers or ISBNs (the older, 10-digit kind, not the newer 13-digit kind starting with 978) have an interesting way of detecting errors made in writing down the numbers. The number at the top of the image above is an example of what I mean. The process works like this:

  1. Circle the right-hand digit. This is the check digit. If it’s an “X,” that means 10. In the image above, the check digit (5) is circled in red.
  2. Copy the other 9 digits, and write 10, 9, 8, 7, 6, 5, 4, 3, 2 underneath them.
  3. Multiply vertical pairs of numbers, and add up the products. Call this S. For the example above, S = 0 + 81 + 24 + 42 + 18 + 40 + 20 + 12 + 0 = 237.
  4. Divide by 11, and call the remainder R. For the example above, R = 6.
  5. The check digit should be 0 if R = 0, and 11 − R otherwise. If not, something is wrong. For the example above, the check digit is 11 − 6 = 5 (for students familiar with modular arithmetic, we can express this more simply: the check digit should be −S mod 11).

This scheme will detect any copying error where a single digit gets changed. Imagine that one of the digits is A (ranging from 0 to 9), in the position where it gets multiplied by N (ranging from 10 to 2), and A gets replaced by a different digit B (ranging from 0 to 9). The sum S will increase by (B − A)N, which cannot be a multiple of 11. Therefore the remainder R will change, and the check digit calculated in step 5 will no longer match the circled one.

The ISBN system also spots digits being swapped. Imagine that one of the digits is A (ranging from 0 to 9), in the position where it gets multiplied by N (ranging from 10 to 2). Another digit is B (ranging from 0 to 9, with B ≠ A), in the position where it gets multiplied by M (ranging from 10 to 2, with M ≠ N). If the digits A and B are swapped, by a similar argument to the one above, the check digit calculated in step 5 will no longer match the circled one.

A number of similar schemes exist, since the problem of people writing down numbers incorrectly is widespread, and detecting such errors is often worthwhile. Australian Medicare cards, like the one above, operate as follows:

  1. Ignore the right-hand digit, which is a sequence number. Circle the digit second from the right. This is the check digit. In the image above, the check digit (8) is circled in red.
  2. Copy the other 8 digits, and write 1, 3, 7, 9, 1, 3, 7, 9 underneath them.
  3. Multiply vertical pairs of numbers, and add up the products. Call this S. For the example above, S = 1 + 6 + 21 + 36 + 5 + 18 + 49 + 72 = 208.
  4. Divide by 10, and call the remainder R. For the example above, R = 8.
  5. The check digit should R. For the example above, the check digit is 8.

This scheme will also detect any copying error where a single digit gets changed. Imagine that one of the digits is A (ranging from 0 to 9), in the position where it gets multiplied by N (1, 3, 7, or 9), and A gets replaced by a different digit B (ranging from 0 to 9). The sum S will increase by (B − A)N, which cannot be a multiple of 10 (this is why 5 is excluded as one of the multiplying numbers). Therefore the remainder R will change, and the check digit calculated in step 5 will no longer match the circled one.

However, the Australian Medicare Number scheme only detects some digit swaps. Even if we only worry about swapping adjacent digits, it does not catch all such errors. For example, 127456786 and 172456786 are both valid. If you imagine that one of the digits is A (in the position where it gets multiplied by N) and the adjacent digit is B (in the position where it gets multiplied by M), you can see that sometimes the change in S from a swap will be a multiple of 10, leaving the check digit unchanged.

Advertisements

One thought on “Mathematics in action: check digits and ISBNs

  1. Pingback: List processing in NetLogo: some more examples | Scientific Gems

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s