# How can I prove irreducibility of polynomial over a finite field?

I want to prove what $x^{10} +x^3+1$ is irreducible over a field $\mathbb F_{2}$ and $x^5$ + $x^4 +x^3 + x^2 +x -1$ is reducible over $\mathbb F_{3}$.

As far as I know Eisenstein criteria won't help here. I have heard about a criteria of irreducibility which sounds like

"If $f(x)$ divides $x^{p^n-1}-1$ (where $n=\deg(f))$, $p$ is from $\mathbb F_{p}$ then $f(x)$ is irreducible."

But I don't know how to show if $f(x)$ can be divided by this or not.

• An irreducible polynomial can't be divided by anything except for associates (i.e. unit multiples) of itself and $1$. In particular, no polynomial can be divided by a polynomial of higher degree (you'd get a rational function). Your concept of division seems backwards. For instance, $2$ cannot be divided by $6$ (although we do say "$2$ divides $6$," notated $2\mid 6$, meaning $\exists n\in\Bbb Z:6=2n$). – anon Jun 29 '15 at 16:42
• Thank you, I corrected the question and tryed to divide using Wolfram Alpha but both times I got a non-empty remainder so both of my polynomials shall be reducible but one of them is not – Ultra Jun 29 '15 at 18:19
• Oops. The correct version of the cited result is the following: All the irreducible polynomials of degree $n>1$ are factors of $x^{p^n-1}-1$. This is the version I use in my answer. – Jyrki Lahtonen Jun 29 '15 at 18:43

The test that you're thinking of is Rabin's test for irreducibility, which can be stated as follows.

Let $f(x)$ be a polynomial of degree $n$ over $\mathbb{F}_p$. Then $f$ is irreducible over $\mathbb{F}_p$ if and only if

• $f(x)$ divides $x^{p^n}-x$, and

• $\mathrm{gcd}\bigl(f(x),x^{p^{n/q}}-x\bigr)=1$ for each prime divisor $q$ of $n$.

For $f(x) = x^{10}+x^3+1 \in \mathbb{F}_2[x]$, we must check that $f(x)$ divides $x^{2^{10}}-x = x^{1024}-x$, and that it is relatively prime with $x^{32}-x$ and $x^4-x$.

For $f(x) = x^5 + x^4+x^3+x^2+x-1 \in\mathbb{F}_3[x]$, we must check that $f(x)$ divides $x^{243}-x$ and that it is relatively prime with $x^3-x$.

All of this is easy to do on a computer. In Mathematica, the PolynomialExtendedGCD command can check polynomial GCD's modulo any prime.

In[1] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^1024 - x, x, Modulus -> 2][[1]]

Out[1] := 1 + x^3 + x^10

In[2] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^32 - x, x, Modulus -> 2][[1]]

Out[2] := 1

In[3] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^4 - x, x, Modulus -> 2][[1]]

Out[3] := 1


This establishes that $x^{10}+x^3+1$ is irreducible over $\mathbb{F}_2$. For the other polynomial, we can try:

In[1] := PolynomialExtendedGCD[x^5+x^4+x^3+x^2+x-1, x^243 - x, x, Modulus -> 3][[1]]

Out[1] := 1


As you can see, the GCD is $1$, so it doesn't divide. Indeed, $$x^5+x^4+x^3+x^2+x-1 \;=\; \bigl(x^2-x-1\bigr)\bigl(x^3-x^2+x+1\bigr)$$ over $\mathbb{F}_3$, so the second polynomial isn't irreducible.

Edit: As Jyrki Lahtonen and Alex M. point out, one can always just use Mathematica directly to test whether a polynomial is irreducible, so there's not a practical reason to use Rabin's test in Mathematica for these two polynomials. Also, if you have access to a computer, you can always in principle check whether a polynomial is irreducible simply by enumerating all possible factors and then attempting to divide by each factor. If you don't have access to a computer, the methods suggested in their answers are certainly better than doing Rabin's method by hand.

However, Rabin's test is important from an algorithmic point of view as one possible way to check for irreducibility. Indeed, for polynomials of high degree, Rabin's test clearly outperforms trial division by all possible factors, though there are other competitive algorithms. The two given problems are simple enough that almost any algorithm you use on a computer will give the desired results very quickly, but it is still instructive to see how Rabin's test can be applied to these examples.

