I want to prove that given a prime $p$ and a positive integer $n$, there is a finite field of order $p^n$. I want to do it by showing that there is an irreducible polynomial of degree $n$ over $\mathbf F_p$.
I know the following fact: Let $a_k$ be the number of degree $k$ monic irredcuibles over $\mathbf F_p$. Then $$p^n=\sum_{d|n} da_d\tag{1}$$ Using this and the Mobius inversion, we get a formula for finding the number of monic irreducibles of degree $n$ over $\mathbf F_p$.
Unfortunately, I am unable to prove (1) without assuming the existence of $\mathbf F_{p^n}$ in advance.
What we really want to show is that the polynomial $x^{p^n} - x$ factors as the product of every irreducible polynomial of degree dividing $d$, exactly once each. Your desired result follows by taking degrees.
This in turn follows from the observation that if $f(x)$ is an irreducible polynomial of degree $d$, then $\mathbb{F}_p[x]/f(x)$ is a finite field of order $p^d$ (note that I am not assuming that these fields exist for all $d$). On any such field we have $y^{p^n} = y$ for all $y$ in the field, so in particular $x^{p^n} \equiv x \bmod f(x)$, so $f(x)$ divides $x^{p^n} - x$.
Conversely, if $f(x)$ divides $x^{p^n} - x$, then $\mathbb{F}_p[x]/f(x)$ is a finite field of order $p^d$, so $f(x)$ divides $x^{p^d} - x$. We have
$$\gcd(x^{p^a} - x, x^{p^b} - x) = x^{p^{\gcd(a, b)}} - x$$
and taking $a = n, b = d$ gives $\gcd(a, b) = d$, so $d \mid n$.
Finally, by computing the derivative of $x^{p^n} - x$ we can see that it's squarefree, so each irreducible factor occurs with multiplicity $1$.