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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for the number of irreducible polynomials with degree $6$ in $\mathbb{F}_2[X]$ with leading coefficient $1$.

First question: The leading coefficient $1$ is redudant because every polynomial of degree $6$ has leading coefficient $1$?

My solution: The polynomials must be of the form

$$ x^6 + \dots + 1$$

to ensure the degree of $6$ and to ensure that $0$ is not a root. Now we have

$$ \dots + \alpha_5x^5+ \dots +\alpha_1x+ \dots$$

with $\alpha_i \in \mathbb{F}_2$. To avoid that $1$ is root, an odd number of $\alpha_i$ must be $1$. The number of combinations for that would be $\frac{2^{(5-1)}}{2}$ = 8. Is that correct?

share|cite|improve this question
Here is an answer to more general question… – Norbert Jul 15 '12 at 18:37
up vote 3 down vote accepted

To finish doing it your way - first of all, you've miscounted - there's five numbers between $\alpha_1, \ldots, \alpha_5$, so you really want $2^5/2 = 16$. But there's still some of those polynomials that aren't irreducible: the problem is that just because a degree 6 polynomial doesn't have a root doesn't make it irreducible (that's only true for degree 2 and 3 polynomials). For example, $$ x^6 + x^2 + 1 = (x^3 + x + 1)^2 $$ in characteristic $2$, so it's not irreducible even though it's on your list.

To figure out which ones to throw out, let's write down the possible irreducible factors of a degree 6 polynomial with no linear factors:

possible irreducible quadratic factors: $x^2 + x + 1$

possible irreducible cubic factors: $x^3 + x^2 + 1$, $x^3 + x + 1$.

possible irreducible quartic factors: $x^4 + x^3 + 1$, $x^4 + x + 1$.

In making this last list I throw out $x^4 + x^2 + 1 = (x^2 + x + 1)^2$. I know the other two are irreducible because the only way I'm going to get a reducible quartic with no linear factors is for it to be the square of the quadratic.

We can't have an irreducible quintic factor because the quotient would be linear.

So, what could go wrong? We can partition 6 as $2 + 2 + 2$, $2 + 4$, or $3 + 3$; these are the only partitions that don't use a 1. There's one way to get a degree 6 polynomial by using a quadratic three times; two ways by using a quadratic and a quartic, and four ways by using two cubics.

So we need $16 - 1 - 2 - 4 = 9$. This agrees with the answer using Möbius inversion given on Mathoverflow.

share|cite|improve this answer

For variety, a different approach. Each irreducible polynomial degree 6 polynomial has 6 distinct roots $\alpha$ with the property that $\mathbf{F}_2(\alpha) = \mathbf{F}_{64}$. Furthermore, no two distinct polynomials have overlapping roots.

There are 64 elements of $\mathbf{F}_{64}$. Of those:

  • 2 of them lie in $\mathbf{F}_{2}$
  • 4 of them lie in $\mathbf{F}_{4}$
  • 8 of them lie in $\mathbf{F}_{8}$

(these are the only proper subfields). After counting everything carefully, this leaves $54 = 6 \cdot 9$ elements that do not lie in any subfield, and thus 9 irreducible polynomials.

share|cite|improve this answer

Your Answer


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.