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$?


$\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).
