4
$\begingroup$

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$?
$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user236182 Feb 22 '16 at 17:51
  • 1
    $\begingroup$ A quick comment: Can we say $a$ is a primitive root mod $p$ if $${\rm ord}(a)=\varphi(p)=p-1$$ $\endgroup$ – user2850514 Feb 22 '16 at 18:09
  • 1
    $\begingroup$ @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. $\endgroup$ – user236182 Feb 22 '16 at 18:57
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.