Find the minimal polynomial of $a^i \in F_{16}$, for all $1 \leq i \leq 14$

Question

Let $\alpha$ be a root of $1+x^3+x^4 \in F_2[x]$. Find the minimal polynomial of $a^i \in F_{16}$, for all $1 \leq i \leq 14$.

I have been self studying algebra and the idea of minimal polynomials has me confused.

Answer 1

Since $\alpha$ is a root of $1+x^3+x^4$, we know that $1+\alpha^3+\alpha^4=0$. Let's try to find a minimal polynomial for $\alpha^2$. Let's use $\beta=\alpha^2$:

Then, since $\mathbb{F}_{16}$ is characteristic $2$ (since $16$ is a power of $2$), let's compute what we can: \begin{align*} \beta&=\alpha^2\\ \beta^2&=\alpha^4=1+\alpha^3\\ \beta^3&=\alpha^6=\alpha^2+\alpha^5=\alpha^2+\alpha(1+\alpha^3)=\alpha+\alpha^2+\alpha^4=\alpha+\alpha^2+(1+\alpha^3)=1+\alpha+\alpha^2+\alpha^3\\ \beta^4&=\alpha^8=\alpha^2(1+\alpha+\alpha^2+\alpha^3)=\alpha^2+\alpha^3+\alpha^4+\alpha^5=\alpha^2+\alpha^3+(1+\alpha^3)+\alpha(1+\alpha^3)\\ &=\alpha^2+\alpha^3+1+\alpha^3+\alpha+\alpha^4=1+\alpha+\alpha^2+\alpha^4=1+\alpha+\alpha^2+(1+\alpha^3)=\alpha+\alpha^2+\alpha^3 \end{align*} Observe that $\beta^4+\beta^3=1$, so $\beta$ also satisfies $x^4+x^3+1=0$.

Let's now consider $\gamma=\alpha^3$:

\begin{align*} \gamma&=\alpha^3\\ \gamma^2&=\alpha^6=\alpha^2(\alpha^4)=\alpha^2(1+\alpha^3)=\alpha^2+\alpha(\alpha^4)=\alpha^2+\alpha(1+\alpha^3)=\alpha+\alpha^2+\alpha^4=1+\alpha+\alpha^2+\alpha^3\\ \gamma^3&=\alpha^9=\alpha(\alpha^4)^2=\alpha(1+\alpha^3)^2=\alpha(1+\alpha^6)=\alpha+\alpha^7=\alpha+\alpha^3(\alpha^4)=\alpha+\alpha^3(1+\alpha^3)\\ &=\alpha+\alpha^3+\alpha^2(\alpha^4)=\alpha+\alpha^3+\alpha^2(1+\alpha^3)=\alpha+\alpha^2+\alpha^3+\alpha(\alpha^4)=\alpha+\alpha^2+\alpha^3+\alpha(1+\alpha^3)\\ &=\alpha^2+\alpha^3+\alpha^4=1+\alpha^2\\ \gamma^4&=\alpha^{12}=(\alpha^4)^3=(1+\alpha^3)^3=1+\alpha^3+\alpha^6+\alpha^9=1+\gamma+\gamma^2+\gamma^3 \end{align*} Therefore, $\gamma$ satisfies $x^4+x^3+x^2+x+1=0$.

If you want to construct the polynomials in an elementary way, compute the powers and then use linear algebra to find the minimal polynomial by trying to eliminate the higher powers of $\alpha$. At every point, you only need to compute up to power $4$.

Answer 2

Every nonzero element of $\mathbb{F}_{16}$ is a root of $x^{15}-1$.

We have this factorization into irreducibles mod $2$: $$ x^{15}-1=(x + 1) (x^2 + x + 1) (x^4 + x + 1) (x^4 + x^3 + 1) (x^4 + x^3 + x^2 + x + 1) $$

The multiplicative order of $\alpha^i$ is $15/\gcd(15,i)$.

Elements of order $1$ have minimal polynomial $x+1$.

Elements of order $3$ have minimal polynomial $x^2 + x + 1$ because $$ x^{3}-1=(x + 1) (x^2 + x + 1) $$

