Wednesday, November 21, 2007

Wednesday Math, Vol. 5: The arithmetic of a clock

On an analog clock, we can't tell the difference between 9:30 in the morning and 9:30 at night. Twelve hours from now, the clock will be in the same position it is in right now. In math we call this modulo arithmetic, in this particular case, it is modulo 12, written in shorthand as mod 12.

The idea of mod 12 is that all the numbers from negative infinity to infinity are put into 12 categories. Two numbers a and b are in the same category if a - b is a multiple of 12. Let me give a shorthand list with ellipses of some of the categories.

0 (mod 12) = {..., -24, -12, 0, 12, 24, 36, ...}
1 (mod 12) = {..., -23, -11, 1, 13, 25, 37, ...}
2 (mod 12) = {..., -22, -10, 2, 14, 26, 38, ...}
10 (mod 12) = {..., -14, -2, 10, 22, 34, 46, ...}
11 (mod 12) = {..., -13, -1, 11, 23, 35, 47, ...}

The category 11(mod 12) states that the clock 11 hours from now will look the same as it did 1 hour prior to now, or 13 hours prior, or 23 hours from now, or 35 hours from now, etc. If I take two elements from the category, say 47 and -1, we have that 47 - (-1) = 47+1 = 48, and 48 is evenly divisible by 12. If I put the numbers in the opposite order, -1 - 47 = -48, which is still evenly divisible by 12.

When I talk about 11(mod 12), I chose 11 as the representative of the set. It's standard in math to choose the representative in modulo n as a number between 0 and n-1, but I also could have called the set -1(mod 12) or 23(mod 12). Any member of the set can be chosen as the representative. For example, when we think of the minute hand by itself, we are dealing with modulo 60, where the only valid numbers are from 0 seconds to 59 seconds, and at 60 seconds it wraps back around to 0. When dealing with hours, instead of going from 0 to 11, we go from 1 to 12. The decision in mod n to count from 0 to n-1 or 1 to n is an arbitrary one. In fact, our way of doing things on the clock is a little confusing.

10 am + 1 hour = 11 am
11 am + 1 hour = 12 pm
12 pm + 1 hour = 1 pm

When we go from the 11th hour to the 12th hour, we also switch the am and pm. To be consistent, it would make more sense to use 0 instead of 12, much in the same way as we count from 0 to 59, then wrap back around to 0 when counting minutes or seconds in modulo 60.

10 am + 1 hour = 11 am
11 am + 1 hour = 0 pm
0 pm + 1 hour = 1 pm

Modulo arithmetic is an important part of group theory. Instead of an infinite number of numbers, mod 12 has only 12 numbers, so addition mod 12 is a finite group. All the integers, positive and negative, are a set known in math as Z, which is the first letter in zahlen, the German word for number. When we deal with modulo arithmetic, we write Z12 or Z7 or Z60, where the number after the Z tells us when to wrap around.

Besides finite groups and infinite groups, another distinction is between abelian groups and non-abelian groups. In an abelian group, a+b always equals b+a. In non abelian groups, this isn't always true. When dealing with the category of groups that are both finite and abelian, ny such group can be written as a combination of modulo arithmetic groups. The combination method is called Cartesian product. If you remember learning about x and y coordinates on the plane, written as (x, y), that is an example of a two dimensional Cartesian product. In math we can also have three dimensions or even more if we see fit. For example, if we have a finite abelian group with eight elements, the possibilities are:

Z8 - This is the set {0, 1, 2, 3, 4, 5, 6, 7} with addition, and the rule of wrapping around.
For instance, 7+5=12 in regular addition, but 12 is too big, and by subtracting 8, we get 12 is equivalent to 4(mod 8), so 7+5= 4(mod 8).

Z4 x Z2 - In this group, we have pairs of numbers where the first number is from {0, 1, 2, 3} and the second number is from {0, 1}. The elements of this group are { (0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)}.
(3, 1)+(2, 0) = (3+2, 1+0) = (5, 1), but because 5 is too big for mod 4, the answer is
(3, 1)+(2, 0) = (1, 1) in Z4 x Z2.

