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.

  • 1
    $\begingroup$ 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? $\endgroup$ Sep 4 '12 at 19:30

$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.


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...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.