Conditions on a Modulus for a Primitive Root to Exist
Any integer which can be expressed as the product of two divisors greater than 2 which are relatively prime and does not have a primitive root.
Proof
Let the integer in question be
\[mn, \; m, \; n \gt 2, \; gcd(m,n)=1\]
.Choose
\[a\]
relatively prime to \[mn\]
we have to show \[a^k \equiv 1 \; (mod \; mn)\]
for some \[0 \lt k \lt \phi (mn)\]
.\[m, \;n\]
are odd, so \[\phi (m), \; \phi (n)\]
are both even.\[gcd(a,m)=1 \rightarrow gcd(a,m)=1 \rightarrow a^{\phi (m)} \equiv 1 \; (mod \; m)\]
from Euler's Theorem.
Let
\[k = \frac{1}{2} \phi (mn)\]
.\[a^k = a^{\frac{1}{2} \phi (mn)}=(a)^{\phi (m)})^{\frac{1}{2}\phi (n)} \equiv 1^{\frac{1}{2}\phi (n)} \; (mod \; m) \equiv 1 \; (mod \; m)\]
The same argument hold with the roles of
\[m, \; n\]
interchanged. so there is no primitive root modulo \[mn\]
, and the theorem is proved.The theorem implies that primitive roots only exist modulo n if n takes one of the forms
\[n=p^k, \; 2p^k, \; k \ge 1 \]
. 
