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 \]

.