About This Site
Powers and Fractions
Notes About Squares
> Repeat Length Again
Intrinsic Nature of Primes
Other Topics (2)
How Many Exceptions?
The Usual Random Thoughts
Multiplication in Base 7
What 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 n-1, 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, Zn. 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 Z3 and y is an element of Z2. 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, non-cyclic 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 color-coded by order. The other green element, 21, is the other generator of the group.
Now let's look at a completely different group, Z6.
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 Zmn is isomorphic to the product Zm × Zn 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 Z2 × Z2 and see that it has no generators, and so is not the same as the cyclic group Z4.)
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 Z6, here 6 × 6 = 1.
The correspondence isn't as strange as it seems. Multiplication is converted into addition by the identity 3a × 3b = 3a+b, and 6 is identified with 0 by the relation 36 ≡ 30 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 ga, but hard to go from ga 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 72.
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, Un. The structure of Un 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), Upk is a cyclic group with (p-1) pk-1 elements. Then, since p-1 is not divisible by p, the numbers p-1 and pk-1 have no common factor, and the group is isomorphic to the product Zp-1 × Zpk-1. The Zp-1 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 U72 is isomorphic to the product Z6 × Z7. Here it is in tabular form.
The numbers are all in base 7, naturally, and the gray-tinted 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 U73 breaks into two pieces, Z6 × Z72; 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!
Multiplication in Base 10
@ April (2006)