##
I used to be rated X *October 28, 2007*

*Posted by Lee in Statistics.*

Tags: ISBN, modular arithmetic

trackback

Tags: ISBN, modular arithmetic

trackback

Get your mind out of the gutter: I’m talking about International Standard Book Numbers (ISBNs). The third edition of my first book had the ISBN number 0-534-997949-X. Now, if you’re the curious and detail-oriented type, you’ll notice that one of these digits is not like the others. Specifically, that last digit: X. Why is there an X in a number? Further: If I told you that 9+5 = 2, would you believe that (a)it’s true and (b)that it’s related to ISBNs?

The second question is actually easier to explain than the first. In fact, given the context, you’d do get the exact same answer. Suppose it’s 9:00, and you add 5 hours to that. What time is it? 2:00. So 9+5=2.

This “clock arithmetic” actually has some deep mathematical applications. Simple arithmetic tells us that 9+5 = 14. Clock arithmetic tells us that 9+5 = 2. Therefore, when 12 is used as the “base”, 2 and 14 have something in common.

The thing they have in common is that they both have the same remainder when divided by 12: 2/12 = 0 remainder 2, and 14/12 is 1 remainder 2. Similarly, 26 has the same property: 26/12 has a remainder 2. So on for 38, 50, 62, 74, and so on. In jargon, all these numbers “mod 12″ are equivalent.

See if you can apply this. What numbers are equal to 4 mod 12? Well, 4, then 16, then 28, 40, 52, and so on.

What numbers are equal to zero mod 12? 0, 12, 24, 48, 60, and so on.

Each of these lists of numbers is called an equivalence class. In mod 12, the equivalence class of 2 is {2, 14, 26, 38, 50, 62…}. The equivalence class of 4 is {4, 16, 28, 40, 52, …} The equivalence class of 0 is {0, 12, 24, 48, 60, …}.

The final question is: How many equivalence classes are there when you’re thinking in mod 12? Of course, there are 12: Once class each for the numbers 0, 1, 2, 3, …, 10, 11. Once you hit 12, you’re back in the 0 class. 13 is in the 1 class, 14 in the 2, ad infinitum.

There’s nothing too special about the number 12. It’s pretty easy to imagine a clock having any number of hours on it, 12 is simply a relic of our Babylonian past (but that’s another post). The link to ISBNs it to imagine a clock with 11 hours, or, in jargon again, to work with numbers mod 11.

How many equivalence classes are there in mod 11? Like we saw above, there are 11: all the numbers that have 0 remainder when divided by 11, all those that have 1 remainder when divided by 11, … those that have 10 remainder when divided by 11. So every number imaginable can be put into one of the mod 11 equivalence classes 0, 1, 2, …, 10.

Now, suppose you were creating a system to designate all these eleven equivalence classes. You have to come up with a single unique symbol for each one of the 10 equivalence classes. Can you do it? Turns out you don’t have to do any real work. let 0 represent the 0 equivalence class, let 1 represent the 1 class, let 2 represent the 2 class, all the way up. That is, until you get to the tenth one. Out number system uses two digits (a 1 and a 0) to represent this number. So we need a new single unique symbol for this one. If you think back to the subject of this post (ISBNs) you’ll know what publishers came up with: X.

—

ISBNs are an example of a self-correcting code. If you’ve ever had a scanner at the grocery store beep at you because it mis-read the number, you’ll have come across self-correcting codes before. The IPC (International Product Code) on grocery storre items is another example of a self-correcting code.

In these codes, the last digit is calculated from the rest of the code on the package. After scanning, if the numbers in the code don’t match the last digit, the computer knows that something went wrong, and it should ask you to rescan.

In the case of ISBNs, the special method for calculating the last digit (called, creatively, the check digit) uses the clock arithmetic we talked about above. It sounds more complicated than it is, so look at the example before deciding it’s impossible.

The rule states to multiply each of the numbers in the 10-digit ISBN by 10, 9, 8, 7, … down to 1, negate it, and find its mod 11 equivalence class. That’s the check digit.

So, for my first book, with ISBN 0-534-99749-X:

0(0)+9(5)+8(3)+7(4)+6(9)+5(9)+4(7)+3(4)+2(9)

=0 + 45 + 24 + 28 + 54 + 45 + 28 + 12 + 18

= 254

Now find the equivalence class (= remainder) mod 11 of the negative:

-254 / 11 = -24 remainder 1o (Check: -24*11 = -264 + 10=-266. Done.)

Since the remainder is 10, we are in that special equivalence class X. So the check digit is X, as we already knew.

Try again. This time, we’ll use the ISBN from the screenplay for American Beauty. Find the correct check digit for its ISBN:1-55704-423-_

10(1)+9(5)+8(5)+7(7)+6(0)+5(4)+4(4)+3(2)+2(3) =

= 10 + 45 + 40 + 49 + 0 + 20 + 16 + 6 + 6=192-192/11

= -18 remainder 6 (check: -18*11 = -198 + 6 = -192. Done) So 6 is the check check digit, which you can verify by clicking the above link.

—

The rest of the story:

Since January 1, 2007, ISBN numbers have become 13 digits long, rather than ten as above. And, the scheme is mod 10 rather than mod 11. To adjust the number of an older book, add 978 to the old ISBN. Alternate numbers are multiplied by either a 1 or a 3, starting from the left to generate a new check digit.

So the fourth edition of my book will have a 13-digit ISBN. 978-1-5999-4525-5.

1(9)+3(7)+1(8)+3(1)+1(5)+3(9)+1(9)+3(9)+1(4)+3(5)+1(2)+3(5) = 145

145 mod 10 = 5, the last digit.

So much for my X.

## Comments»

No comments yet — be the first.