Find the minimal polynomial of $\alpha^2+1$ over $\Bbb F_2$ $α
^2 + 1 ∈ E$ over $\Bbb F_2$, where E is the field $\Bbb F_2[x]/\langle x^3 + 3x + 1\rangle$ and $α ∈ E$ denotes the
coset $\overline{x}$.
What I do know is that $[\Bbb F_2[x]/\langle x^3 + 3x + 1\rangle:\Bbb F_2]=3$ because the polynomial is irreducible over $\Bbb F_2$. But how do I go about to find the minimal polynomial of $\alpha^2+1?$ (I have not learnt Galois Theory yet.)
 A: All right, here's an easier way.  Note that
$$
0 = \alpha^3 + \alpha + 1 = \alpha(\alpha^2 + 1) +1 \implies \alpha(\alpha^2 + 1) = 1 \implies \alpha^2 + 1 = 1/\alpha \, .
$$
Dividing $\alpha^3 + \alpha + 1 = 0$ through by $\alpha^3$, we find that
\begin{align*}
0 = \frac{\alpha^3 + \alpha + 1}{\alpha^3} = \left(\frac{1}{\alpha}\right)^3 + \left(\frac{1}{\alpha}\right)^2 + 1 \, .
\end{align*}

Since the extension $\DeclareMathOperator{\Gal}{Gal} E/\mathbb{F}_2$ is Galois and $\mathbb{F}_2(\alpha^2+1) = E$ by degree considerations, then the minimal polynomial of $\alpha^2+1$ is
$$
m(x) = \prod_{\tau \in \Gal(E/\mathbb{F}_2)} (x - \tau(\alpha^2 + 1)) \, .
$$
That is, the other roots of the minimal polynomial are exactly the Galois conjugates of $\alpha^2 + 1$.  Since $\Gal(E/\mathbb{F}_2)$ is cyclic and generated by the Frobenius automorphism
\begin{align*}
\sigma : E &\to E\\
\beta &\mapsto \beta^2
\end{align*}
then
$$
m(x) = (x - (\alpha^2 + 1))(x - \sigma(\alpha^2 + 1))(x - \sigma^2(\alpha^2 + 1)) \, .
$$

Here's one last answer that's not as clever as the first, but not as inefficient as the second.  Consider the $E$ as a vector space over $\mathbb{F}_2$ with basis $1, \alpha, \alpha^2$.  Multiplication by $\alpha^2 + 1$ is an $\mathbb{F}_2$-linear map which has matrix
$$
\begin{pmatrix}
1 & 1 & 0\\
0 & 0 & 1\\
1 & 0 & 0
\end{pmatrix}
$$
with respect to the above basis.  This matrix has characteristic (and in fact, minimal) polynomial $x^3 + x^2 + 1$.  Since $\alpha^2 + 1$ is a root of this polynomial, and it is irreducible (it has no roots over $\mathbb{F}_2$ and has degree $3$), then it is the minimal polynomial.
