How to find order of all the elements in GF(19) and indicate those which are primitive elements?

Question

As the GF(19) gets pretty lengthy by just writing each element in terms of each element powers, is there any other method to solve this?

Answer 1

Essentially, brute force is the only method. There is no fast algorithm for finding primitive roots. But you don't have to calculate for every element separately. Start with the powers of $2$. If you happen to get $18$ different values before reaching $1$ you're done, since you have a generator of that cyclic group ( a primitive root). If not, then pick an element you don't see and work with it.

For example, using the residue system $(-9, 10)$ (so that i never deal with big numbers) the powers of $2$ are $$ 2, 4, 8, 16 \equiv -3, -6, -12 \equiv 7, 14 \equiv -5, -10 \equiv 9, 18 \equiv -1. $$ Having found the first $9$ powers and not seeing $1$ means $2$ is a primitive root. Then the other primitive roots are $2^a$ when $\gcd(a,18) = 1$ and it's easy to find the orders of everything else too.

Answer 2

So to find the order of each element I have no choice but to calculate it for all the 18 elements?

Not exactly: you have to find a primitive element $a$. All elements in $\mathbf F_{19}^\times$ are a power $a^k$. Now the order of $a^k$ is $$\operatorname{ord}(a^k)=\frac{\operatorname{ord} a}{\gcd(k,\operatorname{ord}a)},$$ so $a^k$ is also a primitive element if and only if $k$ is coprime to $\operatorname{ord}a=18$, i.e. $k$ is one of $\:1,5,7,11,13,17$.

Trying with $2$, we compute its first powers $\bmod 18$. As its order is a divisor of $18$, we only have to compute its powers up to $9$: if its order is $>9$, it is equal to $18$. Indeed, we have this table of the relevant powers of $2$: \begin{matrix} k&2&3&6&9\\ \hline 2^k&4&8&64\equiv7&8\cdot 7\equiv-1 \end{matrix} so $2$ is a primitive element, and the other primitive elements are $$2^5=32\equiv \color{red}{13},\;2^7\equiv 13\times4\equiv\color{red}{14},\; 2^{11}\equiv 13^2\cdot2\equiv-4\equiv\color{red}{15},\;2^{13}\equiv -4^2=\color{red}{3},\;2^{17}\equiv3\cdot16\equiv \color{red}{10}.$$

Answer 3

The orders of elements are $1,3,9,2,6,18$. There are equal numbers of elements of odd and even order. Every element of odd order is a square.

Note that $-1$ is the only element of order $2$. If $a$ has odd order $r$, then $(-a)^r=-1$ and $-a$ has order $2r$.

So we compute the squares $1,4,9,16, 25=6, 36=17, 49=11, 64=7, 81=5$ hence $1,4,5,6,7,9,11,16,17$

Now squares have odd order, so order $1, 3, 9$. There is one element of order $1$ and two of order $3$ and six of order $9$. Identify which have order $3$ and you know them all. Their negatives have double the order. You can do this directly by cubing to identify $7$ and $11$ as the elements of order $3$. Another way to do this is to compute the cubes (there are six of these since $18$ is divisible by $3$) ie $\pm 1, \pm 8, (\pm 27=\pm 8), \pm 64=\pm 7$ or $1,7,8,11,12,18$. The cubes have orders $1,2,3,6$ one each of order $1$ and $2$, and two elements of order $3$ and two elements of order $6$.

This identifies $7$ and $11$ as being the elements of order $3$ (comparing with the list of squares)

So order $1$: $1$

Order $2$: $-1=18$

Order $3$: $7; 11$

Order $6$: $-7=12; -11=8$

Order $9$ (the squares not yet listed): $4; 5; 6; 9; 16; 17$

Order $18$ (primitive roots):$2; 3; 10; 13; 14; 15$

I think this is the kind of thing you mean.

---

Alternatively you can work as follows:

It is pretty obvious that $4^3 \neq 1$, so $4$ must have order $9$ and its negative $-4=15$ must be a primitive root (order $18$).

Now also $(-2)^2$ has order $9$ and $-2=17$ is a square, so $-2$ has order $9$ and $2$ has order $18$.

and continue until you have enough information.

---

To get the numbers of elements of each order note that the multiplicative group here is cyclic and has one subgroup of each order which divides the order of the group.

Alternatively factorise $$x^{18}-1=(x^9+1)(x^9-1)=(x^3+1)(x^6-x^3+1)(x^3-1)(x^6+x^3+1)=$$$$=(x+1)(x^2-x-1)(x^6-x^3+1)(x-1)(x^2+x+1)(x^6+x^3+1)$$ and note that the factors belong to elements of degrees $2;6;18;1;3;9$ respectively.

You can identify the elements of order $3$ therefore as roots of $x^2+x+1=0$ or $4x^2+4x+4=(2x+1)^2+3=0$. Now $-3=16$ is a square and $$2x+1=\pm 4; x=\frac 32=11 \text { or } x=-\frac 52=7$$

I spotted this much later, but if I had caught it earlier, I could have worked out all the orders by computing the squares and solving this one quadratic.

Note that you don't have to do the full factorisation to identify the quadratic for the cubes - just identify the factor $x^3-1= (x-1)(x^2+x+1)$