4
$\begingroup$

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
    In my comments to a [recent question](http://math.stackexchange.com/q/189373/11619) I gave links to no less than SI$X$ earlier questions on Math.SE, where this or relate$d$ questions have been studied. Would any of the answers to those questions help you?2012-09-04

2 Answers 2

4

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

2

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