We looked again at addition and multiplication tables mod n, in particular at mod 5:
| + | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
| * | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
We noted things about the patterns in these tables. The addition table has a very simple structure. It can be traced back to the fact that addition in modular arithmetic is "arithmetic on the face of a clock." That is, you can add as usual, but when you get to 5, in this case, you cycle back to zero and start over, just as on a clock face when you get up to 12, you start over. (Example: Starting at 12:00, if you wait 3 hours, then 5 hours, then 5 hours again, you have waited 13 hours in all, but on the clock it says 1:00. This is addition mod 12).
The multiplication table looks more complicated. It is worth noting, though, that the elements {1,2,3,4} (omitting 0) are invertible. That is, for each of them, there is another one such that their product is 1. Thus 1*1=1, 2*3=1, 3*2=1, 4*4=1. In particular, 4 is its own inverse. This means that we can, in a sense, divide mod 5 as well as multiply. To divide by 3 you just multiply by 2, since 2 is the inverse of 3 (mod 5). To introduce a VERY BAD notation, we could say 1/3 instead of 2! ( We won't, though.) The set of invertible elements in mod n arithmetic forms a very nice little set with a good multiplication called the "group of invertible elements."
Here is the multiplication table mod 4:
| * | 0 | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 0 | 2 |
| 3 | 0 | 3 | 2 | 1 |
Unlike the mod 5 case, above, not all the nonzero elements are invertible. The number 2 does not have an inverse (note that "1" does not occur in the row that shows the various products you can get with 2). The only invertible elements are 1 and 3. The number 2 has the weird property that 2*2=0 mod 4. It is therefore called a "zero divisor." Zero divisors do not occur in our usual arithmetic, and they complicate the process of solving equations. Much nicer is the group of invertible elements:
| * | 1 | 3 |
| 1 | 1 | 3 |
| 3 | 3 | 1 |
mod 4. The only non-obvious line is 3*3=1 mod 4 (showing that 3 is its own inverse).
The same sort of thing happens in mod 6 arithmetic. Here is the multiplication table:
| * | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
There are lots of zero divisors mod 6: 2, 3, and 4. The only invertible elements are 1 and 5. A little reflection shows that mod 4 and mod 6 arithmetic have zero divisors because 4 and 6 are not prime. For example 4*3=0 mod 6 because 4 has some of the factors of 6 and 3 has the remaining ones, so that all together they contain the factors of 6, and hence give 0 mod 6. This cannot happen if you look at arithmetic mod p where p is a prime number, because then there are no factors to split up and put it in two different places. We might also notice in these examples that the invertible elements are exactly the ones which are relatively prime to the mod. In this last example, 1 and 5 are relatively prime to 6, while 2, 3, and 4 share factors with 6.
In the mod 5 example, {1,2,3,4} are all relatively prime to 5. The multiplication takes an unexpectedly simple form if you look at the element 2 and its powers: 2, 2^2=4, 2^3=3, 2^4=1 (mod 5). That is, the powers of 2 cycle through all the invertible elements. This group of invertible elements is therefore called a "cyclic group." The element 2 is said to be a "generator" of the group, because it generates all the elements. Just to play with this idea a little more, the element 4 is not a generator, because if you look at what it generates, you get just 4, 4^2=1, 4, 1, 4, 1, ... , i.e., only (4,1). You never get 2 or 3. On the other hand if you look at what 3 generates, you find 3, 3^2=4, 3^3=2, 3^4=1, ..., i.e., you get (3,4,2,1), all the invertible elements.
In the mod 6 example, {1,5} are relatively prime to 6 and invertible mod 6. This little group is also cyclic, and 5 is a generator, because its powers are 5, 5^2=1, ...., i.e., (5,1). This is the whole group.
Work out the multiplication table for mod 7 arithmetic. Since 7 is prime, we don't expect zero divisors, but comment on what you see. Which are the invertible elements? Finally, decide if this group is cyclic by determining whether there is a generator, a single element which generates the whole group when you take its powers.
The program POLYP in the Math 114 folder evaluates polynomials mod p. If you look at a polynomial in two variables, X and Y, then the values are shown in a table indexed by the values of X and Y, and if the polynomial happens to be XY, what you are looking at is exactly the multiplication table. This is the way the program comes up when you start it. The modulus is 13, so you actually find yourself looking at the multiplication table mod 13. You can change the modulus by using the "modulus" menu item. You can also change the way you visualize the information in the "view" menu item. By clicking in the table with the mouse you can get statistical information: how many times does this value occur in the table, etc. You don't need to use this, but you might enjoy looking at it. By changing the polynomial to X+Y you can make it an addition table, etc.