Calculating the number of irreducible polynomials over a finite field 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?
 A: 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$.