• If you allow Mathematica/WA then you can just do In[1]:=Factor[x^10+x^3+1,Modulus->2] and be done with it. – Jyrki Lahtonen Jun 30 '15 at 8:31
• Is this a mistake? The polynomial over $\Bbb F _3$ has degree $5$, so you should check that it divides $x^{3^5}-x = x^{243}-x$ and that it is coprime with $x^3-x$. Or am I misunderstanding something? – Alex M. Jun 30 '15 at 9:54
• In any case, I second @JyrkiLahtonen in saying that this answer cheats when it uses a computer algebra system, as dividing $x^{1025} - x$ by $x^10 + x^3 + 1$ by hand probably takes more time than my long solution given below. – Alex M. Jun 30 '15 at 9:57
• @AlexM. Yes, thanks for spotting the typo. I have fixed it. – Jim Belk Jun 30 '15 at 11:14
• I have also added some additional comments about the usefulness of this method. I don't disagree with the comments by Jyrki Lahtonen and AlexM., but I suppose I interpreted the OP's question as being primarily about trying to remember the details of Rabin's test as opposed to being primarily about determining whether the given polynomials are irreducible. The answers both of them give below are clearly superior if the goal is to check by hand whether the given polynomials are irreducible. – Jim Belk Jun 30 '15 at 11:36

Neither polynomial has zeros in the respective prime field, so they do not have linear factors either.

Let's check the first polynomial $p(x)=x^{10}+x^3+1\in\Bbb{F}_2[x]$. The claim is that it is irreducible. A more efficient way of using the cited result is to observe that if $p(x)$ were a product of two or more irreducible factors at least one of those factors would have degree $\le5$. We eliminate these possibilities one-by-one. Testing for the presence of higher degree factors becomes progressively a little bit harder as the degree goes up, but the principle is always the same, and this result gives us a tool.

Could it have an irreducible quadratic factor? By the cited result all the irreducible quadratic polynomials are factors of $p_2(x):=x^{2^2-1}-1=x^3+1$. To eliminate the possibility of $p(x)$ having a quadratic factor it thus suffices to show that $\gcd(p(x),p_2(x))=1$. Because $p(x)-p_2(x)=x^{10}$ any common factor they have is also a factor of $x^{10}$, but the only irreducible factor of $x^{10}$ is $x$, so we have cleared this obstacle.

