[Math] Show that $2$ is a primitive root modulo $13$.

elementary-number-theory

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

Best Answer

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

Related Question