About This Site
Powers and Fractions
Notes About Squares
> Repeat Length Again
Intrinsic Nature of Primes
Other Topics (2)
Multiplication in Base 7
The Exceptions Explained
How Many Exceptions?
The Usual Random Thoughts
Now we come to the usual random thoughts exploding in different directions at the end … only this time there are so many of them that I had to split them off into their own subessay. I'm not even going to try to tie them together, I'm just going to jump from one to the next without warning.
The argument that we used in The Exceptions Explained to show that the orders increase by factors of p can also be used to prove that Upk is cyclic, given that Up is. I think that makes a nice footnote to The Structure of Un. (Caveat: the argument does not apply for p = 2, and in fact the groups U2k are not cyclic for k >= 3.)
Regarding the probability distributions for len(p), there are some general rules that apply. For p = 2, the length is always 1. For any other prime, there are always two major peaks: a primary peak at the full length p-1, and a secondary peak at the half length (p-1)/2. The secondary peak is the same size as the primary if p ≡ 3 mod 4, otherwise half the size. No other peak is more than half the size of the primary, so if you have to guess a length, the full length is as good a guess as any.
Actually, that's not quite true … you can use quadratic residues to rule out either the primary or the secondary peak. I learned that from an excellent article by Helmut Richter—who ran the exception search in base 10!—and I can't explain the result any better than he does.
In other words, we have to find K such that the period length is (p-1)/K. In which cases K is even can be determined by quadratic residues: K is even if and only if the base b of the number system is a quadratic residue modulo p. For base 10, this is the case if and only if the distance of p to the nearest multiple of 40 is one of 1, 3, 9, or 13.
So, in the listed cases, you should guess the secondary peak instead.
The exceptions in base 2 are much more famous than the exceptions in base 10. They're called Wieferich primes (see also A001220), and only two are known, 1093 and 3511, even though the search has been carried quite a bit further than in base 10.
… a limit since increased to 1.25×1015 (McIntosh 2004)
No, that's not me, in case you were wondering. Strangely, I'd heard of Wieferich primes only once before, when I was reading about Catalan's conjecture (that I mentioned in Sharps and Flats) … apparently they figure into the proof somehow or other.
I couldn't find any lists of exceptions in other bases, so I ran the numbers myself, and here are the results. An entry marked with an asterisk is a double exception.
I don't have the computing power to run a truly gigantic search, but the table is complete up to 108, and also includes two larger numbers that I saw elsewhere, so that it represents everything I know about the listed bases. The results agree with the sequence A039951 if we take into account the fact that I've excluded 2. Also, according to the other table, the expected number of exceptions below 108 is 3.175, or rather 2.675 after we exclude 2, and the results seem to agree fairly well with that, too. The rows for base 21 and base 29 are blank, and the row for base 34 has only the one larger number … sounds like a reason to use one of them as a base! (Base 21 and base 34 are also good for divisibility testing.)
There are a few patterns we can observe: if the base has the form bk, then it has at least the same exceptions as base b; if also k is divisible by a prime p, then p is an exception of order k-1; and if the base is adjacent to a multiple of pk, then p is (again) an exception of order k-1. The third pattern has a particularly simple explanation. For example, 3 is an exception in base 28 because 28 in base 3 is 1000+1, so 282 = 1002001, with two zeroes at the end. And, of course, for any particular prime we can work out the multiplication table mod p2 and determine the complete pattern. For example, p = 7 is an exception if the base is congruent to 1, 18, 19, 30, 31, or 48 mod 49.
Hey, actually, those patterns are all we need to see the connection to Catalan's conjecture! Suppose the primes p and q have adjacent powers. The power of p is (trivially) a multiple of pk, so p is an exception in base qwhatever; but then p is also likely to be an exception in base q. By symmetry, however, q is likely to be an exception in base p, so that the primes form a double Wieferich prime pair!
What about exceptions with multiple anomalous steps, i.e., with d >= 2? We can already see some with d = 2 in the table: 3 in bases 26 and 28, as a result of the third pattern, and 7 in bases 18 and 19, for no particular reason. That article by Richter mentions a few good ones with d > 2: 13 in base 239 and 5 in base 443, with d = 3, and 5 in base 1068, with d = 5! Let's look at that last one in more detail. 1068 written in base 5 is 13233, nothing unusual there, but then 132332 is 243000000-1, so that 132334 ends in 000001, as expected. Or, looking at it the other way 'round, in base 5 the square root of 73 (243) is 13.23300001213. We can actually see an echo of that in base 10, where it's 8.54400374532.
Now, at long last, I'm going to tell you what I know about p = 2. Let's start with the practical side of things. If we're working in base b and want to understand how the sequence len(2k) behaves, then just as for any other prime p we need to switch to base p and find the first power of b that ends in 1. However, b must be odd, or we'd have discarded 2 … and every odd number ends in 1 in base 2! So, we just need to write down the number b itself in base 2. If the number ends in 01, everything goes as before … d is equal to the number of trailing zeroes, and the lengths obey the improved rule
len(pk) = pk-1-d len(p),
albeit never with d = 0. If the number ends in 11, though, things are different … we need to take the twos complement before we count the zeroes, and if the rule tells us the length is 1, we should use 2 instead. I'm going to use the notation d+ and d- for the two cases, to distinguish them from each other and to remind us that p = 2 is different. To bring all that down to earth, here's a small table of repeat lengths.
On the theoretical side, I'm not going to prove all that, but I will mention a few helpful facts I discovered. First, if you square a number that ends in 01 and has n trailing zeroes, you get a number that ends in 01 and has n+1 trailing zeroes. Second, such numbers—numbers that are congruent to 1 mod 4—form a cyclic subgroup of order 2k-2. (You can use the first fact to prove the second … any number that ends in 101 has order 2k-2 and so is a generator.) Third, you can get to the rest of the group by negating.
Finally, to tie everything up in a nice little package with a bow on top, let's go back to base 7, to the rules for computing len(n), and to that old favorite of mine, 2401, and see what we can say about the length of 1/10k in base 7. In Powers of N, remember, I said that 1/100 has the same length as 1/10 because 2400 is divisible by 100 … that's true, but it's hardly the whole story. The way I see it now, we should factor 10 as 5 × 2 and look at the components.
When we take the least common multiple of the two, though, the factor of 4 from the 5 side covers up the 2 side for quite a while.
Multiplication in Base 10
Two Kinds of Odd
@ April (2006)