IAAWA Check digits

Section 3.2 Check digits

Every published book can be identified by its International Standard Book Number. Before 2007, the ISBN was a 10-digit number, and we will call this variant ISBN-10. If \(d_1 d_2 d_3 \cdots d_{10}\) are the digits of a valid ISBN-10, then they will always satisfy the modular equation:

\begin{equation*} 10d_1 + 9d_2 + 8 d_3 + \cdots + d_{10} \equiv 0 \pmod{11} \end{equation*}

Example 3.9.

The ISBN-10 for Abstract Algebra: Theory and Applications, on which this text is based is 1944325069. We can check that this is a valid ISBN-10 because

\begin{align*} 10 \cdot 1 + 9 \cdot 9 + 8 \cdot 4 + 7 \cdot 4 + 6 \cdot 3 + 5 \cdot 2 + 4 \cdot 5 + \amp 3 \cdot 0 + 2 \cdot 6 + 1 \cdot 9 \\ \amp= 220 \equiv 0 \pmod{11} \end{align*}

The way that ISBN-10 numbers are assigned is that the first 9 digits are chosen and then the last one is solving for the last digit

\begin{equation*} d_{10} = -(10 d_1 + 9 d_2 + 8d_3 + \cdots + 2 d_{9}) \pmod{11} \end{equation*}

If the formula yields \(d_{10}=10\text{,}\) then it can’t be represented by a single digit, and so instead the last digit is written as X.

Proposition 3.10.

If \(d_1 d_2 \cdots d_{10}\) is a valid ISBN-10 code, then changing any single digit makes the code invalid, so \(d_1 \cdots d_{i-1} d_i' d_{i+1} \cdots d_{10}\) is not valid if \(d_i \neq d_i'\text{.}\) Also, transposing any pair of digits will make the code invalid, meaning that if \(i \lt j\) and \(d_i \neq d_j\text{,}\) then

\begin{equation*} d_1 \cdots d_{i-1} d_j d_{i+1} \cdots d_{j-1} d_i d_j \cdots d_n \end{equation*}

is not a valid ISBN-10.

Proof.

We saw that we can always solve for \(d_{10}\text{,}\) but by using modular inverses, we can also do the same for other digits. First, we can rearrange the modular equation to get:

\begin{equation*} -(11-i) d_i \equiv 10 d_1 + \cdots + (11-i+1) d_{i-1} + (11-i-1)d_{i+1} + \cdots + d_{10} \pmod{11} \end{equation*}

By distributing, we can simplify \(-(11-i)\) to \(i-11\text{,}\) which is equivalent to \(i\text{.}\) Since \(1 \leq i \leq 10\text{,}\) then \(i\) is relatively prime to \(11\text{.}\) By Proposition 3.4(6), \(i\) has a multiplicative inverse \(b\text{.}\) Therefore,

\begin{equation*} d_i \equiv b (10 d_1 + \cdots + (11-i+1) d_{i-1} + (11-i-1) d_{i+1} + \cdots + d_{10} \pmod{11}, \end{equation*}

so \(d_i\) is determined by the other digits, and any other \(d_i'\) will not be a valid ISBN.

Now suppose that \(i \lt j\) and \(d_i \neq d_j\text{.}\) For the purpose of contradiction, we assume that \(d_1 \cdots d_n\) and the transposition \(d_1 \cdots d_j \cdots d_i \cdots d_n\) are both valid ISBN-10s. Therefore, we have the modular equations:

\begin{align*} 10 d_1 + \cdots + (11-i) d_i + \cdots + (11-j) d_j + \cdots + d_1 &\equiv 0 \pmod{11}\\ 10 d_1 + \cdots + (11-i) d_j + \cdots + (11-j) d_i + \cdots + d_1 &\equiv 0 \pmod{11}\text{.} \end{align*}

By subtracting the second equation from the first, we get:

\begin{align*} (11-i) d_i + (11-j) d_j - (11-i) d_j - (11-j) d_i &\equiv 0 \pmod{11}\\ (11-i) (d_i - d_j) + (11-j)(d_j - d_i) &\equiv 0 \pmod{11}\\ (11-i - 11 + j)(d_i - d_j) & \equiv 0 \pmod{11}\\ (j-i)(d_i - d_j) &\equiv 0 \pmod{11}\text{.} \end{align*}

Because \(1 \leq i \lt j \leq 10\text{,}\) then \(1 \leq j-i \leq 9\text{,}\) so \(j-i\) is relatively prime to \(11\text{.}\) Thus, we can multiply by the multiplicative inverse of \(j-i\) to get \(d_i - d_j \equiv 0 \pmod{11}\text{.}\) Both \(d_i\) and \(d_j\) are at most \(10\text{,}\) so the only way for \(d_i - d_j\) to be divisible by \(11\) is if \(d_i = d_j\text{,}\) a contradiction.