Find an element of order $5$ of the field $\mathbb{Z}_3[x]/\langle x^4 + x + 2 \rangle$.

Question

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?

Answer 1

$x^4=-x+1$ in this field.

$x^{16}=(-x+1)^4=x^4-x^3-x+1=-x^3+x-1$.

As $(x^{16})^5=x^{80}=1$ then $-x^3+x-1$ has order $5$.

Answer 2

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