Is there a deeper reason for the classification of moduli in which a primitive root exists?

Question

The primitive root theorem classifies the set of moduli for which a primitive root exists as $$1,2,4,p^k,2p^k$$ where $p$ is an odd prime and $k$ is a positive integer.

I have worked through a proof of this assertion which can be broken down as follows:

1. It is clear that $1,2,4$ each have a primitive root.
2. Higher powers of $2$ do not have a primitive root by induction.
3. If the modulus has an odd prime factor and the modulus has a primitive root, then the modulus is either a power of that prime or twice a power of that prime.
4. Every odd prime has a primitive root (using polynomials in modular arithmetic).
5. Primitive roots modulo a prime can be "lifted" to moduli that are higher powers of the prime.
6. Primitive roots in a modulus can be lifted to twice that modulus.

This is all well and good, but this proof just works towards the expected result using standard elementary techniques without providing much insight. I was wondering: Is there a deep reason for why the classification of suitable moduli is so strange? It's a natural question to wonder when a reduced residue system has a multiplicative generator, yet the set we end up with carves out an unexpected subset of the positive integers.

I don't entirely know what would qualify as a satisfactory answer, but some possibilities are:

• The set of integers $1,2,4,p^k,2p^k$ appears in other parts of mathematics.
• There is a more general theorem of which this is merely a shadow.
• There is a different proof that is less reminiscent of mechanical verification.

EDIT: I came across a couple of quotes that sum up my feelings.

What the standard proof is like, if I may exaggerate:

Well, I have slightly mixed feelings about [the classification of finite simple groups]. First of all, it takes so many pages to prove; it seems to me the degree of understanding must be pretty limited if that is the only way it can be done. - Michael Atiyah, The Mathematical Intelligencer

What I'm looking for:

Not only is the above combinatorial proof much shorter than our previous proof, but it also makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simpler combinatorial proof. - Richard Stanley, Enumerative Combinatorics I