## Friday, May 22, 2009

### Predicting with confidence If you've ever read time off of a clock, then you're familiar with something mathematicians call modular arithmetic. You might also think that modular arithmetic is science of counting all the possible ways you can configure an office using cubicles, and you'd be clever, but you'd be wrong. Modular arithmetic is simply ordinary arithmetic (adding, subtracting, multiplying, dividing, exponentiating) performed on numbers whereby you reduce the result to an equivalent number based on something called the modulus of the arithmetic. What does this have to do with a clock?

Well, let's say that it's 8:00 in the morning. You have to be at an important place in 5 hours, or 1:00 in the afternoon. Without much thought, you just did the following arithmetic operation:

8 + 5 =1

Writing it like that makes if feel strange and dirty and absolutely false, but yet it's true. . . in modular arithmetic. If you were in the military, or were one of those strange non-military people who prefer "military time," or a 24-hour clock, you would say that your important destination must be arrived at at precisely 1300 hours, or 13 o'clock. Because most people use the 12-hour clock, you're likely to get a few strange stares from people when you announced it, and you'd probably have to "do the math" for other interested, mathematically illiterate bystanders.

But it's exactly because clock values repeat them self in regular intervals of twelves that clock "arithmetic" is simply modular arithmetic with a modulus (abbreviated simply as "mod") 12. Because 8 + 5 really is 13, we can rewrite the above statement in modular form as

13=1 mod 12

We actually would read this as "13 is congruent to 1 modulus 12," which is a fancy way of saying 1300 hours is 1:00pm to most of us. Now that we've established this new math, let's say that we were big dorks, and one day we decided to not only abandon telling time on a 12-hour clock, but we wanted to keep track of the elapsed hours over a one year period. Imagine the strange looks we'd get if one afternoon 4 months later later, some stranger asked us for the time and we responded with "1841 o'clock . . . . on the DOT!" Would there be anyway to figure out the answer quickly without subtracting out full days at a time? Well yes.

What we'd really want to know in this case is the answer to the question 1841=? mod 24 which would give us the current military time, or, since we know it's in the afternoon, 1841=? mod 12, which would give us the current time p.m. The answer, as it turns out, will simply be the remainder obtained when dividing the given number by the given modulus, 1841/24 or 1841/12 here.

I turns out that 24 goes into 1841 76 times with 17 left over (1841 = 24*76 + 17). So 1841=17 mod 24. That means it's 1700 hours, or 5:00p.m. Using mod 12, we see that 12 goes into 1841 153 times with, you guessed it, 5 left over. So what time is it? Time to have that drink.

It turns out that MANY numbers are equivalent to the same number for any given modulus. For example, 5, 17, 29, 41, 53, 65, 77, 89, 101, etc. are ALL equivalent to 5 mod 12. For all such numbers that are equivalent to each other, we say they are elements of the same Residue Class.

Modular arithmetic works for other things too that occur in regular intervals. Take the world of competitive skate boarding. Imagine a shredder pulling off an AMAZING "7863" rotational trick. Since 1 rotation = 360 degrees and 7863 = 21*360 + 303, we know that so the skater did 21 full rotations plus an additional 303 degrees. Stated mathematically, we can write 7863 = 303 mod 360.

Modular arithmetic also pertains to the days of the week, with a modulus, of course, of seven. Perhaps you'd be interested in knowing what day of the week it will be exactly 1,000,000 days from today. Not that you'd be around to enjoy that day, seeing how its more than 2,739 years from now, but you're such a dork that you ponder these things. How could we do THAT calculation using modular arithmetic?

Let's start with today. Today is Friday (woooo hoooo! is it 5:00 yet?). From here, it requires a little more cleverness. Since 1 million is a power of ten, we will start the computations with the following, seemingly non-intuitve equation, and try to build up the left side, simplifying the result (mod 7) as we go.

10 = 3 mod 7

Feel free to verify this by dividing 10 by seven and finding the remainder. Now in any equation, even if it's modular, we are allowed to square both sides. Here we go.

100 = 9 mod 7

From here, we'll note that 9 = 2 mod 7, so we replace it in the above equation.

100 = 2 mod 7

We can now make a big jump to a million by cubing both sides. Since 100 cubed is 1,000,000 and 2 cubed is 8, we obtain the following.

1,000,000 = 8 mod 7

Now because 8 and 1 are in the same Residue Class, they are interchangeable. Performing the interchanging act we finally reach our desired equation.

1,000,000 = 1 mod 7

So how does that tell us what day of the week 1,000,000 days from today be? Well, the equation tells us that it will be the same day of the week that ONE day from today will be. Say it with me now, "If today is Friday, then tomorrow is . . . Saturday!"

Wasn't that a lot more fun than using a calculator? (Just say "yes.") Besides, our method works for numbers that are beyond the calculating capability of your calculator. If you don't believe me, tell me quickly what day of the week it will be 10 to the 100th power(that's called a "google" baby, a 1 followed by one hundred zeros) days from now.

If you you said "Wednesday, " you're calculator is lying to you.

Feel free to get back to me on that.