What is the order of $x+x^2$ in Multiplicative group of the field $\mathbb F_2[x]/(x^4+x^3+1)$

Question

How do I find the order of this element? What should I use?

Answer 1

What I would do:

• The polynomial $x^4+x^3+1$ is of degree four, so your field has $2^4=16$ elements.

• The multiplicative group of the field has $15$ elements.

• The order of $x+x^2$ can thus be only $3$, $5$ or $15$. Try out calculating the cube and 5th degree of it (mod $x^4+x^3+1$) and you will know which one is right.

Answer 2

Put $\;t=x^2+x\;$ , then

$$\color{red}{t^2}=x^4+x^2=x^3+x^2+1\;,\;$$

$$\color{red}{t^4}=x^6+x^4+1=x^2(x^4)+x^3+1=$$

$$x^5+x^2+x^3+1=x(x^4)+x^3+x^2+1=x^4+x+x^3+x^2+1=$$

$$=x^3+1+x+x^3+x^2+1=x^2+x$$

Well, finish the argument.

Answer 3

If you want to simplify the calculations you can note that this is just group theory.

The elements $ax^3+bx^2+cx+d$ with $a,b,c,d\in \{0,1\}$ are all distinct. There are $15$ non-zero elements which make up the multiplicative group - so elements other than $1$ will have orders $3,5,15$.

Now let $y=x^2+x$ so that $x^2y+1=0$ or $x^2y=1$.

Now you can get away with computing the order of $x$ - since this is odd, it will be the same as the order of $x^2$ and $x^{-2}$ and hence of $y$.