# 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:

1. Why do we only check the divisors of $\varphi(13)$ lead to $1\mod{13}$?
2. 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?
3. 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$?
4. 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$?

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

• For $1)$ you don't need Lagrange's Theorem. If $a^k\equiv 1\pmod{n}$, then $\text{ord}_n(a)\mid k$ follows easily by a proof by contradiction: if $k=\text{ord}_n(a)t+r$ for some $0<r<\text{ord}_n(a)$, you'll get $a^r\equiv 1\pmod{n}$ and a contradiction. – user236182 Feb 22 '16 at 17:51
• A quick comment: Can we say $a$ is a primitive root mod $p$ if $${\rm ord}(a)=\varphi(p)=p-1$$ – user2850514 Feb 22 '16 at 18:09
• @user2850514 Yes. $a$ is a primitive root mod $n$ if and only if $\text{ord}_n(a)=\phi(n)$. It's basically the definition of a primitive root. – user236182 Feb 22 '16 at 18:57

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