abstract-algebrafield-theoryfinite-fieldsirreducible-polynomials
Show that each monic irreducible polynomial of $\mathbb{F}_q[x]$ of degree $m$ is the minimal polynomial of some element of $\mathbb{F}_{q^m}$ with respect to $\mathbb{F}_q$ .
Using theorem, find all the irreducible polynomials of degree 4 over F2. (Let α be a root of 1 + x^3 + x^4 ∈ F2[x].)
In general, you can find the minimum polynomial for an algebraic number $\alpha$ by determining the smallest power of $\alpha$ for which $\{1,\alpha,\alpha^2,\ldots,\alpha^n\}$ is linearly dependent over $\mathbb{Q}$.
For example, let $\alpha=\sqrt{2} + \sqrt{3}$. Then \begin{align*} \alpha^2 &= 5+2\sqrt{6} \\\ \alpha^3 &= 11\sqrt{2}+9\sqrt{3} \\\ \alpha^4 &= 49+20\sqrt{6} \end{align*} Since $\{1,\sqrt{2},\sqrt{3},\sqrt{6}\}$ are linearly independent over $\mathbb{Q}$, we can think of the powers of $\alpha$ as vectors: $$ 1 = \begin{bmatrix}1\\\ 0\\\ 0\\\ 0\end{bmatrix}, \qquad \alpha = \begin{bmatrix}0\\\ 1\\\ 1\\\ 0\end{bmatrix}, \qquad \alpha^2 = \begin{bmatrix}5\\\ 0\\\ 0\\\ 2\end{bmatrix}, \qquad \alpha^3 = \begin{bmatrix}0\\\ 11\\\ 9\\\ 0\end{bmatrix}, \qquad \alpha^4 = \begin{bmatrix}49\\\ 0\\\ 0\\\ 20\end{bmatrix} $$ As you can see, $\{1,\alpha,\alpha^2,\alpha^3\}$ is linearly independent, so $\alpha$ is not the root of any cubic polynomial. However, $\{1,\alpha,\alpha^2,\alpha^3,\alpha^4\}$ is linearly dependent, with $$ \alpha^4 - 10\alpha^2 + 1 \;=\; 0 $$ It follows that $x^4-10x^2+1$ is the minimum polynomial for $\alpha$.
This technique depends on being able to recognize a useful set of linearly independent elements like $\{1,\sqrt{2},\sqrt{3},\sqrt{6}\}$. Depending on how much Galois theory you know, it may be hard to prove that elements like this are linearly independent over $\mathbb{Q}$. In this case, you can use this technique to guess the minimum polynomial, and then prove that you are correct by proving that the polynomial you found is irreducible.
For example, if $\alpha = i\sqrt[4]{2}$, then $$ \alpha^2 = -\sqrt{2},\qquad \alpha^3 = -i\sqrt[4]{8},\qquad \alpha^4 = 2. $$ It seems clear that $ \{1,\alpha,\alpha^2,\alpha^3\} $ is linearly independent, while $\{1,\alpha,\alpha^2,\alpha^3,\alpha^4\}$ satisfies $\alpha^4-2 = 0$. Thus $x^4-2$ should indeed be the minimum polynomial over $ \mathbb{Q} $, though the easiest way to prove it is to show that $x^4 -2$ is irreducible. This can be done using Eisenstein's criterion, or by checking that $ x^4-2 $ has no roots and does not factor into quadratics modulo $4$.
Here are three ways to prove that the degree of $\zeta_{12}$ over $\Bbb{Q}$ is not 2. Two of them will actually prove to you that the degree of this over the rationals is actually 4.
$\textbf{Approach 1:}$ Let's do this in a very simple way and try to determine the degree of $\zeta_{12}$ over $\Bbb{Q}$. Notice that
$$\Bbb{Q}(\zeta_{12}) \cong \Bbb{Q}(\sqrt{3},i) \cong \left(\Bbb{Q}(\sqrt{3})\right)(i). $$
Now the degree of $i$ over $\Bbb{Q}$ is 2 because the minimal polynomial of $i$ over $\Bbb{Q}$ is $x^2 +1$. Now we show that the degree of $\sqrt{3}$ over $\Bbb{Q}(i)$ is two as well. We already have a polynomial with coefficients in $\Bbb{Q}(i)$ with $\sqrt{3}$ as a root, namely the polynomial $x^2 - 3$. Now suppose that this polynomial is reducible, meaning that $\sqrt{3} \in \Bbb{Q}(i)$. Then we get that since as a vector space over $\Bbb{Q}$, $\Bbb{Q}(i)$ is two dimensional we can write
$$\sqrt{3} = a + bi$$
for some $a,b \in \Bbb{Q}$. Then squaring both sides we get that $3 = a^2 - b^2 + 2abi$ and hence that $$\frac{3 - a^2 + b^2}{2ab} = i$$
in particular that $i$ is real. This is a contradiction so that the polynomial $x^2 - 3$ is irreducible, and hence that $[\Bbb{Q}(\sqrt{3},i) : \Bbb{Q}(i)] = 2$. It follows by the dimension counting formula that $[\Bbb{Q}(\sqrt{3},i):\Bbb{Q}] = 2 \times 2 = 4$ and hence the degree of the minimal polynomial of $\zeta_{12}$ over $\Bbb{Q}$ must be 4 and you are right. Therefore if you have found a monic degree polynomial of degree 4 with $\zeta_{12}$ as a root, it must be the case that that polynomial is irreducible otherwise this would contradict our result that $[\Bbb{Q}(\zeta_{12}):\Bbb{Q}] = 4$.
$\textbf{Add-on to approach 1:}$ Suppose you did not know about cyclotomic polynomials (like me) and wanted to compute the minimal polynomial of $\zeta_12$ over $\Bbb{Q}$. You already know that it must be of degree 4 by the argument above. Once you find a monic one of degree 4, it must be unique by uniqueness of the minimal polynomial (exercise). Write
$$x = \frac{\sqrt{3} + i}{2}.$$
Then $2x = \sqrt{3} + i$ so that squaring both sides gives that $4x^2 = 3 - 1 + 2\sqrt{i}$ which implies that $4x^2 - 2 = 2\sqrt{3}i$. Hence
$$\begin{eqnarray*} 2x^2 - 1 &=& \sqrt{3}i\\ \implies 4x^4 - 4x^2 + 1 &=& -3 \\ \implies 4x^4 - 4x^2 + 4 &=& 0 \\ \implies x^4 - x^2 +1 &=& 0 \\ \end{eqnarray*}$$
and voilà! This is exactly the cyclotomic polynomial of degree 4 that you found.
$\textbf{Approach 2: Galois Theory}$ Suppose that $[\Bbb{Q}(\zeta_{12}) : \Bbb{Q}] = 2$. Then this is a degree 2 extension of a field of characteristic zero and hence is a Galois Extension. It follows that the Galois Group $ \operatorname{Gal}(\Bbb{Q}(\zeta_{12})/\Bbb{Q}) \cong C_2$, the cyclic group of order 2.
Now take some $\sigma \in G$. Then $\sigma$ must induce a permutation on the roots of the minimal polynomial of $\zeta_{12}$ over $\Bbb{Q}$. But then since $\sigma(\sqrt{3})^2 = \sigma(3) = 3$ which implies that $\sigma$ fixes $\sqrt{3}$ (similarly it fixes $i$) it follows that
$$\sigma(\zeta_{12}) = \zeta_{12}.$$
But then since $\sigma \in \operatorname{Gal}(\Bbb{Q}(\zeta_{12})/\Bbb{Q})$ was arbitrary this means that every $ \sigma \in \operatorname{Gal}(\Bbb{Q}(\zeta_{12})/\Bbb{Q})$ is the identity permutation so that $ \operatorname{Gal}(\Bbb{Q}(\zeta_{12})/\Bbb{Q})$ is the trivial group. But then this contradicts the fact that $ \operatorname{Gal}(\Bbb{Q}(\zeta_{12})/\Bbb{Q}) \cong C_2$ so it is not possible for $[\Bbb{Q}(\zeta_{12}):\Bbb{Q}]$ to be equal to 2.
$\textbf{Edit:}$ The proof above on Galois Theory is incorrect. Namely because it is not true that $\sigma(\sqrt{3}) = \sqrt{3}$ alone, but rather $\sigma(\sqrt{3}) = \pm \sqrt{3}$ and similarly for $\sigma(i)$.
$\textbf{Approach 3:}$ There is this result that is useful:
$$[\Bbb{Q}(\zeta_n) : \Bbb{Q}] = \varphi(n)$$
where $\varphi(n)$ is the Euler totient function. It counts the number of integers $k$ such that $1 \leq k \leq n$ with $k$ relatively prime to $n$. In your case, the integers relatively prime to 12 are $1,5,7,11$ which is $4$, exactly what you need.
Best Answer
Adding my bit with a view of covering the possibility (somewhat implied by OP's comments) that the task really is to find all the irreducible quartic polynomials over $\Bbb{F}_2$ using the theorem that they must all be factors of $p(x)=x^{16}-x$.
The given minimal polynomial of $\alpha$, $f_1(x)=x^4+x^3+1$ is obviously one of those. A useful trick for finding another one is to go to the so called reciprocal polynomial, i.e. $$ f_2(x)=x^4f_1(\frac1x)=x^4(\frac1{x^4}+\frac1{x^3}+1)=1+x+x^4. $$ We immediately see that $$ f_2(\frac1\alpha)=\alpha^4f_1(\alpha)=0, $$ so $f_2(x)$ is a multiple of the minimal polynomial of $1/\alpha$. As the elements $\alpha$ and $1/\alpha$ generate the same extension field, their respective minimal polynomials must be of the same degree. Therefore $f_2(x)$ is the minimal polynomial of $1/\alpha$ and is, thus also irreducible.
Let's take stock. We know that in addition to $f_1(x)$ and $f_2(x)$ the polynomial $p(x)$ is divisible by $q(x)=x^4-x$ (if you don't know how to deduce this from properties of finite fields, then you can just calculate that $q(x)^4+q(x)=p(x)$. Thus we know that $p(x)$ factors like $$ p(x)=q(x) f_1(x) f_2(x) r(x), $$ where $r(x)$ is some yet unknown factor. We can partially factor $p(x)$ directly as follows: $$ p(x)=x(x^{15}-1)=x(x^5-1)(x^{10}+x^5+1)=x(x-1)(x^4+x^3+x^2+x+1)(x^{10}+x^5+1), $$ and $q(x)$ as follows: $$ q(x)=x(x^3-1)=x(x-1)(x^2+x+1), $$ where that last quadratic factor is irreducible.
I leave it as an exercise for you to check that $$ (x^2+x+1)f_1(x)f_2(x)=x^{10}+x^5+1. $$ Putting all this together gives us that the mystery factor $r(x)=f_3(x)=x^4+x^3+x^2+x+1$. I next claim that $f_3(x)$ is irreducible. As it has no zeros in $\Bbb{F}_2$ it has no linear factors in $\Bbb{F}_2[x]$. It cannot be a product of two distinct quadratics, because then it should be a factor of $q(x)$. It cannot be the square of a quadratic, because then its zeros would not be simple, but $f_3(x)$ is a factor of $p(x)$ that has 16 distinct zeros.
Thus the list $f_1(x), f_2(x), f_3(x)$ is a complete list of irreducible quartics in $\Bbb{F}_2[x].$
Yet another way of deducing the irreducibility of $f_3(x)$ is to observe that $f_3(x)\mid x^5-1$, so its zeros are fifth roots of unity. If you are familiar with the cyclicity of the multiplicative groups of finite fields, then you can immediately check that $\Bbb{F}_{16}$ has no proper subfields containing primitive fifth roots of unity. Therefore the minimal polynomial of a fifth root of unity over $\Bbb{F}_2$ must have degree four, i.e. equal to $f_3(x)$.
Observe that $f_3(x)$ is its own reciprocal polynomial. Polynomials with this property are called palindromic because you can equally well read their sequence of coefficients backwards. Therefore our first trick won't give us a fourth irreducible quartic.