Alternative solution to determine the number of irreducible, monic polynomials in $\mathbb{Z}_p[x]$ of degree $k$

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.

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