If $p^n$ is a prime power, how can we show that there exists a field $F\supseteq\mathbb{F}_p$ such that $$x^{p^n}-x=(x-\theta_1)(x-\theta_2)\cdots (x-\theta_{p^n})$$ for some $\theta_i\in F$?
Using this, can we prove the existence of a field having exactly $p^n$ elements?
I also have an interesting question that seems tougher: does it follow that there exist prime polynomials of every degree in $\mathbb{F}_p[x]$ without using the Mobius inversion formula for number of irreducibles?
Let $F$ be a finite field with $|F|=q$, and let $K\subset F$ be a subfield of $F$. Then, we'll show that $x^q-x\in K[x]$ can be factored over $F[x]$ as $\displaystyle\prod_{\theta\in F}(x-\theta)$, i.e. $F$ is a splitting field of $x^q-x$ over $K$.
Since $\deg(x^q-x)=q$, the number of roots in $F$ is at most $q$. Since $\theta^q=\theta$ in $F$, all elements of $F$ are roots of $x^q-x$, and since $|F|=q$, $x^q-x$ splits in $F$, and cannot split in any field of smaller size.
Now, let $q=p^n$, and consider $P(x)=x^q-x\in\mathbb{F}_q[x]$. Let $F$ be its splitting field over $\mathbb{F}_p$. Let's see what happens when we look at the formal derivative of $P$. We have $P'(x)=qx^{q-1}-1 \equiv -1\pmod{q}$, so since $\gcd(P, P')=1$, $P$ has no repeated roots (try to prove this) and must have $q$ distinct roots in $F$. Now, consider the set $L=\{\theta\in F:\theta^q-\theta=0\}$. Note that $L$ is a subfield of $F$(*).
Since $L$ contains all the roots of $P$, $P$ splits in $L$, which means $F\subseteq L\implies F=L$. $|L|=q$, so $L$ is a finite field of $p^n$ elements as wanted.
(*) $0\in L$, $a,b\in L$ so $(a-b)^q=a^q-b^q=a-b\in L$, $(ab^{-1})^q=a^qb^{-q}=ab^{-1}$ so $ab^{-1}\in L$ where $b\neq 0_L$.