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 know the problem of the number monic, irreducible polynomials of degree $k$ in $\mathbb{F}_p$ have been discussed and that there is a general formula which solves this problem. Nevertheless, I have trouble to understand another approach.

My solution is counting the number of irreducible monic polynomials of degree $6$ in $\mathbb{Z}_2$.

Therefore, we regard $x^{2^6}-x \in \mathbb{Z}_2[x]$ and we know that it can factorized into all irreducible polynomials of degree $1,2,3,6$ over $\mathbb{Z}_2[x]$.

We use the formula $\frac{p^k-p}{p}$ to determine the number of irreducible polynomials of a degree $k$ in $\mathbb{F}_p$ where $k \in \mathbb{P}$ for the divisors of $6$:

$$\frac{2^2-2}{2} = 1$$

$$\frac{2^3-2}{2} = 2$$

And we observe that there are $2$ polynomials of degree $1$.

Up until know I understand the solution but then the results are connected into a formula without further explanation:

$$\frac{2^6-2\cdot1-1\cdot2-2\cdot3}{6} = 9$$

This is the correct result but I do not understand the last step. This looks like an elegant way to solve this problem for small numbers in an exam without usage of the general formula.

share|cite|improve this question
In my comments to a recent question I gave links to no less than SIX earlier questions on Math.SE, where this or related questions have been studied. Would any of the answers to those questions help you? – Jyrki Lahtonen Sep 4 '12 at 19:30
up vote 4 down vote accepted

$x^{64}-x$ has $64$ roots. Of these, $2$ come from the $2$ irreducible degree $1$ polynomials, 2 more from the $1$ irreducible degree $2$ polynomial, $6$ more from the $2$ irreducible degree $3$ polynomials. The remaining $64-2-2-6$ roots come from irreducible degree $6$ polynomials, each being responsible for $6$ roots.

share|cite|improve this answer

Alternative to Hagen's answer is that $x^{2^6}-x$ is the product of of the monic primes of degree $d|6$.

So if $a_d$ is the number of monic primes of degree $d$ over $\mathbb F_2$, then the degree of $x^{2^6}-x$ is equal to:

$$ 64 = 6a_6 + 3a_3 + 2a_2 + a_1$$

So $$a_6 = \frac{ 64-3a_3-2a_2-a_1}{6}$$

This uses that $x^{2^6}-x$ has exactly these primes as factors, and that no factor occurs more than once...

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.