To eliminate the possibility of $p(x)$ having a cubic factor it similarly suffices to check that $\gcd(p(x),p_3(x))=1$, where $p_3(x)=x^{2^3-1}-1=x^7+1$. Here we see (the first step in calculating this gcd by Euclid's algorithm) that $$p(x)-x^3p_3(x)=1,$$ so no common factors there either.

To eliminate the possibility of a quartic factor of $p(x)$, we need to calculate $\gcd(p(x),p_4(x))$ with $p_4(x)=x^{2^4-1}-1=x^{15}+1.$ Let's run Euclid: \begin{aligned} p_4(x)-x^5p(x)&=x^8+x^5+1=: r_1(x)\\ p(x)-x^2r_1(x)&=x^7+x^3+x^2+1=:r_2(x). \end{aligned} Here we could continue with Euclid, but we can also save a step or two by factoring the remainder whenever we can do so easily. Here $$r_2(x)=x^3(x^4+1)+(x^2+1)=x^3(x^2+1)^2+(x^2+1)=(x^2+1)(x^5+x^3+1).$$ We know from earlier steps that $p(x)$ is not divisible by $(x+1)$. Because $(x^2+1)=(x+1)^2$, we can discard that factor as a possibility, and continue Euclid with $\gcd(r_1(x), r_3(x))$ where $r_3(x)=x^5+x^3+1$. We see that \begin{aligned} r_1(x)-x^3r_3(x)&=x^6+x^5+x^3+1=(x+1)(x^5+x^2+x+1)\\ &=(x+1)^2(x^4+x^3+x^2+1)=(x+1)^3(x^3+x+1). \end{aligned} Here I used extensively the trick (based on geometric sums) that whenever $0<a<b$ we have $$\frac{x^a+x^b}{x+1}=x^a+x^{a+1}+x^{a+2}+\cdots+x^{b-1}.$$ Anyway, the above calculation shows that any eventual common factor of $p(x)$ and $p_4(x)$ is also a factor of the cubic $x^3+x+1$, but we already showed that $p(x)$ has no cubic factors. Therefore we are done with this case, too.

The last step of proving that $p(x)$ as no quintic factors needs another run of Euclid. This time checking that $\gcd(p(x),p_5(x))=1$, where $p_5(x)=x^{31}+1$. To get started we use square-and-multiply. We already calculated in the previous step that $$x^{15}\equiv x^8+x^5\pmod{p(x)}.\qquad(*)$$ Consequently $x^{16}\equiv x^9+x^6\pmod{p(x)}$. Squaring $(*)$ (Freshman's dream simplifies squaring in characteristic two) gives $$x^{30}\equiv x^{16}+x^{10}\equiv (x^9+x^6)+x^{10}\pmod{p(x)}.$$ Here $$x^{10}+x^9+x^6-p(x)=x^9+x^6+x^3+1.$$ Therefore (multiply by $x$) $$x^{31}\equiv x^{10}+x^7+x^4+x\equiv x^7+x^4+x^3+x+1\pmod{p(x)}.$$ So we know the remainder of $p_5(x)$ modulo $p(x)$. The remaining task is thus to check that $$\gcd(p(x),x^7+x^4+x^3+x)=1.$$ Leaving that to you :-)

Your other polynomial $$q(x)=x^5+x^4+x^3+x^2+x-1\in\Bbb{F}_3(x)$$ is quintic. So if it is reducible, it must have one factor that is either linear or a quadratic. We eliminated the possibility of linear factors by checking that it has no zeros. Using the above technique we find eventual quadratic factors by calculating $$\gcd(q(x),q_2(x))\in\Bbb{F}_3[x].$$ Here $q_2(x)=x^{3^2-1}-1=x^8-1$. Leaving it to you to run this instance of Euclid, and find the quadratic factor.

• If you are happy to use WA here, then the calculation of GCDs is much easier. This is about the limit of what I'm willing to do with pencil & paper unless you pay me (which would be a baaaad idea :-) – Jyrki Lahtonen Jun 29 '15 at 18:45
• Ah, if I only knew about this criterion! So, I guess that it can be stated as "$f$ is irreducible iff $\gcd (f, X^{p^k-1}) = 1$ for all $1 \le k \le [\frac n 2]$". Does it also work in $\Bbb F _{p^n}$ with $n>1$? – Alex M. Jun 29 '15 at 19:03
• @Alex: Yes. If $q=p^n$, and $f$ is irreducible over $\Bbb{F}_q$ of degree $m$, then $f\mid x^{q^m-1}-1$. The rest goes as above. – Jyrki Lahtonen Jun 30 '15 at 8:30

I think that the criterion that you allude to is the following:

Assume that $X^p - a$ has no roots in $\Bbb F _{p^n}$. Then $X^{p^m} - a$ is irreducible in $\Bbb F _{p^n}[X]$ $\forall m \ge 1$.

In any case, you can't use it here.

1) Let us see how to prove that the second polynomial (call it $P$) is reducible. First, none of $0, 1, 2$ is a root, so $P$ has no factor of degree $1$ (and, therefore, no factor of degree $4$). Let us see whether $P$ can be written as a product of two polynomials, of degree $2$ and, respectively, $3$. The long method is to multiply the polynomials $aX^2 + bX + c$ and $eX^3 + fX^2 + gX + h$, equate the coefficients of equal powers etc...

A shorter approach is the following: let us list all the polynomials of degree $2$ and check whether they divide $P$. Since $P$ has no linear factor, it is enough to list only those polynomials of degree $2$ that are irreducible. Note that no such polynomial may end in $0$, so the constant term is $1$ or $2$. Concerning the leading coefficient, it is enough to consider only monic polynomials. So far we get the polynomials $X^2 + aX + 1$, $X^2 + aX +2$. A polynomial of degree $2$ is irreducible if it has no roots, i.e. if its discriminant is not a perfect square. Since the only perfect squares in $\Bbb F _3$ are $0$ and $1$, you want $a$ such that the discriminant should be $2$.

In the first case, the discriminant is $a^2 - 4$, so you want $a$ such that $a^2 - 4 = 2$, so $a=0$.

In the second case, the discriminant is $a^2 - 8$, so you want $a$ such that $a^2 - 8 = 2$, i.e. $a^2 = 1$, i.e. $a=1$ or $a=2$.

So, the only monic irreducible polynomials of degree $2$ are $X^2 + 1$, $X^2 + X + 2$, $X^2 + 2X +2$. Let us see which one divides our polynomial.

Note that $P = X^3 (X^2+1) + X^2 (X^2+1) + X-1$, so when you divide $P$ by $X^2 +1$ you get the remainder $X-1$, so $X^2-1 \not| P$.

Finally, try to divide $P$ by the last two polynomials. $X^2 + 2X +2$ will turn out to be a factor.

2) Concerning the first polynomial (call it $Q$), the approach will be similar. First, note that it has no roots, so it has no linear factor. Therefore, we are going to look only for irreducible factors of degree $2, \dots, 5$. In order to be irreducible, these potential factors must have the constant term $1$.

