Ian Stewart Page 6

  3 + 3 = 6, subtract 4 (the modulus) to get 2

  3 × 3 = 9, subtract 8 (twice the modulus) to get 1.

  We can write down addition and multiplication tables:

  Here the boldface numbers show which numbers are being operated on, and the number in the corresponding row and column is the result. For example, to find 3 + 2 look in row 3, column 2 of the table with a + in the top left-hand corner. The result is 1, so 3 + 2 = 1.

  Well, you may not approve of arithmetic in which 3 + 2 = 1, but it turns out to be vital to any problem in which what really matters is the remainder after dividing by 4. For instance, if you turn some object through four right angles it ends up exactly where it started. So a turn of three right angles followed by two right angles has the same affect as a turn through one right angle. (Yes, that’s also five right angles, but only 0, 1, 2, 3 right angles are needed to cover all possibilities, so it often makes sense to stay in that range.) So

  3 right angles + 2 right angles = 1 right angle

  and 3 + 2 = 1 isn’t so silly in this context. Neither is 2 + 2 = 0, which is how that sum pans out. Rotate through two right angles, and another two right angles, and you get right back where you began - a rotation through zero right angles.

  Two right angles plus two right angles equals zero right angles.

  The fun comes when you discover that you can use any positive whole number as the modulus - not just 4. The same ideas still work, and they’re now sufficiently general to be useful. Any process that repeats the same behaviour over and over again, for instance, may be ripe for analysis using this kind of arithmetic.

  When the modulus is 12, we get what is often called clock arithmetic, because on a conventional clock the hour hand gets back to the same position after 12 hours have passed, so multiples of 12 have the same effect as zero.

  These funny variants on arithmetic turn up whenever things fit together as part of some cycle that eats its own tail and starts again. It turns out that they obey all of the standard laws of algebra, such as

  a + b = b + a, ab = ba, a(b + c) = ab + ac

  and so on. There are a few oddities, though, especially when it comes to division. For example, when working to the modulus 4, the fraction makes no sense. If it did make sense, it would be whichever number, multiplied by 2, gives 1. But the only multiples of 2 are 0 and 2 - the number 1 never appears.

  It can be proved that division does make sense whenever the modulus is prime, though you still can’t divide by 0. For instance, if the modulus is 5, then the two tables above become

  Every number appears in every row of the multiplication table, except row 0, and we can now say things like

  because

  2×4 = 3

  Again, the usual rules for division also work in these cases.

  When there is any danger of confusion, mathematicians write these equations like this:

  2 × 4 ≡ 3 (mod 5)

  with a special symbol ≡ replacing the equals sign, and a reminder of which modulus is involved, to make it clear that they don’t really think that 2×4 = 3. But often they don’t bother.

  Secret Codes That Can Be Made Public

  Arithmetic to a modulus is the key (no pun intended) to a remarkable development in cryptography: the public key cryptosystem. All codes rely on secret keys, and the biggest danger is that an eavesdropper finds out what the key is. If the enemy gets hold of a copy of your one-time pad, perhaps through the actions of a spy, you’re in deep trouble.

  Or maybe not. The tacit assumption here is that, once someone knows the key, they can easily decode the message. After all, that’s what the intended recipient has to do, so it’s silly to make it hard. But in 1977 Ron Rivest, Adi Shamir and Leonard Adleman discovered that matters aren’t quite so straightforward. In fact, it is possible to make public the key for putting a message into code, without anyone being able to deduce the inverse procedure of decoding the message. However, the legitimate recipient can decode the message using a different, related key - which is kept secret.

  Methods like this rely on a curious mathematical fact: reversing a calculation, working back from the answer to the question, can sometimes be much harder than doing the calculation itself - even when the process is in principle reversible.13 If so, knowing the procedure concerned does not make it possible to work out how to undo it. But this fact alone is no use unless there is some secret short cut, so that the intended recipient can undo the encoding procedure easily. And it is here that arithmetic to a modulus, Gauss’s bizarre invention in which 2 + 2 might be 0, comes into its own.

  The RSA cryptosystem, named after the initials of its aforementioned inventors, is based on a theorem proved by Euler, generalising a simpler one discovered and proved by Pierre de Fermat. The simpler version is called Fermat’s Little Theorem, to distinguish it from his Last (or ‘Great’) Theorem (Cabinet, page 50). It states that if you are working to a prime modulus p, then ap-1 ≡ 1 for any number a. For example, with 5 as the modulus, we should find that 14 ≡ 1, 24 ≡ 1, 34 ≡ 1, 44 ≡ 1. And they are. For instance,

  34 ≡ 3 × 3 × 3 × 3 ≡ 81 ≡ 1 (mod 5)

  because 81 - 1 = 80, which is divisible by 5. The same sort of thing works for the other numbers.14

  To apply RSA encryption, you first represent messages by numbers. For example, every block of 100 letters, spaces and other characters could be represented as a 200-digit number, where each successive pair of digits encodes characters according to the rule A = 01, B = 02, . . . , Z = 26, [space] = 27, ? = 28, and so on. Then a message breaks up into a series of 100-digit numbers. Let N be one of those numbers. Our first task is to put N into code, and we do that using a mathematical recipe in modular arithmetic.

  I’ll start with an example, using numbers much smaller than those used in practice.

  Alice uses two special numbers: 77 and 13, which can be made public. Suppose that her message is N = 20. Then she calculates 2013 (mod 77), which is 69, and sends that to Bob.

  Bob knows the secret number 37, which reverses what Alice does with 13. He decodes Alice’s message by raising it to that power (mod 77):

  6937≡ 20 (mod 77)

  This works for any message that Alice might send, because

  (N13)37 ≡ N (mod 77)

  Where do these numbers come from?

  Alice’s choice of 77 is the product of two primes, 7×11. Euler’s theorem applies to the number (7 - 1) × (11 - 1), which is 60. It tells us that there is some number d such that 13d ≡ 1 (mod 60), and then (N13)d ≡ N (mod 77) for any message N. As Bob - and only Bob - knows, d = 37.

  To make this method practical, we replace 7 and 11 by much larger primes - typically with 100 digits or thereabouts (see note on page 288). The encoding key (here 13) and decoding key (here 37) can be calculated from those primes. Only the encoding key and the product of the two primes, a 200-digit number, need be made public. Only Bob need know the decoding key.

  This involves finding really big primes, which turns out to be easier than we might expect: there are efficient ways to test whether a number is prime without looking for factors. And, of course, you have to use a computer to do the sums. Note the catflap effect: Alice doesn’t need to know how to decode messages, only how to encode them. Mathematicians generally think, but can’t yet prove, that working out the prime factors of a really big number is extremely hard - so hard that in practice it can’t be done, no matter how big and fast your computer might be. Finding big primes is much easier, and so is multiplying them together.

  Of course, in my example, with impractically small numbers, finding the decoding key 37 is easy. Alice could work it out, and so could any eavesdropper. But with 100-digit primes, say, calculating the decoding key seems to be impossible if all you know is the product of the two primes. On the other hand, if you do know the primes, then it is relatively straightforward to find the decoding key. That’s why it’s possible to set up the system to begin with.

  Systems like RSA are very suitable for the inte
