Home

> urticator.net
Search

> Domains
Glue
Stories

Computers
Driving
Games
Humor
Law
Math
> Numbers
Science

Powers and Fractions
Decimal Expansions
> Repeat Length Again
Number Maze
Primes
Divisibility
Intrinsic Nature of Primes
Other Topics
Other Topics (2)

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

## The Exceptions Explained

prev

There's one last fact we need to have on hand before we can get started. It's explained in detail in Repeat Length.

If b and n are relatively prime, the repeat length of 1/n in base b is equal to the order of b under multiplication mod n.

That one little fact has many consequences. For one thing, it makes it much less surprising that my algorithm for computing powers of N in base 10 should also produce the expansions of 1/10k in base N … I don't think I've mentioned that anywhere before. For another, it helps explain why, in the last step of the process above, the final repeat length is the least common multiple. If, for example, we want to know the length of 1/119, we factor 119 as 7 × 17 and recall that 1/7 and 1/17 have lengths 6 and 16. But then it follows that

 106 ≡ 1 mod 7 1016 ≡ 1 mod 17,

so that

 1048 = (106)8 ≡ 18 = 1 mod 7 1048 = (1016)3 ≡ 13 = 1 mod 17,

and therefore (see The Structure of Un if this is unclear)

1048 ≡ 1 mod 119.

Thus, the repeat length of 1/119 is 48, precisely because 48 is the least common multiple of both 6 and 16.

The main consequence, though, is that the question we're interested in—the question of how len(p) is related to len(p2), len(p3), and so on—is really a question about multiplication mod p, mod p2, mod p3, and so on! That wouldn't have helped us much, before; but now, with our detailed knowledge of the case p = 7, we can answer the question!

So, let's start by looking at len(7) in base 10, or rather at the order of 10 mod 7. But, there's not so much to look at … first we observe that 10 is congruent to 3, then we consult the table and see that 3 has order 6, and that's that.

So, why does len(7) turn out to be 6? No reason … if we used base 9 it would be 3; if we used base 8 it would be 1. In fact, if we pretend the base is chosen at random, we can count the elements in the table and get a nice little probability distribution!

(Of course really 1/7 of the time the base will be divisible by 7, and the decimal expansion of 1/7 will terminate. I'm excluding those bases here and in the rest of the discussion.)

Now, what about len(72)? Well, 10, written in base 7, is 13, which is already just two digits, so that's what 10 is congruent to mod 72. Then, consulting the table, we see that 13 has order 42.

Because of the projection from U72 to U7, 10 had to stay in the second column; the question was whether it would stay in the bottom row and keep the same order, or move up and increase its order by a factor of 7. There's no apparent pattern to which elements move and which stay; and in fact if we again pretend the base is chosen at random, we can see that an element stays in the bottom row with probability 1/7.

That's not some kind of abstract argument, by the way … we know exactly which elements move and which stay. For example, in that same column, 33 moves, but 43 stays, so that in base 31 (43), len(72) = len(7). An exception!

Now I imagine you can see where this is going, but let me walk you through one more step, since there's still one thing we haven't seen.

As before, everything is controlled by the projection. An element that was in the bottom row may stay there (with probability 1/7) and keep the same order, or move up to one of the light gray rows and increase its order; nothing new there. An element in any other row may also stay or move, but guess what … it doesn't matter! The element was light gray before, and will be dark gray after; the order is guaranteed to increase.

Now we can generalize. If we look at len(p) in some base b, it has an initial value that we can't predict. As we step through len(p2), len(p3), and so on, the value may remain the same for one or more steps, with probability 1/p each; then after that the value will increase by p at each step. If we call the number of anomalous steps d, we obtain the following rule (for the increasing part).

len(pk) = pk-1-d len(p)

So, the exceptions to the original rule are simply the primes p for which d > 0! (The only exception to the new rule is that p = 2 is different, as I'll explain later; but then we get to throw out p = 2 unless the base is odd.)

As a practical matter, it would be nice if we had a way to test whether a prime p is an exception without working out the entire multiplication table mod p2. Fortunately, we do. If an element appears in the bottom row of the table, and we take powers of it, the powers will all stay in the same row; so when we find one that lands in the first column, it will land in the bottom corner, on 01. Conversely, if an element appears in any other row, and we take powers of it until we find one that lands in the first column, it won't land in the bottom corner. That's not as obvious, but I'll leave it as an exercise. So, a prime p is an exception in base b if the first power of b that ends in 1 mod p2 happens to end in 01. (You can also just look at bp-1 if you want.)

Unfortunately, if p is an exception, that test doesn't tell us how many anomalous steps there are. We know there's one, but there could be more. To find out, the obvious thing to do is look at multiplication mod p3: if the first power of b that ends in 1 mod p3 happens to end in 001, there are at least two anomalous steps; if not, there's definitely only one. We could continue on to higher and higher powers of p, but there's a better way. The trick is, looking at higher powers of p doesn't affect the last digit … whatever power of b ends in 1 mod p2 will also end in 1 mod pk for all k; we might as well compute the number once, in base p, and be done with it. Then we can just read off the answer, because the number of anomalous steps is equal to the number of trailing zeroes! Just as an example, the first base in which 7 is exceptional is 18 (the 24 in the bottom row mod p2), and 183 in base 7 is 23001, so there are two anomalous steps in that case.

next