How common are prime powers?

The Mathematics Weblog at sixthform.info shows a cute little theorem: that the group table for any cyclic group can be arranged so that all the instances of the same element lie along a (possibly broken) diagonal, and that this isn't possible for noncyclic groups.

This reminds me of the addition tables one sees in the back of notebooks, which in base 10 look like

+	0	1	2	3	4	5	6	7	8	9
0	0	1	2	3	4	5	6	7	8	9
1	1	2	3	4	5	6	7	8	9	10
2	2	3	4	5	6	7	8	9	10	11
3	3	4	5	6	7	8	9	10	11	12
4	4	5	6	7	8	9	10	11	12	13
5	5	6	7	8	9	10	11	12	13	14
6	6	7	8	9	10	11	12	13	14	15
7	7	8	9	10	11	12	13	14	15	16
8	8	9	10	11	12	13	14	15	16	17
9	9	10	11	12	13	14	15	16	17	18

If you just look at the last digits -- thus considering this as addition in the group Z₁₀ -- then you see this pattern. All the numbers ending in, say, 5 -- the 5s and the 15s -- lie along a single broken diagonal.

You don't see the same pattern when you consider the analogous multiplication table, and so you think "hmm, the integers mod 10 under multiplication don't form a cyclic group?" But as it turns out, they do, and it's a cyclic group of order 4, because when we're considering the integers mod k under multiplication we only look at the invertible elements; these are 1, 3, 7, and 9, and we get the following little table:

×	1	3	9	7
1	1	3	9	7
3	3	9	7	1
9	9	7	1	3
7	7	1	3	9

Is this something special about 10, or is it common? Now, if we pick a random number k, what are the chances that the group of units (i. e. invertible elements) mod k is cyclic? From looking at the small cases, you'd think the probability is rather large: k = 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, and 14 have this property. But in general, it's actually pretty rare. Given k, we can write k = p^aq^br^c... where p, q, r... are primes, and consider the integers modulo each of the prime powers p^a, q^b, r^c, ... separately. For example, the group of units mod 10 is the direct product of the group of units mod 2 (trivial) and mod 5 (cyclic of order 4). The group of units mod 12, in contrast, is the direct product of the group of units mod 4 (cyclic of order 2) and mod 3 (cyclic of order 2, again), which isn't cyclic.

It turns out (this is a fairly basic result in classical number theory) that the units mod k form a cyclic group if and only if k is 2, 4, a power of an odd prime, or twice a power of an odd prime. This is a quite restrictive condition, although it doesn't seem so from the list I made; I suspect this sequence is only a bit less sparse than the primes themselves.

However, I can't show this quickly. The number of odd prime powers up to N is a bit smaller than log₃ N + log₅ N + log₇ N + ..., where the indices run over all the primes (the exact number is this with a floor function applied to each term); this is

(log N)(1/log 3 + 1/log 5 + 1/log 7 + ...)

and we can approximate the jth prime by j log j; thus this is approximately

(log N)(1/(2 log 2) + 1/(3 log 3) + 1/(4 log 4) + ...)

or at least has the same convergence behavior as this sum. But this sum can be approximated by the integral of 1/x log x from, say, 2 to infinity; that integral is log log x, so the sum diverges, although very slowly. As you may have guessed, I don't actually know analytic number theory, and I'm just fooling around here. I might actually be wrong; prime powers might end up being more common than primes for large enough numbers.