Z2 x Z2 x Z2 - Think of Z2 as being like even (0) and odd (1), where odd+odd=even, so we write this as 1+1=0(mod 2).
All the rest of the addition is as we would expect: 0+0=0, 1+0=1, 0+ 1=1.
Here we have ordered triplets of numbers, every number either 0 or 1, so the set is as follows: {(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.

The basic 'splainin' about finite groups is relatively straightforward, but the more advanced stuff includes the most common methods of cryptography used today, using modulo arithmetic by a number n which is the product of two huge prime numbers, each of them somewhere between 20 or 40 digits long.

Now playing: The Chieftains - Past Three O'Clock
via FoxyTunes


dguzman said...

Man, you really love math. I admire you for that.

Splotchy said...

You lost me with the zahlen stuff at the end. And abelian versus non-abelian - I don't really understand the distinction (but the distinction wasn't the goal of your post, I reckon).

Didn't understand the zahlen equations. I didn't really understand what your Z equations were supposed to indicate. Are those X's supposed to represent multiplication?

To show I have learned something from your post, I will say that military time is mod 24, using a count from 0 to n-1.

Matty Boy said...

Thanks for letting me know, Splotchy. I hate to lose a student who is paying attention. I added some 'splainin' to show what the x means, combining copies of two or more clock arithmetic systems together.

Let me know if it helps.

Distributorcap said...

but you still can't take the square root of negative one.....

ok it is i

Matty Boy said...

Hi, dcap. As someone with a master's in math, you would know that using i and multiplication creates a group with 4 elements.

i = i
i*i = -1
i*i*i = -i
i*i*i*i = 1

So if I raise i to some whole number n, there are only four possible answers, and it depends on n(mod 4).

Splotchy said...

If I'm understanding correctly (and I don't know if I am), in the Z8 (sorry, comments don't allow me to subscript) zahlen, it represents a set of numbers, and then you take an everyday arithmetic problem (7+5=12) and show how the answer would be displayed in modulo arithmetic, represented by the Z8 set (zahlen).

I'm still a little unclear what the "answer" is for the remaining equations, if there indeed is one. I think I understand that you're combining the different zahlens to represent a combination set of the two or three zahlens (the definition of a Cartesian product?).

Are you representing the same 7+5=12 equation in the following line?


If not, what are you doing here? If so, what are you doing here?

Matty Boy said...

Splotchy asks:


(3, 1)+(2, 0) = (1, 1) in Z_4 x Z_2


Answer part 0: When we don't have easy access to subscripts, math folk use the underscore, as in Z_4.

Answer part 1: The 7+5 example and the (3, 1)+(2, 0) example are completely separate.

Answer part 2: If you understand the idea of the military clock as numbers between 0 and 23 that wrap around, you can think of Z_4 x Z_2 as two separate clocks, the first with the numbers 0, 1, 2 and 3, the second with only the numbers 0 and 1. The addition we do on the first clock is completely separate from the addition we do on the second clock, but we still consider the two clocks together as a single system.

Let me know if this makes any more sense.

Splotchy said...

Thanks for the extra 'splainin'!

Answer 0: That makes sense to me. I knew I could represent exponents with a caret ('^') but I guess it could potentially be used by to indicate any kind of superscript (though I can't think of any use for a superscript besides an exponent off the top of my head). It makes sense that you can use an underscore for a subscript.

Answer 1: I think I get you now with this.

Answer 2: And I get this too.


FranIAm said...

I am feeling very, well very non-smart at the moment.

But still glad to be here after days of not really having time to read or comment.

You smart kids are something else.

Matty Boy said...

My dear friend Victor Manjarrez, who taught at Cal State Hayward but I never took a class from him, used to say.

"I'm glad we cleared up that little piece of understanding."

He was being humoresque, of course. Sometimes math takes a little more work.