MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be a prime number. The number of monic irreducible polynomial $P\in{\mathbb F}_p[X]$, in terms of the degree $d$, begins with $${\rm irr}(1)=p,\qquad{\rm irr}(2)=\frac{p(p-1)}2,\qquad{\rm irr}(3)=\frac{p(p^2-1)}3,\qquad{\rm irr}(4)=\frac{5p^2(p^2-1)}{12}.$$ This seems to be the beginning of a nice sequence of polynomials in $p$. Does someone know the general formula?

Motivation. As F. Brunault pointed out to me, there is a polynomial $\Pi_{n,p}$ that vanishes over ${\bf M}_n({\mathbb F}_p)$. Just take the lcm of all the polynomials of degree $n$ over $F_p$. In closed form, it is the product of all the irreducible polynomials of degree $d\le n$, to the power $[\frac{n}{d}]$ (integral part). The degree of $\Pi_{n,p}$ is $$\delta(n)=\sum_{d\le n}d[\frac{n}{d}]{\rm irr}(d).$$ In terms of $n$, this degree is $$\delta(1)=p,\quad\delta(2)=p(p+1),\quad\delta(3)=p(p^2+p+1),\quad\delta(4)=\frac13p(p+1)(5p^2-2p+3).$$

Edit. The values given above for $n=4$ are erroneous.

share|cite|improve this question
up vote 12 down vote accepted

The product of all monic irreducible polynomials of degree dividing $d$ in $\mathbb F_q[x]$ is $$x^{q^d}-x,$$ so from Mobius inversion we get the number of irreducible polynomials of degree $d$ is $$M _d (q) = \frac{1}{d} \sum _{k | d} \mu(k) q ^{d/k} $$ This is known as the necklace polynomial.

share|cite|improve this answer
For $n=4$, the factor $1/4$ does not coincide with Denis's $5/12$. I assume Denis made a calculation mistake? – Tom De Medts Jul 6 '12 at 8:37
Should be $\mu(d)$ in the sum, I assume. – Vladimir Dotsenko Jul 6 '12 at 8:48
And now (after the edit) it should be $\mu(k)$ in the sum, I assume. – Tom De Medts Jul 6 '12 at 9:08
Ah, I can't seem to type a single equation right. Thanks for the correction. – Gjergji Zaimi Jul 6 '12 at 9:12
Thanks; I see the reason: $x^{q^d}-x=0$ is the equation of $K={\mathbb F}_{q^d}$ over $k={\mathbb F}_q$, and every element of $K$ has a unique mimimal polynomial. – Denis Serre Jul 6 '12 at 9:14

Gjergji Zaimi already said it all, but I want to point out a tiny bit longer but equally cute way to derive the same formula. Every monic polynomial over $\mathbb{F}\_q$ decomposes into a product of irreducibles uniquely, hence we have a formal power series equality $$ \frac{1}{1-qt}=\prod_{k\ge 1}\frac{1}{(1-t^k)^{M_k(q)}} $$ (indeed, the coefficient of $t^n$ on the left is the number of monic polynomials of degree $n$, and the coefficient of $t^n$ on the right counts the decompositions into irreducibles with multiplicities). Taking logarithmic derivatives, one can do the M\"obius inversion and arrive at the formula pointed out by Gjergji.

share|cite|improve this answer
This is of course the infinite product formula for the Weil zeta function of $\mathbb A^1$. – Will Sawin Jul 6 '12 at 16:16

Your Answer


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.