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.

Let $F=\mathbb{F}_{q}$ be a finite field (so $q=p^k$ for some prime $p$ and positive integer $k$), and let $\varphi(d)$ denote the number of monic irreducible polynomials of degree $d$ in $F[X]$. I'm supposed to show that $\displaystyle{\sum_{d \mid n} d \varphi(d) = q^n}$.

I see there are previous questions about this topic and even a paper, but all (save one) seem to employ the use of the Möbius function and Möbius inversion - both topics I have not covered yet in class. There is also this answer, but it appears to hinge upon the extension having prime degree. Is there some way to show this without explicitly coming up with a formula for the number of irreducible monic polynomials of a given degree in $F[X]$?

Any help would be greatly appreciated.

share|improve this question
1  
Consider elements $\alpha\in F$ and their minimal polynomials $m_\alpha(x)$ over the prime field. What degrees are possible for $m_\alpha$? Why do they all appear as $m_\alpha$ for some $\alpha$? How many elements of $F$ share the same minimal polynomial? Derive an equation! –  Jyrki Lahtonen Mar 19 '13 at 4:54
    
Do you know that $\mathbb F(q^r)\subset\mathbb F(q^s)$ if and only if $r|s$? –  Lubin Mar 19 '13 at 4:54
1  
As an aside, Mobius inversion is employed after that formula is already attained (to find $\varphi$ explicitly) - it is not used to obtain it. –  anon Mar 19 '13 at 4:56
    
@Lubin, Do you mean $\mathbb{F}_{q^r} \subset \mathbb{F}_{q^s}$ iff $r \mid s$? If so, then yes, I do know that. –  JoeDub Mar 19 '13 at 4:57
1  
Joe, $m_\alpha$ is not the minimal polynomial over $F$, but over the prime field of $p$ elements. Nevertheless, they do not share roots, but have as many roots as is indicated by their degree. –  Jyrki Lahtonen Mar 19 '13 at 5:04

1 Answer 1

up vote 3 down vote accepted

The splitting field of $X^{q^n}-X$ is ${\bf F}_{q^n}$. Every irreducible $\pi(X)$ of degree $d$ splits in ${\bf F}_{q^n}$ and every element of ${\bf F}_{q^n}$ is a root of $X^{q^n}-X$, and thus $\pi(X)\mid(X^{q^n}-X)$. Furthermore $X^{q^n}-X$ has no repeated roots so each irreducible $\pi(X)$ of degree $d\mid n$ must appear in its factorization precisely once. Therefore we have the conclusion

$$X^{q^n}-X=\prod_{d\mid n}\prod_{\deg\pi=d}\pi(X).$$

Taking degrees yields $\displaystyle q^n=\sum_{d\mid n}d\varphi(d)$ (and from here Möbius inversion yields $\varphi(d)$).

share|improve this answer
    
Somehow it wasn't clicking that I was examining polynomial degrees. When you put it that way, it's quite clear to me now what is happening. –  JoeDub Mar 19 '13 at 5:14

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.