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?
Best Answer
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.