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.

Advertisements

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

%d bloggers like this: