For $f(x) = x^4 + x + 1 \in F_2[x]$ . Let $a \in F_{16}$ be a root of $f$.
How can I find the multiplicative order of $a$ and $a^2+a+1$
My attempt:
$f$ clearly has not root in $F_2$ so if it is reducible it must be reduced to polynomials of degree 2. Then by considering the only few cases we see that $f$ is irreducible. Now since $a\in F_{16}$ and the multiplicative group of $ F_{16}$ has only 15 elements we deduce that the order of $a$ is one of $3,5,15$ and it cannot be 3 since the minimal polynomial is of degree 4 so it can only be 5 and 15, from there I cannot continue and for $a^2+a+1$ I have no idea
Any help would be much appreciated
Thanks
Best Answer
Since $x^4+x+1$ is irreducible over $\mathbb{F}_2$ the roots of $x^4+x+1$ in $\mathbb{F}_{16}\simeq \mathbb{F}_2[x]/(x^4+x+1)$ are of the form $a,a^2,a^4,a^8$. Since $a$ is a root of $x^4+x+1$ we have $a^4=-a-1=a+1$. We cannot have $a^3=1$ or $a^5=1$ since $x^3-1$ and $x^5-1$ share no common factor with $x^4+x+1$ over $\mathbb{F}_2$. It follows that the multiplicative order of $a$ is $15$. Similarly $$(a^2+a+1)^3 \equiv 6a^3+2a^2-6a-5 \pmod{a^4+a+1} $$ implies that the multiplicative order of $a^2+a+1$ is three. As a brute-force alternative, since $16$ elements are not that much, we may just list the elements of $\mathbb{F}_{16}^*$ as the group generated by $a$:
$$ 1,a,a^2,a^3,a^4,a+1,a^2+a,a^3+a^2,a^3+a+1,a^2+1,a^3+a,\color{red}{a^2+a+1},a^3+a^2+a,a^3+a^2+a+1,a^3+a^2+1,a^3+1$$ we get $a^2+a+1 = a^{10}$ and the same conclusion as before.