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 (Section)
  Number Maze
  Primes
  Divisibility
  Intrinsic Nature of Primes
  Other Topics
  Other Topics (2)

  Decimal Expansions
> Repeat Length Again
  The Nagell-Ljunggren Equation
  A Digression

> Multiplication in Base 7
  The Exceptions Explained
  How Many Exceptions?
  The Usual Random Thoughts

Multiplication in Base 7

prev

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.

1 × 3 =3
3 × 3 =9≡ 2
2 × 3 =6
6 × 3 =18≡ 4
4 × 3 =12≡ 5
5 × 3 =15≡ 1

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!

  • Although the group is built on multiplication, now that we've written it out as a table the elements combine by coordinate addition, just as in the original example Z3 × Z2. For example, the element 03 has coordinates (1,1), so we can multiply any element by 3 by taking a diagonal step up and to the right.
  • In particular, the table is a multiplication table—the element at (x,y) is the product of the elements at (x,0) and (0,y). For example, 24 × 31 = 04.
  • The table is completely determined by the generators at positions (1,0) and (0,1), but the generators are not uniquely determined. There are two elements of order 6 (pure green), and six of order 7 (pure gray), so there are twelve possible table arrangements.
  • There's a natural projection from U72 to U7: discard the first digit. If we have two two-digit numbers, we get the same result if we multiply and then discard the first digit as if we discard the first digits and then multiply. (There's a nice commutative diagram for you.) In practical terms, that's why the last digit is constant in each column. I picked 43 as the horizontal generator so that the last digits would match the table for U7.
  • The pattern in the left column is a result of the following identity.

    a1 × b1= (ap + 1)(bp + 1)
    = abp2 + (a+b)p + 1 ≡ (a+b)p + 1 = (a+b)1

    Of course I had to pick 11 as the vertical generator once I saw that.

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.

  • Look at the element of order 2 in the three groups so far. I might have believed it a coincidence that the first two were 6 and 66, but that the third is 666 is really too much. The explanation, of course, is that the element of order 2 is really always −1 (because (−1)2 = 1 in any modulus), and that the 6s are just what −1 looks like mod 7k.
  • As before, the table is completely determined by the generators. There are 42 elements of order 49 (dark gray), but still only two of order 6, so there are 84 possible table arrangements.
  • Much as before, there's a natural projection from U73 to U72. In practical terms, if we discard the first digits of all the elements in the table, we see we have a vertical stack of copies of the previous table. That requirement restricts the possible table arrangements, of course—it determines the horizontal generator and forces the vertical generator to end in 11, leaving seven possible arrangements.
  • Much as before, the pattern of order-7 elements in the left column is controlled by an identity, in this case, a01 × b01 = (a+b)01. However, we no longer get to pick which one comes first … the first one is the seventh power of a vertical generator ending in 11, and, as it happens, the answer doesn't depend on what the initial digit is. Fortunately, the answer turns out to be 101, just as desired! (I'm pretty sure that the answer turns out as desired for any prime and any number of digits, but it's still something of a happy accident that it does.)
  • So, in the end, we're left with an arbitrary choice for the initial digit of the vertical generator. I like 0 because it displays a bit of the Pascal's triangle pattern that I mentioned in Powers of N.

Now you know everything I do about multiplication in base 7!

next

 

  See Also

  Decimal Expansions (Section)
  Logarithmic Forms
  Multiplication in Base 10
  Printer Theory
  Repunits
  Structure of Zn, The

@ April (2006)