<s>[INST] Find an element of order $5$ of the field $\mathbb{Z}_3[x]/\langle x^4 + x + 2 \rangle$. Find an element of order $5$ of the field $\mathbb{Z}_3[x]/\langle x^4 + x + 2 \rangle$.
I tried the systematic method of considering
$$1=(ax^3 + bx^2 + cx + d)^5$$
and using the relation $x^4 = 2x+1$ but the algebra got messy. Any idea?
 [/INST] It is maybe good to know that the one or the other computer algebra system can deal systematically with computations in finite fields.
For instance, using sage, a small dialog with the sage interpreter detects all elements of multiplicative order $=5$, the code has a digestible mathematical syntax, that will be explained in the sequel:
sage: R.<X> = PolynomialRing( GF(3) )
sage: F.<x> = GF( 3^4, modulus=X^4+X+2 )

sage: F.multiplicative_generator()
x
sage: F.multiplicative_generator().multiplicative_order()
80

sage: for k in [ 16, 32, 48, 64 ]:
....:     print ( "x^%s = %s is an element of multiplicative order %s"
....:             % (k, x^k, (x^k).multiplicative_order() ) )
....:     
....:     
x^16 = 2*x^3 + x + 2 is an element of multiplicative order 5
x^32 = x^3 + 2*x^2 + 2 is an element of multiplicative order 5
x^48 = 2*x^2 + 2*x + 2 is an element of multiplicative order 5
x^64 = 2*x^2 + 2 is an element of multiplicative order 5

sage: [ y for y in F if not y.is_zero() and y.multiplicative_order() == 5 ]
[2*x^3 + x + 2, x^3 + 2*x^2 + 2, 2*x^2 + 2*x + 2, 2*x^2 + 2]

We have solved twice, without complications...
Comments for the code. Above, we have first initialized the ring $R=\Bbb F_3[X]$, since we need the "modulus" $X^4+X+2$, we construct $F=\Bbb F_3[X]/(X^4+X+2)$, this is a field with $3^4=81$ elements, then the group of its non-zero elements (with the multiplication) is a group of order $80$, it is cyclic, a generator is $x$, given by sage. (Of course, $y^{80}=1 for all $y\in F$, $y\ne 0$.)
Knowing it, we expect that all elements of order $5$ are of the shape
$$
x^{16k}\ ,\qquad k=1,2,3,4\ .
$$
The code asks for the explicit representation of these elements, checks also their multiplicative order.
One can also use the one-liner [ y for y in F if not y.is_zero() and y.multiplicative_order() == 5 ] to get them in an unstructural way.
Not needed, but to do something concrete in the direction of a human effort, let us check for instance (humanly) that the last element, $2(x^2+1)=-(x^2+1)$ has order $5$, computations get simpler if we use the Frobenius, so...
$$
\begin{aligned}
(-(x^2+1))^5
&=-(x^2+1)^5
=(?)\ ,
\\
&\qquad\text{ so let us start with a related expression}\dots
\\[2mm]
(x^2+1)^6
&=(x^2+1)^3(x^2+1)^3
\\
&=(x^6+1)(x^6+1)
\\
&=x^{12}-x^6+1
\\
&=(x^4)^3-x^4\cdot x^2+1
\\
&=(1-x)^3-(1-x)\cdot x^2+1
\\
&=(1-x^3)-(x^2-x^3)+1
\\
&=-(x^2+1)\ ,\qquad\text{ so}
\\[2mm]
-(x^2+1)^5 
&= 
1\ .
\end{aligned}
$$
</s>