## Number Systems: Problem Sheet 9

Recall that if $n,n' \in \mathbb{Z}$ and $m \in \mathbb{N}$ then we say that $n$ is congruent to $n'$ modulo $m$, if $n-n'$ is divisible by $m$. We write this as $n \equiv n'$ modulo $m$.

Note that this use of the $\equiv$ sign is something new. The notation is maybe a little strange: in this context the “modulo $m$” goes with $\equiv$, and one should not appear without the other. An alternative notation, which you might prefer, is $n \equiv_m n'$.

(You might have used $\equiv$ before to write identities, for example $\sin^2 x \equiv 1-\cos^2 x$. An alternative (better?) way to write this would be: $\sin^2x = 1-\cos^2x$ for all $x \in \mathbb{R}$.)

Alternative definition. An equivalent definition is that $n \equiv n'$ mod $m$ if $n$ and $n'$ have the same remainder on division by $m$. This is the definition used in How to think like a mathematician. The equivalence of these definitions is proved in Theorem 29.6. For example, $17 \equiv 1$ mod $8$, because $17$ and $1$ both have remainder $1$ on division by $8$.

Question 3. This asks you to find $2^n$ mod $11$ for $n = 0,1,\ldots, 10$. For example, since $2^6 = 64$, and $64 = 5 \times 11 + 9$, the remainder when $64$ is divided by $11$ is $9$. Hence $2^6 \equiv 9$ mod $11$. There is a shortcut using Lemma 8.10 from lectures: if $2^n \equiv r$ mod $11$ then $2^{n+1} \equiv 2r$ mod $11$. So there is no need to work with $2^7 = 128$ to find $2^7$ mod $11$. We can just take $2^6 \equiv 9$ mod $11$ and double $9$, to get

$2^7 \equiv 2 \times 9 = 18 = (11+7) \equiv 7 \ \text{mod } 11$

Question 5. An ISBN (or International Standard Book Number) is, for the purposes of this question, a sequence $u_1u_2\ldots,u_{10}$ where each $u_i \in \{0,1,\ldots,9,\mathrm{X}\}$. Here the Roman numeral X is used to stand for 10. The check sum of this ISBN is

$\sum_{j=1}^{10} (11-j)u_j = (11-1)u_1 + (11-2)u_2 + \cdots + (11-10)u_{10}.$

The check sum of an ISBN is always congruent to $0$ modulo $11$.

In the first part of (a) you are asked if 0-521-71978-X is an ISBN. (The dashes are put in for readability: they are not formally part of the code). The check sum is

$10 \times 0 + 9 \times 5 + 8 \times 2 + \cdots + 2 \times 8 + 1 \times 10 = 198.$

Note that the final 10 comes from the final X in the ISBN. Since $198 = 18 \times 11$, we have $198 \equiv 0$ mod $11$. So this is an ISBN. In fact it is the ISBN of How to think like a mathematician.

The second sequence is obtained from this ISBN by swapping the 7 and 8. You could compute its check sum in the same way, but it is much more illuminating to think about the difference between the two check sums. You should find that this is $1$, and so the check sum for 0-521-71987-X is $199 \equiv 1$ mod $11$. So the new sequence is not an ISBN and the error is detected.