# Number of monic irreducible polynomials of degree $p$ over finite fields

Suppose $F$ is a field s.t $\left|F\right|=q$. Take $p$ to be some prime. How many monic irreducible polynomials of degree $p$ can exist over $F$?

Thanks!

-
What have you tried? (Think about subextensions of $\mathbb{F}_{q^p}$ over $\mathbb{F}_q$.) – Qiaochu Yuan May 23 '11 at 9:31
@Qiaochu: Thanks, got the idea and found the answer... will write it down here soon! – IBS May 23 '11 at 13:25

The number of such polynomials is exactly $\displaystyle \frac{q^{p}-q}{p}$ and this is the proof:

The two main facts which we use (and which I will not prove here) are that $\mathbb{F}_{q^{p}}$ is the splitting field of the polynomial $g\left(x\right)=x^{q^{p}}-x$,
and that every monic irreducible polynomial of degree $p$ divides $g$.

Now: $\left|\mathbb{F}_{q^{p}}:\mathbb{F}_{q}\right|=p$ and therefore there could be no sub-extensions. Therefore, every irreducible polynomial that divides $g$ must be of degree $p$ or 1. Since each linear polynomial over $\mathbb{F}_{q}$ divides $g$ (since for each $a\in \mathbb{F}_{q}$, $g(a)=0$), and from the fact that $g$ has distinct roots, we have exactly $q$ different linear polynomials that divide $g$.

Multiplying all the irreducible monic polynomials that divide $g$ will give us $g$, and therefore summing up their degrees will give us $q^{p}$.

So, if we denote the number of monic irreducible polynomials of degree $p$ by $k$ (which is the number we want), we get that $kp+q=q^{p}$, i.e $\displaystyle k=\frac{q^{p}-q}{p}$.

-
Nice answer and question as well! +1 for both... Btw, you can accept your own answers? – Kugelblitz Mar 10 at 13:40

the number of monic irreducible polynomials of degree $n$ over the ﬁnite ﬁeld $\mathbb{F}_{q}$ is given by Gauss’s formula $$\frac{1}{n}\sum\limits_{d \mid n} \ \mu(n/d) \cdot q^{d}$$

For a complete proof : Please refer

• Abstract Algebra: Dummit and Foote, Chapter 14, Galois theory, Pages $567-568$.

• You might also want to see this paper, which actually presents a new idea of counting irreducible polynomials using Inclusion - Exclusion Principle. Link: http://arxiv.org/pdf/1001.0409

-
Just knowing the answer is not useful to anybody. I also suspect that this is a homework problem based on the condition on degrees, so please don't give answers like that. – Qiaochu Yuan May 23 '11 at 9:40
@Qiaochu: Ok... – user9413 May 23 '11 at 11:20
@Chandru: the proof presented in that paper is not new; it is equivalent to the classical proof by Mobius inversion. Inclusion-exclusion is a special case of Mobius inversion on a poset. – Qiaochu Yuan May 23 '11 at 11:24
@Chandru: i hope you don't mind, but Qiaochu is right and this was a homework qeustion about the extension $\mathbb{F}_{q^{p}}\geq\mathbb{F}_{q}$. I actually used Quaochu's comment to find the answer myself... appreciate the help. – IBS May 23 '11 at 13:24
For what it's worth, this answer was useful to me as a quick reference for the formula. I do not agree that "the answer is not useful to anybody". – J Swanson Oct 26 '13 at 9:58