Show that $2$ is a primitive root modulo $13$. Find all primitive roots modulo $13$.

We show $2$ is a primitive root first. Note that $\varphi(13)=12=2^2\cdot3$. So the order of $2$ modulo $13$ is $2,3,4,6$ or $12$.
\begin{align}
2^2\not\equiv1\mod{13}\\
2^3\not\equiv1\mod{13}\\
2^4\not\equiv1\mod{13}\\
2^6\not\equiv1\mod{13}\\
2^{12}\equiv1\mod{13}
\end{align}
Hence $2$ has order $12$ modulo 13 and is therefore a primitive root modulo $13$. 
Now note all even powers of $2$ can't be primitive roots as they are squares modulo $13$. $(*)$
There are $\varphi(12)=4$ primitive roots modulo $13$. These must therefore be
$$2,2^5=6,2^7=11,2^{11}=7\mod{13}.$$

Questions:


*

*Why do we only check the divisors of $\varphi(13)$ lead to $1\mod{13}$?

*does the line marked $(*)$ mean they can be written in the form $a^2$? Why does this mean they can't be a primitive root?

*I thought $\varphi(12)$ counts the number of coprimes to $12$.. Why does this now suddenly tell us the number of primitive roots modulo $13$?

*How have these powers been plucked out of thin air? I understand even powers can't be primitive roots, also we have shown $2^3$ can't be a primitive root above but what about $2^9$?

 A: 1 .  This is Lagrange's theorem.  If $G$ is the group $(\mathbb{Z}/13\mathbb{Z})^{\ast}$ (the group of units modulo $13$), then the order of an element $a$ (that is, the smallest number $t$ such that $a^t \equiv 1 \pmod{13}$) must divide the order of the group, which is $\varphi(13) = 12$.  So we only check the divisors of $12$.
2 .  Yes, that is a square mod $13$.  To say that $a$ is a primitive root mod $13$ means that $a^{12} \equiv 1 \pmod{13}$, but all lower powers $a, a^2, ... , a^{11}$ are not congruent to $1$.  Again use Lagrange's theorem: supposing $a^2$ were a primitive root, then $12$ would be the smallest power of $a^2$ such that $(a^2)^{12} \equiv 1$.  But note that $b^{12} \equiv 1$ for ANY integer $b$ not divisible by $13$.  So $(a^2)^{6} = a^{12} \equiv 1$, and $6 < 12$, contradiction.
3 .  It's a general result about finite cyclic groups.  A cyclic group of order $m$ is a group of the form $H = \{ 1, g, g^2, ... , g^{m-1}\}$.  It is basically the same thing as the group $\mathbb{Z}/m\mathbb{Z}$ with respect to addition.  In general, if $d \geq 1$, there exist elements in $H$ with order $d$ (that is, their $d$th power is $1$, all lower powers are not $1$) if and only if $d$ is a divisor of $m$, and there are exactly $\varphi(d)$ such elements.
In particular, if $p$ is an odd prime number, the result is that $(\mathbb{Z}/p\mathbb{Z})^{\ast}$ is a cyclic group of order $\varphi(p) = p-1$, and the number of primitive roots (that is, the number of elements with order $p-1$) is exactly $\varphi(p-1) = \varphi(\varphi(p))$.
4 .  If you have found a primitive root modulo $p$ (where $p$ is an odd prime), then you can easily find the rest of them: if $a$ is a primitive root mod $p$, then the other primitive roots are $a^k$, where $k$ runs through those numbers which don't have any prime factors in common with $p-1$.  It's a good exercise to prove this.  So $2^9$ wouldn't work; $9$ has prime factors in common with $12$.  
A: $\varphi(13)=12$, and by Fermat's Little Theorem, $a^{12}\equiv1\mod13$.
We can split the numbers less than $12$ into two groups - those co-prime to $12$, namely $1,5,7,11$, and those such that $\gcd(x,12)\gt1$, namely $2,3,4,6,8,9,10$.
To explain (1), (2) and (4), we can see that if an integer $d$ belongs to the second group and is also a divisor of $12$, then if $a^d\equiv1\mod13$ then so is $a^{kd}\equiv 1\mod13$ for $k=12/d$.
The non-divisors of $12$ do not have this feature, if $f$ is such a number then $a^{kf}\equiv1\mod13$ for the first time when $k=12$ (by elementary number theory), which answers (3).
