# Multiplicative order of element in field extension

Let $$F_n$$ be the field with $$n=2^k$$ elements. Let $$K_{16}=K_2(\alpha)$$.

1. Which multiplicative orders are possible for $$\alpha$$?
2. How many such $$\alpha$$ do exist?

Here are my thoughts:

1. The multiplicative groups of $$K_{16}$$ has $$15$$ elements, so only $$3,5,15$$ are candidates for the order of $$\alpha$$. Since the degree of the field extension must be $$4$$ I can rule out $$3$$ as a candidate.
2. Since the degree of the field extension must be $$4$$ I looked at the irreducible polynomials of degree 4 over $$K_2$$ of which I found 4, so there are at most 16 such $$\alpha$$.

I did not manage to get any further. I would be really grateful for input. Only related question I found is Order of element in field extension

Assuming $$\ K_{2^n}\$$ is the finite field $$\ F_n\$$ of order $$\ 2^n\$$, then $$\ K_{16}\$$ is the splitting field of the polynomial $$\ x^{16}-x\$$ over $$\ K_2\$$. According to Wolfram alpha, the factorisation of $$\ x^{16}-x\$$ into irreducible factors over $$\ K_2\$$ is \begin{align} x(x+1)(x^2+x+1)&(x^4+x+1)\\ &(x^4+x^3+1)(x^4+x^3+ x^2+x+1)\ , \end{align} so there are only $$3$$, not $$4$$, irreducible polynomials of degree $$4$$ over $$\ K_2\$$. Since $$\ K_{16} = K_2(\alpha)\$$ if and only if $$\ \alpha\$$ is a root of any of those $$3$$ irreducible polynomials, the total number of such $$\ \alpha\$$ is $$12$$. The polynomials, $$\ x^4+x+1\$$ and $$\ x^4+x^3+1\$$ are both primitive, so all their roots have multiplicative order $$15$$, and since $$\ (x+1)(x^4+x^3+ x^2+x+1)=x^5+1\$$, all the roots of $$\ x^4+x^3+ x^2+x+1\$$ have multiplicative order $$5$$.

• First of all thanks very much, I have a question though: How can I be sure that there are really 12 distinct $\alpha$?
– GEO
Commented Oct 21, 2019 at 8:16
• To make my question more precise: How can I be sure the two primitive polynomials do not share roots? What about the non primitive polynomial? Is there some trick to quickly observe that those two polynomials are primitive?
– GEO
Commented Oct 21, 2019 at 8:27
• The most direct (if tedious) way of showing that no two of the polynomials share a root is to compute their gcd over $\ K_{16}\$. If $\ \alpha$ were a common root, then the gcd would have to be a multiple of $\ x-\alpha\$, but every pair of the listed factors of $\ x^{16}-x\$ has gcd $1$. A more civilised proof is to observe that every element $\ \alpha\$ of $\ K_{16}\$ satisfies the equation $\ \alpha^{16}=\alpha\$, so all sixteen distinct elements of $\ K_{16}\$ are roots of the polynomial $\ x^{16} -x\$, and since this polynomial has degree $16$, none of the roots can be repeated. Commented Oct 21, 2019 at 9:11
• How would you prove the two mentioned polynomials are primitive?
– GEO
Commented Oct 21, 2019 at 9:15
• An irreducible polynomial of degree $\ n\$ over $\ K_2\$ is primitive if $\ 2^n-1\$ is the smallest value of $\ m\$ such that the polynomial divides one of the form $\ x^m-1\$. Here, $\ m\$ can only be $3$, $5$ or $15$. Clearly, none of the degree $4$ polynomials can divide $\ x^3-1\$, and \begin{align} x^5-1&= x(x^4+x+1)+x^2+x+1\\ &=x( x^4+x^3+1)+ x^3+x\ , \end{align} so neither of the polynomials $\ x^4+x+1\$ or $\ x^4+x^3+1\$ divides $\ x^5-1\$. Commented Oct 21, 2019 at 9:37