7
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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! $\endgroup$
    – Jyrki Lahtonen
    Mar 19, 2013 at 4:54
  • $\begingroup$ Do you know that $\mathbb F(q^r)\subset\mathbb F(q^s)$ if and only if $r|s$? $\endgroup$
    – Lubin
    Mar 19, 2013 at 4:54
  • 1
    $\begingroup$ As an aside, Mobius inversion is employed after that formula is already attained (to find $\varphi$ explicitly) - it is not used to obtain it. $\endgroup$
    – anon
    Mar 19, 2013 at 4:56
  • $\begingroup$ @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. $\endgroup$
    – Joe Wells
    Mar 19, 2013 at 4:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Mar 19, 2013 at 5:04

1 Answer 1

Reset to default
7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joe Wells
    Mar 19, 2013 at 5:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .