# 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.

-
For the polynomial to be irreducible (over ${\mathbb Z}_3$) you don't only need it to have no zeros there, you also need to show there are no quadratic factors. – Robert Israel Aug 23 '12 at 21:48

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$.

-

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.

-

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.

-

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$.

-

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.

-

For $a$: were this polynomial was not an irreducible polynomial the quotient won't have been a field.

-
Yes, but this speaks towards the intent of the problem: is it to prove that the quotient is a field, or just to realize the link between field extensions and irreducible polynomials? – Aaron Aug 23 '12 at 22:12
@Aaron - I don't understand your question, can you explain please ? – Belgi Aug 23 '12 at 22:17
The problem begins by stating that $\mathbb{Z}_3[x]/(x^4+x^2+x+1)$ is a finite field, but part (a) can be viewed two different ways. The first way is that it is asking to prove that the quotient ring is a field. The second way is that it is asking you to deduce that the polynomial is irreducible GIVEN that the quotient is a field. The latter interpretation is rather uninteresting, in part because it has a one line answer (which you gave). I choose to believe that we should use the first interpretation. – Aaron Aug 23 '12 at 22:27
@Aaron - I interpet this the first way since before $a$ is asked it is written: "We have the finite field". – Belgi Aug 23 '12 at 22:57
I didn't think about that.. I'm not sure if that would be allowed, but that's a smart solution! :D – Spyral Aug 24 '12 at 5:26