which Numbers can have primitive roots?

Question

I know that if $(a,n)=1,n>0$ and $a^{ϕ(n)}≡1\pmod n$, i.e, order of a $\bmod n$ is $ϕ(n)$, then $a$ is called the primitive root modulo $n$.

I want to know what are the possible values of $n$, i.e, which integers can have primitive roots?

Is there any rule that only certain integers can have primitive roots?

I also realised that $n$ cannot be only prime, as $3^2≡1\pmod 4$, so that $n=4$ and $ϕ(4)=2$.

Sorry for such a basic question, but any help would be appreciated :)

Answer 1

The natural numbers which have a primitive root are exactly the following numbers: $2,4$, powers of an odd prime and $2$ times a power of an odd prime.