How to construct minimal polynomial? This is an exam question from last semester.
We have the finite field
$$ \mathbb F_{81} = \mathbb Z_3 [x]/(x^4+x^2+x+1)$$
(a) Prove that the polynomial $$ x^4+x^2+x+1 $$
is irreducible
(b) Construct the minimal polynomial of the element $$ x^3+x^2+x+1 \space\epsilon\space Z_3 [x]/(x^4+x^2+x+1)$$
Use y as a formal variable in this polynomial. Hint: using $$ x^3+x^2+x+1 = (x^2+1)(x+1) $$ should help with the calculations.
(c) Construct the subfield F9 in  $$ Z_3 [x]/(x^4+x^2+x+1)$$

I tried a and I think you can prove it by showing the polynomial has no Zeros? So assuming we call the polynomial g(x). I just filled in {0,1,2} and none of them gave 0 --> You can't split up the polynomial in polynomials of lower orders -> it's irreducible? 
I don't know how to do b and c though.
Can someone please tell me how to do it in general and what the solution is here? Really need the answer.
 A: For (a), a reducible polynomial of degree 4 must have either linear or quadratic factors.  Having linear factors is the same as having a root, and it is easy to plug in $0,1,$ and $2$ and see that they are not roots of the polynomial.  Therefore, we must verify that 
$$x^4+x^2+x+1 \neq (x^2+ax+b)(x^2+cx+d)=x^4+(a+c)x^3+\ldots +bd$$
for any choice of $a,b,c,d\in \mathbb{F}_3$.  If we had equality, then the $x^3$ term tells us $a=-c$ and the constant term tells us $b=1/d$ so either $b=d=1$ or $b=d=-1$.  Fully expanding out, we have
$$ (x^2+ax+b)(x^2-ax+b)=x^4+(2b-a^2)x^2+b^2 $$
which has zero $x$ term, and therefore cannot equal $x^4+x^2+x+1$.
For (b), we need to find the smallest linear relation over $\mathbb{F}_3$ between powers of $y=(x^2+1)(x+1)$ modulo $x^4+x^2+x+1$.  First, we note that because our field is a vector space over the subfield generated by $y$, the minimal polynomial will have degree $1$, $2$, or $4$.  
One can calculate that $y^2\equiv x^3+x^2+x-1\pmod{x^4+x^2+x+1}$ over $\mathbb{F}_3$, and therefore $y^2+2=y$ is the minimal polynomial for $y$.  Presumably the factorization helps for doing the calculation by hand.
For (c), since the minimal polynomial of $y$ is quadratic, the subfield generated by $y$ is isomorphic to $\mathbb{F}_9$.  
A: Since it has no zeros in $\mathbb{F}_3$, it has no linear factors.
To show it has no quadratic factors, set up a system of equations from:
$$(x^2+ax+b)(x^2+cx+d)=x^4+x^2+x+1$$ 
and you will find, by solving this system, that the system is inconsistent.
Thus it has no quadratic factors, and is irreducible. 
A: You can solve the problem of finding minimal polynomial, by "elimination theory". In doing so, you can use Grobner bases tool easily as follow:
1- Let $I=\langle y-(x^3+x^2+x+1) , x^4+x^2+x+1 \rangle \subset \mathbb{Z}_3[x,y]$,
2- Compute a Grobner basis, $G$, for $I$ w.r.t. a lexicographical ordering with $y \prec x$,
3- Find out the polynomial $f$, for which $\{f\} = G \cap \Bbb{Z}_3[y]$.
Then $f$ is the minimal polynomial of $x^3+x^2+x+1$.
You can do these computations using a computer algebra system like Maple, Singular or Magma. 
A: There's not really a good human-executable algorithm for bigger cases, in general, but in small cases we can succeed.
As commented, you must verify that $f(x)=x^4+x^2+x+1$ has has neither linear nor quadratic factor. You already tested for linear factors by testing for roots of $f(x)=0$ in $\mathbb F_3$, and there are none. Indeed, $0$ is not a root, and for non-zero $\alpha$ in $\mathbb F_3$, $\alpha^2=1$, so $f(\alpha)=1+1+\alpha+1=\alpha\not=0$.
Similarly, since $\mathbb F_9^\times$ is cyclic of order 8, non-zero elements satisfy $\alpha^8=1$, and observe that $x^8-1=(x^4-1)(x^4+1)$, conveniently two quartics, which we can play off against $f(x)$. For example, if $f(\alpha)=0$ and $\alpha^4+1=0$, then subtract, obtaining $\alpha^2+\alpha=0$, but this has roots $-1$ and $0$, which were already excluded. If $f(\alpha)=0$ and $\alpha^4-1=0$, in since we've already excluded $\alpha^2-1=0$, necessarily $\alpha^2+1=0$, and we subtract $\alpha^2$ times this from $f(\alpha)$, obtaining $\alpha+1=0$, which we've already excluded.
Obviously this idea could be implemented in some mathematical software, but would be tedious (and error-prone) to execute by hand. 
A: I will answer only (b).
By abuse of notation, we write $x$ for the image of $x$ in $\mathbb{Z}_3[x]/(x^4 + x^2 + x + 1)$.
Let $y = x^3 + x^2 + x + 1$.
Since $y = (x^2 + 1)(x + 1)$, $y^2 = (x^2 + 1)^2(x + 1)^2$.
Hence $y^2 = (x^4 + 2x^2 + 1)^2(x + 1)^2 = (-x + x^2)(x + 1)^2 = x(x - 1)(x + 1)^2 = x(x^2 - 1)(x + 1) = x(x^3 + x^2 - x - 1) = x^4 + x^3 -x^2 - x$
$= x^3 - 2x^2 -2x - 1 = x^3 + x^2 + x - 1$.
Hence $y^2 + 2 = y$.
Since $y$ is not contained in $\mathbb{F}_3$, $Y^2 - Y - 1$ is the minimal polynomial of $y$ over $\mathbb{F}_3$.
A: For $a$: were this polynomial was not an irreducible polynomial the quotient won't have been a field. 
