Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
7  
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

6 Answers 6

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.