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.

I'm investigating irreducible polynomials over finite fields at the moment, and I wanted to know if there is a formula for the number of irreducible polynomials of degree n over a fixed finite field $\mathbb{F}_q$. Wolfram MathWorld gives the formula \begin{equation} \frac{1}{n}\sum_{d|n}\mu(\frac{n}{d})q^d \end{equation} However, neither it nor the OEIS page it links to offers any proof for this as far as I can tell, and I'm kind of confused by the presence of a divisor sum; I don't see why such a sum would appear in dealing with these polynomials.

So how does one prove this formula?

share|improve this question
1  
This question has been answered previously on this site. See for example here –  Dilip Sarwate Dec 19 '11 at 15:53
1  
Anyhow, this looks like the Mobius inversion formula. If $f(n)$ is the number of irreducible polynomials, this formula suggests that $q^n= \sum_{d|n} df(d) $, which doesn't look obvious to me... –  N. S. Dec 19 '11 at 15:56
4  
@N.S.: That's obvious once you know that $x^{q^n}-x$ is the product of all the (monic) irreducible polynomials over $\mathbb{F}_q$ of degree dividing $n$. –  Chris Eagle Dec 19 '11 at 16:05
    
@Dilip: Sorry; for some reason I didn't notice. Thanks for pointing that out. –  William D. Dec 19 '11 at 17:13
add comment

2 Answers 2

up vote 7 down vote accepted

Let $N_q(n)$ be the number of irreducible monic polynomials in $\mathbb{F}_q[x]$ of degree $n$. First prove that $$q^n = \sum_{d|n} d\cdot N_q(d).$$ Then, you can use the additive version of the Möbius inversion formula with $H(n)=q^n$ and $h(n)=nN_q(n)$, so that $H(n)=\sum_{d|n} h(d)$ implies that $h(n)=\sum_{d|n}\mu(\frac{n}{d})H(d)$.

share|improve this answer
    
I always liked to show my students this, whenever I taught algebra. –  Lubin Dec 20 '11 at 3:56
    
It is indeed a very neat application of Mobius inversion! –  Álvaro Lozano-Robledo Dec 20 '11 at 4:06
    
Thank you for pointing this out. –  William D. Dec 20 '11 at 6:32
add comment

You may also have a look at A Classical Introduction to Modern Number theory, by Ireland and Rose, page 84.

share|improve this answer
    
Thank you; that's a very helpful resource. –  William D. Dec 20 '11 at 6:32
add comment

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.