I am trying to find the number of irreducible polynomials of degree $n$ over $\mathbb{F}_p$. Here is what I have done:

(1). Let $K=\mathbb{F}_{p^n}$. Let $M(n,p)$ the number of monic irreducible polynomials of degree $n$ over $\mathbb{F}_p$.

(2). Any root of a monic irreducible polynomial of degree $n$ is a primitive element of $K|\mathbb{F}_p$. Conversely, any primitive element of $K|\mathbb{F}_p$ is a root of a monic irreducible polynomial of degree $n$. Therefore, $$n\cdot M(n,p)=\text{ Number of primitive elements of }K|\mathbb{F}_p$$

(3). But we know that $K^{\times}$ is a cyclic group of order $p^n-1$. The primitive elements of $K|\mathbb{F}_p$ are precisely the generators of the cyclic group $K^{\times}$. The number of such generators are $\varphi(p^n-1)$.

(4). Combining (2) and (3) we conclude that $$M(n,p)=\frac{\varphi(p^n-1)}{n}$$

(5). Any irreducible polynomial of degree $n$ is a nonzero constant multiple of a monic irreducible polynomial of degree $n$. The number of such constants is $p-1$. Therefore the number of such polynomials is $$(p-1)\cdot M(n,p)=\frac{(p-1)\varphi(p^n-1)}{n}$$

So the final answer is $$\frac{(p-1)\varphi(p^n-1)}{n}$$

But my answer does not match with the usual way of solving this question which involves the Mobius inversion formula. What am I doing wrong?


First of all, very well-asked question! which makes it much easier to find the most helpful response.

It seems that you are conflating two different properties into one:

  • a "primitive element" of a field extension $L/K$, which is an element $\alpha\in L$ such that $L=K(\alpha)$;

  • a "primitive element" of a cyclic group, which is a generator of that group.

These two concepts do not correspond exactly with each other.

For example, consider $\Bbb F_9$, which is a degree-2 extension of $\Bbb F_3$. There are 6 elements of $\Bbb F_9$ that are not in $\Bbb F_3$, and any of them serves as a primitive element for the extension $\Bbb F_9/\Bbb F_3$ (in the first sense above). On the other hand, the multiplicative group $\Bbb F_9^\times$ is cyclic of order 8, and thus has $\phi(8)=4$ generators; all of these are primitive elements in the field-extension sense, but there are two other primitive elements that are not generators of the multiplicative group.

We can be super concrete here. Write $\Bbb F_9$ as $\Bbb F_3[x]/\langle x^2+1\rangle$, valid since $x^2+1$ is a degree-2 irreducible polynomial over $\Bbb F_3$. Then the elements of $\Bbb F_9$ are $a+bx$ where $a,b\in\{0,1,2\}$, with addition and multiplication defined as usual for polynomials except that $x^2=-1=2$. In this field, $x$ (or, more pedantically, the image of $x$ under the quotient map from $\Bbb F_3[x]$ to $\Bbb F_3[x]/\langle x^2+1\rangle$) is certainly a primitive element for the field extension. However, $x^4 = (x^2)^2 = 2^2 = 1$, and so $x$ does not generate the multiplicative group $\Bbb F_9^\times$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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