1
$\begingroup$

I am motivated by this question, and want to find a solution to the following problem.

Question: How many monic, irreducible polynomials of degree $n$ are there over the finite field $\mathbb{F}_q$ for some prime $q$?

The solution provided in the original question pivots on two central claims:

Claim 1: $\mathbb{F}_{q^n}$ is the splitting field of the polynomial $g(x)=x^{q^n}−x$

Claim 2: Every monic irreducible polynomial of degree $n$ divides $g$.

Claim 1 I am happy with, but in the case of Claim 2 I cannot see why it is true. Could someone please explain.

$\endgroup$
3
$\begingroup$

The point is that every element of ${\mathbb F}_{q^n}$ is a root of $g(x)$, so $$g(x) = \prod_{\alpha \in {\mathbb F}_{q^n}} (x - \alpha).$$ Now an irreducible polynomial $h(x)$ over ${\mathbb F}_q$ of degree $n$ splits in distinct linear factors over ${\mathbb F}_{q^n}$, so all its factors are also factors of $g(x)$. Therefore $h(x)$ divides $g(x)$.

$\endgroup$
  • $\begingroup$ Thanks, it's all so clear now $\endgroup$ – Mathmo May 2 '14 at 13:24
1
$\begingroup$

Denote by $N_q(n)$ the number of monic, irreducible polynomials in $\mathbb{F}_q[x]$ of degree $n$. Here $q$ can be any prime power. Then Claim $1$ and $2$ give $$ q^m =\sum_{n\mid m}nN_q(n), $$ for all $m\ge 1$, and this gives the formula $$ N_q(n)=\frac{1}{n}\sum_{d\mid n} \mu \left(\frac{n}{d}\right)q^d $$ by the Möbius inversion formula.

$\endgroup$

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.