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$ do exist over $F$?


  • 4
    $\begingroup$ What have you tried? (Think about subextensions of $\mathbb{F}_{q^p}$ over $\mathbb{F}_q$.) $\endgroup$ – Qiaochu Yuan May 23 '11 at 9:31
  • 1
    $\begingroup$ @Qiaochu: Thanks, got the idea and found the answer... will write it down here soon! $\endgroup$ – IBS May 23 '11 at 13:25
  • $\begingroup$ There are some programs for computation on irreducible poly in finite field on academia.edu/30039889/… $\endgroup$ – Rorschach Feb 20 '17 at 9:55

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}$.

  • 1
    $\begingroup$ Nice answer and question as well! +1 for both... Btw, you can accept your own answers? $\endgroup$ – Kugelblitz Mar 10 '15 at 13:40
  • 1
    $\begingroup$ As you can see, it is possible :) $\endgroup$ – IBS Apr 2 '16 at 19:44
  • $\begingroup$ does not work if $p=1$ (it is not prime though). $\endgroup$ – T.... Oct 29 '16 at 20:43

the number of monic irreducible polynomials of degree $n$ over the finite field $\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

  • 7
    $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan May 23 '11 at 9:40
  • $\begingroup$ @Qiaochu: Ok... $\endgroup$ – user9413 May 23 '11 at 11:20
  • 6
    $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan May 23 '11 at 11:24
  • 1
    $\begingroup$ @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. $\endgroup$ – IBS May 23 '11 at 13:24
  • 14
    $\begingroup$ 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". $\endgroup$ – J Swanson Oct 26 '13 at 9:58

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.