rnet, where every user has to ‘know’ how to send an encrypted message (such as a credit card number). That is, the method for encrypting this message has to be stored on their computer. So a skilled programmer could find it. But only the bank needs to know the decryption key. So until criminals discover efficient ways to factorise big numbers into primes, your money is safe. Assuming it’s safe in the hands of the banks, which has suddenly become questionable.

  In practical applications, some care has to be taken and the method isn’t quite this simple. See, for example: en.wikipedia.org/wiki/RSA

  It is also worth remarking that, in practice, RSA is mainly used for sending encrypted versions of keys to other, simpler cryptosystems, which can then be used to send messages, rather than using RSA for the messages themselves. RSA involves a bit too much computational time to be used routinely for messages.

  There is a curious historical postscript to this story. In 1973, the same method was invented by Clifford Cocks, a mathematician working for British Intelligence, but it was considered impractical at the time. Because his work was classified Top Secret, no one knew about his anticipation of the RSA system until 1997.

  Calendar Magic

  ‘My beautiful assistant,’ stated the Great Whodunni, ‘will now hand me a perfectly ordinary calendar.’

  Grumpelina smiled sweetly and did as instructed. It was indeed an ordinary calendar, with seven columns per month, headed by the days Sunday-Saturday, and the numbers of the days written in order.

  Whodunni then called for a volunteer from the audience, while Grumpelina blindfolded him (Whodunni, that is).

  ‘I want you to choose any month from the calendar, and then draw a 3×3 square round nine dates. Don’t include any blank spaces. I will then ask you to tell me the smallest number from those dates, and I will instantly tell you what the nine numbers add up to.’

  The volunteer did so, and, as it happened, he chose a square of dates for which the smallest number was 11. As soon as he told the magician this number, Whodunni immediately replied ‘171’.

  Whodunni’s method works whichever 3×3 square is chosen. How does he do it?

  Answer on page 289

  The volunteer’s choice.

  Mathematical Cats

  Isaac Newton, it is said,15 had a cat. He cut a hole in the bottom of his study door so that puss could get in and out. So we must add to Newton’s achievements the invention of the catflap, except that his version lacked the flap. Anyway, the cat had kittens. So Newton cut a small hole in the door next to the bigger one.

  I don’t know whether Lewis Carroll - pen-name of the mathematician Charles Lutwidge Dodgson - had a cat, but he created one of the most memorable fictional cats: the Cheshire Cat, which slowly faded away until only its grin remained. The Cheshire isn’t a breed of cat: it is an English county where cheese was (and still is) made. Possibly Carroll was referring to the British shorthair, a breed of cat that appeared on Cheshire Cheese labels.

  The Cheshire Cat.

  Problem 79 of the ancient Egyptian Rhind Papyrus (pages 77-8) poses the sum

  houses 7

  cats 49

  mice 343

  wheat seed 2,401

  hekat 16,807 (a hekat is a measure of volume)

  TOTAL 19,607

  where each number is 7 times the previous one. The scribe gives a short cut:

  2,801×7 = 19,607

  Note that 2,801 = 1 + 7 + 49 + 343 + 2,401. These numbers are the first few powers of 7. I have no idea why the scribe thought it sensible to add up such diverse items, mind you.

  Still on exponential growth: the Humane Association has pointed out that if two cats and their kittens breed for 10 years, with each cat having two litters of three surviving kittens per year, then the cat population grows like this:

  12 66 382 2,201 12,680 73,041 420,715 2,423,316 13,968,290 80,399,780

  In the 1960s the Russian mathematician Vladimir Arnold studied a map (another word for ‘function’ or ‘transformation’) from the torus to itself, defined by

  (x, y) → (2x + y, x + y) (mod 1)

  where x and y lie between 0 (included) and 1 (excluded), and (mod 1) means that everything before the decimal point (the integer part) is ignored. So 17.443 (mod 1) = 0.443, for instance. The dynamics of this map are chaotic (Cabinet, page 117); also, it ‘preserves area’, meaning that areas don’t change when it is applied. So it provided a simple model for more complicated area-preserving maps arising naturally in mechanics.

  This map quickly became known as Arnold’s cat, because he illustrated its effect by drawing a cat on the torus, and showing how the cat distorts when the map is applied. The same thing is done with a picture of a real cat at:

  upload.wikimedia.org/wikipedia/commons/a/a6/Arnold_cat.png

  www.nbi.dk/CATS/PICS/cat_arnold.gif

  Author Theoni Pappas wrote a children’s book, The Adventures of Penrose the Mathematical Cat, presumably named after mathematical physicist Roger Penrose.

  Arnold’s cat.

  In the book Mathematicians in Love by Rudy Rucker, two mathematics graduate students prove a theorem characterising all dynamical systems in terms of objects from Dr Seuss’s The Cat in the Hat.16

  In his 1964 research text Abelian Categories, Peter Freyd included the index entry ‘kittygory’. The page concerned refers to a ‘small category’.

  There’s a mathematician named Nicholas Katz - does that count?

  Um - Felix Hausdorff?

  The Rule of Eleven

  There’s an old test for divisibility by 11, seldom taught in these days of calculators. Suppose, for example, that the number is 4,375,327. Form the two sums

  4 + 7 + 3 + 7 = 21, 3 + 5 + 2 = 10

  formed by taking every alternate digit (4375327). Take the difference, 21-10 = 11. If this difference is exactly divisible by 11, so is the original number, and conversely. (The number 0 is exactly divisible by 11, being equal to 11×0.) Here the difference is 11 itself, which is divisible by 11, so the test says that 4,375,327 is divisible by 11. In fact, it is equal to 11×397,757. Initial zeros make no difference, by the way, since they add zero to whichever sum they appear in.

  Here are two puzzles and a question; the puzzles are easier if you use this test.

  • Find the largest number that uses each of the digits 0-9 exactly once, and is divisible by 11 without remainder.

  • Find the smallest such number, not starting with 0.

  • While we’re at it: what is the smallest positive multiple of 11 for which the test does not yield a difference of zero? Answers on page 290

  Digital Multiplication

  The square array uses each of the nine digits 1-9. The second row 384 is twice the first row 192, and the third row 576 is three times the first row.

  1 9 2

  3 8 4

  5 7 6

  There are three other ways to do this. Can you find them?

  Answer on page 291

  Common Knowledge

  There is an entire genre of puzzles that rests on the counterintuitive properties of ‘common knowledge’ - something that has been made public, so that not only does everyone involved know it, but they know that everyone knows it, and they know that everyone knows that everyone knows it . . . A traditional case concerns the curious habits of the obscure but very polite Glaberine17 order of monks.

  Not ‘habits’ as in clothing, you appreciate.

  Brothers Aelfred, Benedict and Cyril are asleep in their cell, when the novice Legpulla sneaks in and paints a blue blob on the top of each of their shaven heads. When they awake, each notices the blob on the other’s head. Now, the monastery rules are clear: it is impolite to say anything that will cause direct embarrassment to another member of the order, but it is also impolite to conceal anything embarrassing about yourself. And impoliteness is not permitted under any circumstances. So the monks say nothing, and their demeanour gives no hint of what they have seen.

  Each vaguely wonders whether he, too, has a blob, but da
