# $f(x)$ is irreducible over finite field $F_p$ , does $f(x)$ split over $F_p / \langle f(x) \rangle$?

I want to know whether it is possible to generalize the next thing exercise.

$$x^4 + x + 1$$ is irreducible over $$F_2[x]$$ , so $$F_2[x]/\langle x^4 +x+1\rangle = span_{F_2} \{1,\bar{x} , \bar{x}^2,\bar{x}^3\} \cong F_{2^4}$$. So $$\bar{x}^4 + \bar{x} +1 = 0$$ in $$F_2[x]/\langle x^4+x+1\rangle$$ and due to the fact that in $$F_2$$ $$(a+b)^2 = a^2 + b^2$$ ,we get that $$\bar{x}^8 + \bar{x}^2 +1 = 0=(\bar{x}^4 + \bar{x} +1)^2 = 0$$ so $$\bar{x}^2$$ is also a root. And similarly $$\bar{x}^4 , \bar{x}^8$$ are roots. A simple check gives that those are 4 different roots, thus indeed the polynomial splits.

So my question, is there a way to use the fact that $$F_{p^n}$$ is the splliting field of $$x^{p^n}-x$$ over $$F_p$$ and the fact that for every $$f(x)$$ irreducible polynomial over $$F_p[x]$$ from degree $$n$$ , $$F_p[x]/ \langle p(x) \rangle \cong F_{p^n}$$ to show that $$f(x)$$ splits over $$F_p[x]/ \langle f(x) \rangle$$ ?