Looking for irreducible polynomials of degree $2$, these must look like $X^2 +aX +1$. Clearly, $a=1$ gives the only irreducible one.

For degree $3$, you want those polynomials $X^3 + aX^2 + bX +1$ that have no linear factor; since $0$ cannot be a root, you also do not want $1$ to be so, therefore you want $1+a+b+1 \ne 0$, which means $a+b =1$, so the only possibilities are $X^3 + X^2 +1$ and $X^3 +X+1$.

In degree $4$, you want those polynomials $X^4 + aX^3 + bX^2 + cX +1$ that have no roots (so $1+a+b+c+1 \ne 0$, i.e. $a+b+c=1$) and that have no irreducible factor of degree $2$, i.e. that are not divided by $X^2+X+1$ (found above). A reducible factor of degree $4$ having no root would have to be $(X^2+X+1)^2 = X^4 + X^2 +1$. Therefore, the only irreducible polynomials of degree $4$ remain $X^4 + X^3 +1$, $X^4+ X+1$ and $X^4+ X^3 + X^2 + X + 1$.

Finally, the reducible polynomials $x^5 + aX^4 + bX^3 +cX^2 + dX +1$ of degree $5$ are those that have roots (i.e. $a+b+c+d=0$) and those that can be divided by $X^2+1$. Performing long division by $X^2+1$, you get the remainder $(b+d+1)x + (a+c+1)$, so in order to get the reducible polynomials impose $a+b+c+d = 0, \; b+d+1 = 0, \; a+c+1 = 0$. Solve this system (it will have several solutions); the polynomials that are not among these solutions are the irreducible ones of degree $5$.

Now that you've listed all the irreducible polynomials of degree $\le 5$, check (by performing long division or by computing the greatest common divisor) which ones divide $Q$. None will, so $Q$ is irreducible.

Below is the proof of the irreducibility criterion mentioned at the beginning of my post.

Notice that $X^{p^m} - a$ has at least one root $x$ in some algebraic closure $K$ of $\mathrm F_{p^m}$; if $y \in K$ is another root, it follows that $x^{p^m} = y^{p^m}$ and, since $r \mapsto r^{p^m}$ is an automorphism of $K$ (because the Frobenius map $r \mapsto r^p$ is), it follows that $x=y$. It follows that $X^{p^m} - a$ has exactly one root $x \in K$, of multiplicity $p^m$.

If $g \in \mathrm F_{p^m} [X]$ is the minimal polynomial of $x$, then $X^{p^m} - a = g^s$; since $p^m = s \deg g$, it follows that $s = p^t$. Let $b = -g(0)$ and assume $t>0$. Evaluating $X^{p^m} - a = g^s$ in $0$, and assuming $t>0$, we get $a = (b^{p^{t-1}})^p$ (because $-1 = (-1)^s$ in characteristic $p>0$), which would imply that $X^p - a$ has the root $b^{p^{t-1}} \in \mathrm F _{p^m}$, which would contradict the hypothesis of the criterion. It follows that $t=0$, so that $s=1$, therefore $X^{p^m} - a$ is the minimal polynomial of $a$, therefore irreducible by the definition of the concept of "minimal polynomial".

• Hi there. Do you have ny reference (book, site...) for the result in yellow you mention at the beginning of your answer? Thanks a lot. +1 – DonAntonio Feb 26 '18 at 17:58
• @DonAntonio, I had taken this criterion from an old set of lecture notes of mine. Since I have found no proof of it elsewhere, I have added a proof of it at the end of my post. – Alex M. Feb 26 '18 at 20:31