Determine the number of irreducible polynomials of degrees 2, 3, and 6 over the prime field $\mathbb F_p$.

Question

Determine the number of irreducible polynomials of degrees 2, 3, and 6 over the prime field $\mathbb F_p$.

Hint: Count all polynomials of a given degree. Which of these are reducible?

Answer 1

Let $f(n) $ be the number of irreducible polynomials of degree $n$ and $g(n)$ the number of all poylnomials of degree $n$. In both cases, however, we count only those with leading coefficient $1$. A polynomial of degree $n$ looks like this: $$ X^n+a_{n-1}X^{n-1}+\cdots +a_1X+a_0.$$ We conclude that $g(n)=p^n$.

All reducible polynomials of degree $2$ are products of polynomials of degree $1$. More precisely, we either have the square of a degree-1 polynomial - $g(1)$ possibilities - or the product of two distinct polynomials - $g(1)\choose 2$ because the order does not matter. We conclude that $$ f(2)=g(2)-g(1)-{g(1)\choose 2}=p^2-p-\frac{p(p-1)}2=\frac{p(p-1)}2.$$

Similarly, in degree $3$, a reducible polynomial is the product of a degree-1 and an irreducible degree-2 polynomial or the product of three degree-1 polynomials. Taking care of repetitions among the latter, we find $$f(3)=g(3)-g(1)f(2)-g(1)-g(1)(g(1)-1) -{g(1)\choose 3} $$ You can fill in the above results - and try your luck with degree 6.