Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

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

2 Answers 2

up vote 17 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
5  
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
3  
@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
1  
@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
    
@IBS: Hey no problem. I never thought about it. Anyhow good that you got the answer. That is important. –  user9413 May 23 '11 at 13:25
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.