# Counting irreducible polynomials over finite fields [duplicate]

How many irreducible polynomials in $Z_2[x]$ of degree $3$?

I have discussed this with my friend before and we found that $x^3 + x^2 + 1$ and $x^3+x+1$ are the two said polynomials which irreducible. We got this the approachment that polynomials $p(x) = ax^3+bx^2+cx+d$ must satisfy $a\ne 0$ and later $d \neq 0$ and here we only need to take some cases of the value of $b$ and $c$. Do you have idea to solve this problem clearly without guessing? I am afraid that there will be a new problem asking for polynomials whose degree is higher than this one and here I will be stuck.

## marked as duplicate by Dietrich Burde abstract-algebra StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 9 '18 at 8:45

There is a general method to count irreducible polynonials of a certain degree with coefficients in any finite field. I think with the first hint you can figure out this method already by yourself, but I left a second hint and a complete solution (for your particular problem) just in case.

Hint: you can count the number of reducible polynomials of degree three and the total number of polynonials of degree three. The difference gives you the number of irreducible polynomials of degree three.

Further hint: if a degree 3 polynomial factors, it does as 3 linear factors or as 1 linear factor and 1 irreducible polynomial of degree 2. You can count the number of irreducible polynomials of degree 2 in the same way: count the reducible ones, which are just the product of two linear factors.

Solution:

There are 3 reducible polynomials of degree 2, namely $x^2$, $x(x+1)$ and $(x+1)^2$. In total there are 4 polynomials of degree 2, so there is only one irreducible polynomail of degree 2.

There are 4 polynomials of degree 3 that factor as 3 linear polynomials, namely $x^3$, $x^2(x+1)$, $x(x+1)^2$ and $(x+1)^3$.

There are 2 polynomials of degree 3 that factor as a linear factor times an irreducible degree 2 polynomial, namely $xf(x)$ and $(x+1)f(x)$, where $f(x)$ is the only irreducible polynomial of degree 2.

In total we have found 6 reducible polynomials of degree 3. There are $2^3=8$ polynomials of degree 3. Hence, there are only 2 irreducible polynomials of degree 3 in $\mathbb{Z}_2[x]$.

Up to isomorphism there is only one field with $8$ elements.

If $f(x)$ has degree $3$ and is irreducible, take an extension field $F$ of $\mathbb{Z}_2$ where $f$ has a root. By the statement above, all roots of $f$ belong to $F$. By the dimension formula, $F$ cannot contain elements of degree $2$ over $\mathbb{Z}_2$. Thus there are exactly two (monic) irreducible polynomials of degree $3$, because the set $F\setminus\mathbb{Z}_2$ has six elements and fixing one of them identifies the other two roots of its minimal polynomial.

For similar reasons, there is only one irreducible polynomial of degree $2$.

For the degree $4$ it's a bit more complicated, but we can partition the $16$ element field into two elements of degree $1$, two elements of degree $2$, and $12$ elements of degree $4$. Thus the irreducible polynomials of degree $4$ are three.

Degree $5$ is simple again (because $5$ is prime): the number of irreducible polynomials is $$\frac{2^5-2}{5}=6$$