re not ask, and there are no mirrors in their cell, nothing reflective at all. And so things remain until the Abbot enters, frowns, and informs them (neatly avoiding direct embarrassment) that ‘At least one of you has a blue blob on his head.’

  Of course, all three monks know that. So does the information make any difference to them?

  If you’ve not met this puzzle before, it helps to start with a simpler version, just two monks, Aelfred and Benedict. Each can see the other’s blob, but has no idea what his own head might bear. After the Abbot’s public announcement, Aelfred starts thinking. ‘I know Benedict has a blob, but he doesn’t, because he can’t see the top of his own head. Dear Lord, do I have a blob? Hmmm . . . Suppose I don’t have a blob. Then Benedict will see that I don’t, so he will immediately deduce from the Abbot’s remark that he must have a blob. But he hasn’t shown any sign of embarrassment. Oh dear, I must have a blob.’ Benedict comes to a similar conclusion.

  Without the Abbot’s remark, these deductions don’t work, yet the Abbot tells them nothing - apparently - that they don’t know already. Except ... Each knew that at least one monk (the other one) had a blob, but they didn’t know that the other monk knew that at least one monk had a blob.

  Got that? Very well - what happens with three monks? Again, they can all deduce that they have blobs, but only after the Abbot’s announcement (see the answers on page 291). The same goes when there are four, five, or more monks, if all of them have blobs on their heads. Indeed, suppose there are 100 monks. Each bears a blob, each is unaware of that, and each is an amazingly rapid logician. To avoid timing issues, suppose that the Abbot has a bell. ‘Every ten seconds,’ he tells them, ‘I will ring this bell. That will give you time to carry out the necessary logic. Immediately after I ring, all monks who can deduce logically that they have a blob must put their hands up.’ He waits ten minutes, ringing his bell from time to time, but nothing happens. ‘Oh, yes, I forgot,’ he says. ‘Here is one extra piece of information. At least one of you has a blob.’