Elements of order $5$ have minimal polynomial $x^4 + x^3 + x^2 + x + 1$ because $$ x^{5}-1=(x + 1) (x^4 + x^3 + x^2 + x + 1) $$ Elements of order $15$ have minimal polynomial $x^4 + x + 1$ or $x^4 + x^3 + 1$ because it's what is left.

Answer 3

Adding a trick not mentioned in the other answers as well as comments on how to best apply them to the task at hand.

1. The use of the Frobenius automorphism $z\mapsto z^2$ is surprisingly powerful here, see Arthur's comment under the OP. Because we have $(u+v)^2=u^2+v^2$ for all $u,v\in\Bbb{F}_{16}$, it follows that $\alpha,\alpha^2,\alpha^4$ and $\alpha^8$ all share the same minimal polynomial $x^4+x^3+1$. Observe that as $\alpha^{15}=1$, we get that $\alpha^{16}=\alpha$, so it is pointless to add $\alpha^{16}$ to that list - it already is there (consequently so are $\alpha^{32}=\alpha^2$ et cetera). This is just as well, because as $x^4+x^3+1$ is of degree four, we should expect it to only have four zeros.
2. As pointed out in lhf's answer, the element $\alpha^3$ is of order $5=15/\gcd(3,15)$. Therefore it must be a zero of $(x^5-1)/(x-1)=x^4+x^3+x^2+x+1$ that we easily see to be irreducible, and hence the minimal polynomial of $\alpha^3$. Reusing the Frobenius trick we see that $(\alpha^3)^2=\alpha^6$ shares this same minimal polynomial with $\alpha^3$. As do $(\alpha^3)^4=\alpha^{12}$ and $(\alpha^3)^8=\alpha^{24}=\alpha^9$. Again, a quartic polynomial with four zeros. Also observe that with all the exponents $e=3,6,9,12$ we have $\gcd(e,15)=3$, and therefore $\alpha^e$ is of order $15/\gcd(e,15)=5$.
3. The lowest power of $\alpha$ not yet covered is $\alpha^5$. This has order $15/\gcd(5,15)=3$, so must be a zero of $(x^3-1)/(x-1)=x^2+x+1$. This time the Frobenius trick shows that $(\alpha^5)^2=\alpha^{10}$ shares this minimal polynomial with $\alpha^5$. Observe that this the Frobenius trick stops here. You see that $(\alpha^{10})^2=\alpha^{20}=\alpha^5$. Again, perfectly fitting the fact that the minimal polynomial is a quadratic. It is uncertain whether the following makes sense to you, but I just add that the shorter cycles we get by applying the Frobenius automorphism are due to the fact that $\alpha^{5}$ and $\alpha^{10}$ belong to the subfield $\Bbb{F}_4$ sitting inside $\Bbb{F}_{16}$.
4. The lowest power not yet covered is $\alpha^7$. Reusing the Frobenius idea we see that $\alpha^7$ shares the minimal polynomial with $(\alpha^7)^2=\alpha^{14}$, $\alpha^{28}=\alpha^{13}$ and $\alpha^{56}=\alpha^{11}$. But what's the minimal polynomial? You can apply Michael Burr's technique to brute force it, but I'll show you a trick. We see that $\alpha^{14}=\alpha^{15-1}=\alpha^{-1}$. How to take advantage? We have the equation $$\alpha^4+\alpha^3+1=0.$$ If we divide that by $\alpha^4$ we get $$0=\frac{\alpha^4+\alpha^3+1}{\alpha^4}=1+\alpha^{-1}+\alpha^{-4}.$$ This shows that $\alpha^{-1}$ is a zero of the quartic $1+x+x^4$. Because $\alpha^{-1}$ shares its minimal polynomial with a total of four elements, its minimal polynomial must have degree four, so we have just found it.

This completes the list. All the powers $\alpha^i,1\le i\le14,$ were accounted for. The trick in item 4 is known as using the reciprocal polynomial. If $z\neq0$ is a zero of some polynomial $p(x)$ of degree $n$, then $1/z$ is a zero of the reciprocal polynomial $$ \tilde{p}(x)=x^np(\frac1x), $$ also of degree $n$.