• Yes. This always happens. If you have studied Galois theory, then you could realize that $K=\Bbb{F}_p[x]/\langle f(x)\rangle$ is a Galois extension of $\Bbb{F}_p$. – Jyrki Lahtonen Feb 26 at 20:58
• sorry, but I am not familiar with Galois theory. =( – dan Feb 26 at 21:04
• This is a relatively common question. I gave a few links to earlier threads in this recent incarnation. Basically they are all saying the same thing you observed. Some use the language of Galois theory and Frobenius automorphism. Some just raise the roots to $p$th power (which means exactly the same thing!). – Jyrki Lahtonen Feb 26 at 21:09
• @JyrkiLahtonen: The earlier threads mingle the question with deeper Galois-theoretical questions (about conjugacy and Galoisness), so I think this one has a raison d'etre. – darij grinberg Feb 26 at 21:34
• Nothing wrong with your answer @darijgrinberg. I think we (=the site) have danced around this question multiple times (the list of questions linked/related to the one above give many hits), but I couldn't find the best version. Most of the other takes on this are rather terse in comparison to yours, so all is well :-) – Jyrki Lahtonen Feb 26 at 22:13

Yes, your conjecture is true and can be proven without Galois theory (@commenters):

Theorem 1. Let $$K$$ be a finite field. Let $$f \in K\left[x\right]$$ be an irreducible polynomial. Let $$L$$ be the field $$K\left[t\right] / \left(f\left(t\right)\right)$$. Then, $$f$$ factors into linear polynomials over the field $$L$$.

Note that I have used two different indeterminates $$x$$ and $$t$$ here in order to avoid the awkwardness of having a polynomial in $$x$$ over a ring that already sort-of contains an $$x$$ in it. This is either necessary or redundant depending on the pedantic minutiae of your definition of polynomial rings; in either case, it does not hurt.

Proof of Theorem 1. Let $$q = \left|K\right|$$. It is well-known that for any commutative $$K$$-algebra $$A$$, the map $$A \to A,\ a \mapsto a^q$$ is a $$K$$-algebra endomorphism of $$A$$ (since any $$a, b \in A$$ satisfy $$\left(a+b\right)^q = a^q + b^q$$ and $$\left(ab\right)^q = a^q b^q$$, and since each $$\lambda \in K$$ satisfies $$\lambda^q = \lambda$$). This endomorphism will be denoted by $$F_A$$, and is called the Frobenius endomorphism of $$A$$.

Let $$n$$ be the degree of $$f$$. For each polynomial $$g \in K\left[t\right]$$, let $$\overline{g}$$ be the projection of $$g \in K\left[t\right]$$ onto the quotient ring $$K\left[t\right] / \left(f\left(t\right)\right) = L$$. Let $$u = \overline{t} \in L$$. Let $$F$$ be the map $$F_L$$. Thus, $$F$$ sends each $$a \in L$$ to $$a^q$$ (by the definition of $$F_L$$). Hence, for each nonnegative integer $$i$$ and each $$a \in L$$, we have \begin{align} F^i\left(a\right) = a^{q^i} \label{darij1.pf.t1.Fi} \tag{1} \end{align} (indeed, this can be proven by induction on $$i$$, using the previous sentence in the induction step).

We shall show that $$F^0\left(u\right), F^1\left(u\right), \ldots, F^{n-1}\left(u\right)$$ are $$n$$ distinct roots of $$f$$ in $$L$$. This will quickly yield that $$f$$ factors into linear polynomials over $$L$$. Let us proceed in three steps:

Claim 1: The $$n$$ elements $$F^0\left(u\right), F^1\left(u\right), \ldots, F^{n-1}\left(u\right)$$ of $$L$$ are distinct.

Proof of Claim 1. Assume the contrary. Thus, there exist two elements $$i$$ and $$j$$ of $$\left\{0,1,\ldots,n-1\right\}$$ such that $$i and $$F^i\left(u\right) = F^j\left(u\right)$$. Consider these $$i$$ and $$j$$. We have $$i < j$$, thus $$q^i < q^j$$ (since $$q = \left|K\right| > 1$$).

Let $$a \in L$$ be arbitrary. We are going to prove that $$a^{q^j} - a^{q^i} = 0$$. Indeed, we have $$a \in L = K\left[t\right] / \left(f\left(t\right)\right)$$; in other words, $$a = \overline{s}$$ for some polynomial $$s \in K\left[t\right]$$. Consider this $$s$$. But $$s = s\left(t\right)$$, so that $$\overline{s} = \overline{s\left(t\right)} = s\left(\overline{t}\right)$$ (since $$s$$ is a polynomial with coefficients in $$K$$). In view of $$u = \overline{t}$$, this rewrites as $$\overline{s} = s\left(u\right)$$. Hence, $$a = \overline{s} = s\left(u\right)$$. But $$F^i$$ is a $$K$$-algebra homomorphism (since $$F$$ is a $$K$$-algebra homomorphism), and thus commutes with the application of any polynomial over $$K$$. Hence, in particular, $$F^i$$ commutes with $$s$$. Thus, $$F^i\left(s\left(u\right)\right) = s\left(F^i\left(u\right)\right)$$. Now, applying $$F^i$$ to both sides of the equality $$a = s\left(u\right)$$, we find \begin{align} F^i\left(a\right) = F^i\left(s\left(u\right)\right) = s\left(F^i\left(u\right)\right) . \end{align} Comparing this with \eqref{darij1.pf.t1.Fi}, we obtain $$a^{q^i} = s\left(F^i\left(u\right)\right)$$. The same argument (applied to $$j$$ instead of $$i$$) yields $$a^{q^j} = s\left(F^j\left(u\right)\right)$$. Hence, \begin{align} a^{q^i} = s\left(\underbrace{F^i\left(u\right)}_{= F^j\left(u\right)}\right) = s\left(F^j\left(u\right)\right) = a^{q^j} . \end{align} In other words, $$a^{q^j} - a^{q^i} = 0$$.

Now, forget that we fixed $$a$$. We thus have shown that $$a^{q^j} - a^{q^i} = 0$$ for each $$a \in L$$. In other words, each $$a \in L$$ is a root of the polynomial $$x^{q^j} - x^{q^i} \in K\left[x\right]$$. This polynomial is nonzero (since $$q^i < q^j$$, so that the terms $$x^{q^j}$$ and $$x^{q^i}$$ do not cancel) and has degree $$q^j$$ (since $$q^i < q^j$$), and thus has at most $$q^j$$ many roots in $$L$$ (since any nonzero polynomial over $$L$$ of degree $$d$$ has at most $$d$$ many roots in $$L$$). Since each $$a \in L$$ is a root of this polynomial, we thus conclude that there are at most $$q^j$$ many $$a \in L$$. In other words, $$\left|L\right| \leq q^j$$.

But $$L = K\left[t\right] / \left(f\left(t\right)\right)$$ is a $$K$$-vector space of dimension $$n$$ (since the polynomial $$f$$ has degree $$n$$), and thus has size $$\left|K\right|^n = q^n$$ (since $$\left|K\right| = q$$). Hence, $$\left|L\right| = q^n$$, so that $$q^n = \left|L\right| \leq q^j$$ and therefore $$n \leq j$$. This contradicts $$j \in \left\{0,1,\ldots,n-1\right\}$$. This contradiction shows that our assumption was wrong. Hence, Claim 1 is proven.

Claim 2: The $$n$$ elements $$F^0\left(u\right), F^1\left(u\right), \ldots, F^{n-1}\left(u\right)$$ of $$L$$ are roots of $$f$$.

Proof of Claim 2. From $$u = \overline{t}$$, we obtain $$f\left(u\right) = f\left(\overline{t}\right) = \overline{f\left(t\right)}$$ (since $$f$$ is a polynomial with coefficients in $$K$$). Thus, $$f\left(u\right) = \overline{f\left(t\right)} = 0$$ (since $$f\left(t\right) \equiv 0 \mod f\left(t\right)$$).

Now, let $$i \in \left\{0,1,\ldots,n-1\right\}$$ be arbitrary. Then, $$F^i$$ is a $$K$$-algebra homomorphism (since $$F$$ is a $$K$$-algebra homomorphism), and thus commutes with the application of any polynomial over $$K$$. Hence, in particular, $$F^i$$ commutes with $$f$$. Thus, $$F^i\left(f\left(u\right)\right) = f\left(F^i\left(u\right)\right)$$. Hence, $$f\left(F^i\left(u\right)\right) = F^i\left(\underbrace{f\left(u\right)}_{=0}\right) = F^i\left(0\right) = 0$$ (again since $$F^i$$ is a $$K$$-algebra homomorphism). In other words, $$F^i\left(u\right)$$ is a root of $$f$$.

Now, forget that we fixed $$i$$. We thus have shown that $$F^i\left(u\right)$$ is a root of $$f$$ for each $$i \in \left\{0,1,\ldots,n-1\right\}$$. In other words, the $$n$$ elements $$F^0\left(u\right), F^1\left(u\right), \ldots, F^{n-1}\left(u\right)$$ of $$L$$ are roots of $$f$$. This proves Claim 2.

We are now almost done proving Theorem 1. Claim 2 shows that the $$n$$ elements $$F^0\left(u\right), F^1\left(u\right), \ldots, F^{n-1}\left(u\right)$$ of $$L$$ are roots of $$f$$. Since these $$n$$ elements are distinct (by Claim 1), we thus conclude that the polynomial $$f$$ has (at least) $$n$$ distinct roots over $$L$$. But this polynomial $$f$$ has degree $$n$$; hence, if it has $$n$$ distinct roots over $$L$$, then it factors into linear polynomials over $$L$$. So we have proven that $$f$$ factors into linear polynomials over $$L$$. This proves Theorem 1. $$\blacksquare$$