# Existence of an irreducible polynomial over $\mathbb F_p$. [duplicate]

I need to prove that there exists an irreducible polynomial of degree $n$ over $\mathbb F_p$. Here is what I know so far:

• The polynomial $x^{p^n} - x$ is the product of all monic irreducible polynomials of degrees dividing $n$.
• The above polynomial has no roots with multiplicities $>1$. So, has $p^n$ distinct roots in some field.
• A monic irreducible polynomial of degree $d$ over $\mathbb F_p$ has the form $$(x - \alpha)(x-\alpha^p)\cdots(x - \alpha^{p^{d-1}}),$$ where all the $\alpha^{p^i}$ are distinct.
• Map $a\mapsto a^p$ is an automorphism of any finite field of characteristic $p$ and so are all it's iterations.
• I know Möbius inversion formula and can therefore count monic irreducible polynomials from the above information, and get the formula $I_n = \frac 1n\sum_{d|n}p^d\mu(n/d)$ for their number. I don't know that this number is not zero.

What I "do not know" is the existence of a finite field of $p^n$ elements. In fact, my aim is to prove the existence of such a field from the existence of polynomial. I also "do not know" any Galois theory.

It seems that $I_n>0$ could be shown by induction from the above expression, but I run into inclusion-exclusion and get confused. Is there a more transparent argument for why there must be an irreducible polynomial of degree n over $\mathbb F_p$?

Thank you!

## marked as duplicate by Gerry Myerson, Jyrki Lahtonen, Hagen von Eitzen, Brandon Carter, draks ...Jan 24 '13 at 13:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• For another related thread see this question. IIRC the approach in there did not start assuming that finite fields of all prime power orders exists. But yeah, this has been covered many times over in this site. – Jyrki Lahtonen Jan 24 '13 at 11:52
• You don't have to know Galois theory, just open an arbitrary book on algebra and answer your question. $\mathbb{F}_{p^n}$ is the splitting field of $x^{p^n}-x$ over $\mathbb{F}_p$. – Martin Brandenburg Jan 24 '13 at 13:11
• @MartinBrandenburg I know how $F_{p^n}$ is obtained as a splitting field. The point of the exercise is to show the existence of such fields using only the concept of simple extension. – Artem Jan 24 '13 at 13:20
• @GerryMyerson Yes, but the question you cited was answered based on the assumption that the roots of $x^{p^n} - x$ form a field. I am looking to establish that via the answer to my question. – Artem Jan 24 '13 at 13:26
• Artem, I'm sure that in addition to citing that question I suggested having a look at the questions listed under "Related" at the side of the page, as several of them cover the territory that interests you. As there is no sign of that suggestion here, I must have hit the wrong button. My apologies. – Gerry Myerson Jan 24 '13 at 22:21

## 1 Answer

Sometimes it's best to start with a "simple case", and see where that leads us. So let's start by just looking at where $n=q$, a prime number. It is easy to see the polynomial: $f(x) = x^{p^q} - x$ has no repeated root, as its derivative is $p^qx^{p^q - 1} - 1 = -1$ and thus shares no roots with $x^{p^q} - x$.

Since there are only $p$ elements of $\Bbb F_p$, $f$ must have some irreducible factor of degree > $1$. Let's call this factor $g$. If $\deg(g) = t$, we therefore have a field $K$ with $p^t$ elements. Suppose $u$ is a root of $g$ that lies in this field. Then every element of $K$ can be written as a $\Bbb F_p$-linear combination of $\{1,u,...,u^{t-1}\}$. So if $y\in K$:

$\displaystyle f(y) = y^{p^q} - y = \left(\sum_{j=0}^{t-1} \alpha_ju^j\right)^{p^q} - \sum_{j=0}^{t-1}\alpha_ju^j = \sum_{j=0}^{t-1} \alpha_j^{p^q}u^{jp^q} - \sum_{j=0}^{t-1}\alpha_ju^j$.

Since $\alpha_j \in \Bbb F_p$, $\alpha_j^{p^q} = \alpha_j$, and since $u$ is a root of $f$, $u^{jp^q} = u^j$, so $f(y) = 0$. So every element of $K$ is a root of $f$. This, in turn, implies that:

$x^{p^t} - x|x^{p^q} - x$, so $x^{p^t-1}-1|x^{p^q-1}-1$, so $p^t - 1|p^q - 1$, and thus $t|q$. Since by assumption $t > 1$, $t = q$. This is truly "the hard part".

For now, we write $n = q_1^{r_1}q_2^{r_2}\cdots q_k^{r_k}$. Using the same construction, we first construct a field of $p^{q_1}$ elements, then a field of $(p^{q_1})^{q_1} = p^{q_1^2}$ elements, and continuing in like fashion until we have a field of $p^{q_1^{r_1}}$ elements, and then move on to $q_2$, etc. until we exhaust all the prime factors of $n$.

• How does existence of irreducible polynomial of degree $t$ imply existence of a field with $p^t$ elements.? – Siddharth Joshi Jul 4 '17 at 12:11
• If $g(x)$ is an irreducible polynomial of degree $t$ over $\Bbb F_p$, then $K = \Bbb F_p/\langle g(x)\rangle$ is a field, because $\langle g(x)\rangle$ is a maximal ideal. As a vector space, $K$ has dimension $t$ over $\Bbb F_p$ (since the cosets of $1,x,\dots,x^{t-1}$ are linearly independent, by the irreducibility of $g(x)$). Since the elements of $K$ are thus $\Bbb F_p$-linear combinations of these basis elements, this gives exactly $p^t$ elements of $K$ – David Wheeler Jul 5 '17 at 3:17