How to find a primitive element for $\mathbb F_{11}$

Question

This is a pretty dumb question considering this is the very first question in my exercises (on a section about finite fields). First, the the group of units $\mathbb F_{11}^*$ is $\mathbb{Z}/10\mathbb{Z} = \{ 0,1, \ldots \}$ (it's not how it's defined but it's isomorphic ok). I know that I need to find an element $a$ of maximum order $n$ in $\mathbb{Z}/10\mathbb{Z}$ because then $\mathbb F_{11}^* = \mathbb{Z}/10\mathbb{Z} = \langle a \rangle$, so $a$ is a primitive root.

But I have no idea how to find such an element of maximum order. I can only think of brute force, which doesn't seem like a very efficient way to solve this. Can someone help me?

Answer 1

Pick a random member of the group, and test whether it is a primitive root. Repeat until you find one that is.

To test whether $a$ is a primitive root modulo $p$, test whether

$$a^{(p-1)/d} \equiv 1 \pmod p,$$

for each prime divisor $d$ of $p-1$ (such that $1<d<p-1$). If this equivalence holds for any $d$, then $a$ is not a primitive root. If it fails to hold for all $d$, then $a$ is a primitive root.

See https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots.

Answer 2

You can try the process of elimination.

$$\mathbb F_{11}^* = \{1, 2, \ldots, 10\}$$

Eliminate the identity and the obvious perfect powers (perfect squares and the perfect 5-th powers only because the order of this group is $2\times 5$) Also eliminate $10$ because it has an order of $2$. $10^2\equiv (-1)^2\equiv 1\pmod{11}\tag*{}$

The potential candidates for being generator are $2,3,5,6,7, 8\tag*{}$

$\mathbb F_{11}^*$ admits $\varphi(10)=4$ generators so in our last stage of elimination, exactly two of these numbers will be eliminated.

Claim 1: Either $5$ or $6$ is not a generator.

Hint: $6\equiv -5\pmod{11}$
If $x$ is a generator i.e., $\DeclareMathOperator{\ord}{ord}\ord(x)=10$ then $\ord(x^5)=2\implies x^5\equiv -1\implies (-x)^5\equiv 1\pmod{11}\tag*{}$ $\because$ $-1\pmod{11}$ is the only element of order $2$.

Claim 2: Likewise, either $8$ or $3$ is not a generator.

This means that $2$ must have been a generator (because $2$ is not among the candidates which will be potentially eliminated) and hence, $8=2^3$ is also a generator. Mind that this is true because $\text{gcd}(3,10)=1$.

Thus, $3$ is not a generator and $\ord(3)\neq 2, 10$ so the only divisor of $10$ which remains is $5$, so $\ord(3)=5$.

Now, $6^5=2^5\times \underbrace{3^5}_{\equiv 1} \equiv -1\pmod{11} \tag*{}$ Thus, $\ord(6)=10$ i.e., $6$ is also a generator and hence $5$ is not one.

The four generators of $\mathbb F_{11}^*$ are: $2,6,7, 8\tag*{}$

As suggested in the comments by user Jyrki Lahtonen:
In case, $p$ is prime such that $(p-1)/2$ is odd i.e., $p\equiv 3\pmod{4}$ and $x$ is a generator of $\mathbb F_p^*$ then $-x$ is not a generator.

Answer 3

For smaller primes, I usually follow one trick. If $a$ has to be a primitive root in $\mathbb{Z}_p$, then $a^{\frac{p-1}{2}}\equiv -1 \pmod p$( In other word $a$ is a quadratic non-residue modulo $p$. Need not worry if you aren't introduced to quadratic residues). There are always exactly $\frac{p-1}{2}$ elements in $\mathbb{Z}_p^{\star}$ which satisfy above congruence.

Further, there shall be $\varphi(p-1)$ primitive roots modulo $p$. These must be from these $\frac{p-1}{2}$ elements. Using these two, we can easily reduce the set of numbers for which the verification is needed. For instance:

In case of $p =11$, $\frac{p-1}{2}=5$ and there are exactly 5 elements in $\mathbb{Z}_{11}^\star$ that satisfy $a^5\equiv -1 \pmod {11}$. A primitive root must be one of these $5$ elements. As there are $\phi(10)=4$ primitive roots, $4$ out of the $5$ elements which satisfy above congruence must be primitive roots. Notice that $10$ which is $-1$ modulo $11$ is one element which satisfies above congruence. This is clearly not a primitive root as $o(10)=2$. Hence the primitive roots are all the remaining elements that satisfy $a^5\equiv 1 \pmod {11}$.

Quite clearly $2^5\equiv -1 \pmod {11}$ and hence it must be a primitive root modulo $11$. Once we get one primitive root, others can be easily found out, as others will be $2^3, 2^7, 2^9$ modulo $(11)$.

Answer 4

Generally speaking, there is no simple algorithm to find primitive root.

But in this particular case, it is easy: Each element of $a\in\mathbb F_{11}^\times$ has order $1, 2, 5$ or $10$. We already know $-1=10$ is the only element of order $2$ (in the multiplicative group of any field). Now pick a random element $a\in \mathbb F_{11}\setminus\{0, \pm 1\}$, if $a$ has order $10$, we're done, otherwise $a$ has order $5$, then $-a$ must have order $10$. Only one element needs to be tested.

For simplicity, pick $a=2$, $2^5=32=-1$, we're done.