Prove that 12 has no primitive root So I've got to prove that there exists no integer $a$ such that $a$ has order 4 mod 12. How can I do this?
EDIT: Can I just try every integer less 12 and co-prime to 12 i.e. 5,7,11
Why does it suffice to consider only integers less than 12?
 A: Yes, it would suffice to check that there is no positive integer less than $12$ that has order $4$. You ask about why it suffices to check only numbers less than $12$. Mechanically, this is because if $a \equiv b \pmod {12}$, then $a^k \equiv b^k \pmod {12}$, so that being equivalent mod $12$ completely determines behaviour. Intuitively, this is because there are only $12$ numbers mod $12$ (and only $4$ numbers in the multiplicative group $(\mathbb{Z}/\mathbb{Z}^{12})^\times)$.
As an aside, we consider this from a slightly more sophisticated point of view. We are trying to determine the structure of the group $\left(\mathbb{Z}/\mathbb{Z}^{12}\right)^\times$, which is sometimes denoted $U(12)$ or $U_{12}$, the group of units. This group consists of those elements relatively prime to $12$ under multiplication. There are $4$ elements, so asking whether any element has order $4$ is asking whether or not $U(12)$ is cyclic.
Determining the structures of the groups $U(n)$ is a fundamental question in the study of elementary number theory. It turns out that these groups are cyclic if and only if $n = 2, 4, p^k$ or $2p^k$ for odd primes $p$ and positive integers $k$. This is proved in most elementary number theory books and (likely) multiple times on this site.
A: Do you realize that checking $n$ has a primitive root or not is same as checking whether $U(n)$  is a cyclic group or not. 
Now is $U(n)$ cyclic? 
