Other Bases

The first way of understanding is to use other bases. As I said in Hexadecimal,

I bet if one really learned to think in foreign bases, it would be amazing. I imagine one would be able to see the numbers and their relationships almost as Platonic ideals, free of any accident of base.

The essay about divisibility in other bases is probably the most compelling view I can offer; it really does say something about the intrinsic nature of the primes. What I want to do here is much simpler … I want to look at what last digits the primes can have in other bases.

In base 10, of course, all the primes (except 2 and 5) have to end in one of the digits 1, 3, 7, and 9 … 1379 for short. So, that's four possible digits … not a lot, certainly, but there are some bases that have fewer. In base 2, for example, all primes end in 1 … but that's not much of a constraint, because any odd number ends in 1 in base 2.

In base 4 the situation is more interesting. The primes, like the odd numbers, end in 1 and 3; but now the primes ending in 3 have very different number-theoretic properties from the ones ending in 1! If a prime p ends in 1, for example, then the size of the group of integers under multiplication mod p is divisible by 4. As a result, the element −1, which always appears in the middle because it has order 2, has a square root, in fact two of them; in other words, −1 is a quadratic residue. And, conversely, if p ends in 3, it's not.

There are also two possible digits in base 6, namely, 1 and 5. What's nice about that base is that the small primes exhibit a surprising amount of order. Here's a list of the first few primes in base 6, which you can compare to the list in base 10 at the start of Primes.

2 3 5   11 15   21 25   31 35   45   51   101 105   111 115

The only breaks in the pattern are at 41 and 55, which can be written as 50 ± 5, and which, therefore, are clearly divisible by 5, and not prime.

To some extent, base 12 provides the best of both worlds. The first few primes follow a nice pattern, and the last digits tell the residues mod 4. Unfortunately, since there are four possible digits (157B), the pattern quickly begins to look as irregular as the pattern in base 10.

Finally, of all the bases I'm going to talk about, the last digit is most constrained in base 30, where it has eight possible values, 17BD and HJNT. (Actually, the last digit is just as constrained in base 60, and tells the residue mod 4 too, but then, as I explained in In Other Bases, base 60 isn't good for divisibility testing.)

The really excellent thing about base 30, which I didn't fully appreciate until a friend pointed it out to me, is that the eight possible values of the last digit correspond to the eight positions in a block of the sieve pattern, or, as I later decided to call it, a tableau.

Now I need to digress in reverse, and jump over to say a bit about last digits in general. Suppose we write out the whole multiplication table in base n. If we erase everything except the last digits, we get the multiplication table mod n; if we then erase everything except the rows and columns for numbers relatively prime to n, i.e., for numbers that are last digits of primes, we get the multiplication table for the group U_n.

Just to make things a bit less abstract, let's compare base 10 and base 12. There are four possible last digits in either case, but the group structures are completely different. The group U₁₀ is the four-element cyclic group Z₄, …

1

3

9

7

… but the group U₁₂ is the product ( Z₂ )².

B	7
1	5

Now we return to base 30. When I was thinking about tableaux and products, it occurred to me that not only the prime factors but also the resulting composite numbers had to end in one of the eight possible last digits. In other words, every product could be projected onto a product in U₃₀! Thus, I thought it might be beneficial to understand multiplication in U₃₀ … if nothing else, I could use it to compute checksums, or, rather, check-products.

Now, the group U₃₀ is just the product Z₂ × Z₄. The generators can be chosen in various ways (as they can be above, too, actually); the ones below are the easiest to work with, I think. Here I've used negative numbers to represent the congruence classes of the digits HJNT; the digit T, for example, congrues to −1.

−1	7	B	D
1	−7	−B	−D

I never did use this for anything, but I still think it's neat.

I was just fooling around when I said “congrues”, above, but since I formed the word via the standard pattern, naturally it's a real word, in Latin if not in English, and it means just what you'd expect. There's something very amusing about its roots, however. It's made from the prefix “con-”, “together”, and the verb “gruo”, “I honk”, which in turn derives from the noun “grus”, “crane” (bird.crane) … also the name of a constellation, by the way. I've never seen many cranes, here or elsewhere, so I prefer to use Canadian geese for my mental image of honking. In any case, we end up with the perfect summary of why modular arithmetic works: the numbers that honk together, stay together.