# Different ways of proving a polynomial is irreducible in finite field.

Is there a general characterization of irreducible polynomials over a finite field?

I was going through a problem in finding whether $p(x):=x^7+x^5+1$ is irreducible over $\mathbb F_2[x]$ or not.

If the polynomial is of degree less than or equal to $3$ then we can easily find out if its irreducible or not by finding whether it has a root or not. In this case considering the polynomial $p(x)=f(x)\cdot g(x)$ we may be able to show the irreducibility but this doesn't seem to be a very great idea. Can anyone suggest a better idea ?

The given polynomial is in fact not irreducible. There is at least one decomposition:

$$(x^2+x+1)\cdot(x^5+x^4+x^3+x+1) = x^7+x^5+1$$

This can be found by resolving the equality for coefficients:

$$(x^2+ax+1)\cdot(x^5+bx^4+cx^3+dx^2+ex+1) = x^7+x^5+1$$

which, equating term by term, and ignoring the terms of degree $0$ and $7$:

$$(a+b)x^6 + (1+ab+c)x^5 + (b+ac+d)x^4 + (c+ad+e)x^3 + (d+ae+1)x^2 + (e+a)x = x^5$$

so

$$a+b=0 \\ ab+c=1 \\ b+ac+d = 0\\ c+ad+e=0\\ d+ae=1\\ e+a=0$$

which are more than enough to find the solution, given that in $\mathbb{Z}_2$, $a^2=a$ and $a+a=0$ for any $a$.

• How did you get it ? @rewritten , did you use maple or something ? or just brute force ? – Complex analysis Dec 2 '13 at 16:58
• Not with brute force, in $\mathbb{Z}_2$ is pretty easy to do calculations, either the coefficient is 1 or 0. So you just set arbitrary coefficients (the top degree and the constant term have of course coefficient 1). Then set equality and solve. – rewritten Dec 2 '13 at 17:11
• Added explicit solution. – rewritten Dec 2 '13 at 17:17

Over a finite field $\mathbb F_p$, the product of all irreducible polynomials of degree $d$ is $x^{p^{d}}-x$, so this polynomial is irreducible iff it divides $x^{2^{7}}-x = x^{128}-x$. Now you can just check this by computation.

• Over $\mathbb F_2$ the product of all irreducible polynomials of degree $2$ is $x^2+x+1$ which is different from $x^4-x$. Maybe you want to say "the product of all irreducible polynomials of degree $k$ with $k\mid d$ is $x^{p^{d}}-x$". – user26857 May 4 '17 at 8:30