Recall that if and then we say that is congruent to modulo , if is divisible by . We write this as modulo .

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

(You might have used before to write identities, for example . An alternative (better?) way to write this would be: for all .)

Alternative definition. An equivalent definition is that mod if and have the same remainder on division by . 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, mod , because and both have remainder on division by .

Question 3. This asks you to find mod for . For example, since , and , the remainder when is divided by is . Hence mod . There is a shortcut using Lemma 8.10 from lectures: if mod then mod . So there is no need to work with to find mod . We can just take mod and double , to get

Question 5. An ISBN (or International Standard Book Number) is, for the purposes of this question, a sequence where each . Here the Roman numeral X is used to stand for 10. The check sum of this ISBN is

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

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

Note that the final 10 comes from the final X in the ISBN. Since , we have mod . 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 , and so the check sum for 0-521-71987-X is mod . So the new sequence is not an ISBN and the error is detected.

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Monday, December 2nd, 2013 at 12:42 pm and is filed under Number Systems. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.