Prove that Carmichael number has no primitive roots

Question

Prove that if $n$ is a Carmichael number, then $n$ has no primitive roots. This seems tricky to prove, and the only logical explanation for this is that it contradicts the basis of the Lucas Primality Test, but again that is not proving the original statement.

Answer 1

You can prove this quite quickly using the classification of numbers with primitive roots: $n$ has a primitive root iff $n$ is $2$, $4$, or of the form $p^k$ or $2p^k$ for $p$ an odd prime. So you just have to check that these are not Carmichael. This is easy: any Carmichael number is odd, so you only have to check the case $n=p^k$. In that case, if $a$ is a primitive root, $a^n=a$ mod $n$ implies $n-1=p^k-1$ is divisible by $\phi(n)=(p-1)p^{k-1}$, which is impossible for $k>1$.

Answer 2

This is not tricky to prove, because a Carmichael number is a square-free number with at least three (different) prime factors, so it obviously does not have the form which admits primitive roots: $2, 4, p^k, 2p^k$ with an odd prime $p$.