Home> urticator.net Search About This Site > Domains Glue Stories Computers Driving Games Humor Law Math > Numbers Science Powers and Fractions Notes About Squares Decimal Expansions > Repeat Length Again Number Maze Primes Divisibility Intrinsic Nature of Primes Other Topics Other Topics (2)
How Many Exceptions? The Usual Random Thoughts 
Multiplication in Base 7What I have to say about multiplication in base 7 is really very straightforward, but I happen to think about it in mathematical jargon, and I don't want to waste time trying to avoid what are in fact exactly the right words. So, instead, if you don't mind, I'll just start a little further back than you might expect … I think that will make everything perfectly clear. Let's start with congruence. We say two numbers a and b are congruent modulo n if they differ by a multiple of n—that is, if there's a number k such that a = b + kn—and we write a ≡ b, possibly with a “mod n” at the end if it's not clear what the modulus is. (The word “modulo” is just Latin for “with modulus”.) As the written form suggests, the idea is to think of congruent numbers as equal, so that for example n and 0 are no longer different numbers. So, if we're counting, we start with 0, 1, 2, and 3, then eventually we get to n1, and thence to n, or rather 0, and we're right back where we started. So, since the numbers modulo n form a circle, or cycle, we call them a cyclic group; and since they turn up fairly often, we give them a standard symbol, Z_{n}. Wheels and clocks are good examples to keep in mind here. Next, let's consider pairs of numbers xy where x is an element of Z_{3} and y is an element of Z_{2}. We can think of the numbers as coordinates, like so.
Now we can count horizontally, by 10s—00, 10, 20, 00— or vertically, by 01s—00, 01, 00. Since it takes three steps to get back to the start in the first case, and two in the second, we say that the element 10 has order 3, and that 01 has order 2. But what if we count diagonally, by 11s? We get the whole group!
Any element that generates the whole group is called a generator; cyclic groups have generators, noncyclic groups don't. Also, more specifically, we see that the element 11 has order 6. Now that that's settled, I can explain what you may already have guessed, which is that the elements are colorcoded by order. The other green element, 21, is the other generator of the group. Now let's look at a completely different group, Z_{6}.
Actually, as you can see, it's not so different. The size is the same, the structure is the same … only the labels are different. In such a case we say the two groups are isomorphic; the word is Greek for “same shape”. (In fact, even the labels aren't as different as they seem. For example, the element 5 that appears in place of 21 is congruent to 2 mod 3, and to 1 mod 2.) In general, the group Z_{mn} is isomorphic to the product Z_{m} × Z_{n} if the numbers m and n are relatively prime, i.e., have no common factor. (And, conversely, if the numbers have a common factor, the groups aren't isomorphic. As a concrete example, you can construct Z_{2} × Z_{2} and see that it has no generators, and so is not the same as the cyclic group Z_{4}.) Now we're ready to think about multiplication! Let's see what happens if we “count” multiplicatively by 3s, mod 7.
At the end, we're right back where we started, so what we have here is another cyclic group … … or, rather, the same cyclic group again, with different labels. For example, just as 3 + 3 = 0 in Z_{6}, here 6 × 6 = 1. The correspondence isn't as strange as it seems. Multiplication is converted into addition by the identity 3^{a} × 3^{b} = 3^{a+b}, and 6 is identified with 0 by the relation 3^{6} ≡ 3^{0} mod 7. On the other hand, the correspondence isn't trivial. It's hard to find a generator g; and once you've found one, it's easy to go from a to g^{a}, but hard to go from g^{a} back to a. (That's the discrete logarithm problem I mentioned at the end of Repeat Length.) We're not done yet, though … the subject here is multiplication in base 7, not just mod 7. Fortunately, the two are related. In any base, the last digit in a number tells the value modulo the base; so since we understand multiplication mod 7, we know how the last digit in a base 7 number behaves. So, as a next step, let's find out how the last two digits behave by looking at multiplication mod 7^{2}. First, let me explain a little bit more theory. When we multiply instead of add, the numbers modulo n have a different structure, so we give them a different symbol, U_{n}. The structure of U_{n} is interesting, well worth reading about some time, but for now all we need to know is that for any prime p (other than 2), U_{pk} is a cyclic group with (p1) p^{k1} elements. Then, since p1 is not divisible by p, the numbers p1 and p^{k1} have no common factor, and the group is isomorphic to the product Z_{p1} × Z_{pk1}. The Z_{p1} component can be broken down further, as we saw above for p = 7, but here it's more convenient if we leave it in one piece. So, in particular, the group U_{72} is isomorphic to the product Z_{6} × Z_{7}. Here it is in tabular form.
The numbers are all in base 7, naturally, and the graytinted elements have an extra factor of 7 in the order, so that for example the order of 02 is 3 × 7 = 21. There are many interesting things to observe here!
That still doesn't quite give us the full picture, so, finally, let's take a brief look at how the last three digits behave. The group U_{73} breaks into two pieces, Z_{6} × Z_{72}; the second component, although large, cannot be broken down further. I won't show the whole table, but here's how it starts.
Again, there are many interesting things to observe.
Now you know everything I do about multiplication in base 7!

See AlsoLogarithmic Forms Multiplication in Base 10 Repunits @ April (2006) 