Proving irreducibility of polynomial over various fields I am working on a problem set from an online course and am struggling to understand a key concept related to proving reducibility / split-ability etc. in a finite field $\mathbb{F}_{p^n}$, as well as the obvious ones like $\mathbb{Q}$. Specifically I'm working on $X^4 + X - 1$ over $\mathbb{F}_3$, $\mathbb{Q}$, and its reduction over $\mathbb{F}_3$ for $\mathbb{F}_{81}$. I understand that $\mathbb{F}_{81}$ is the splitting field because $3^4 = 81$ and $\deg(P) = 4$ but I'm not exactly sure why or how I learned that somewhere. How in general do I approach proving these things? I noted that if $P = P_1 P_2$ their degrees must sum up properly so on the only possibilities are degree 1 and 3 (impossible because has no roots) or 2 and 2.... so how are you supposed to approach these kinds of problems? I'm having trouble both with the theory of finite fields and with whether Eisenstein's criterion applies to this polynomial.
Thanks in advance for your help!
 A: Great questions! The first thing I'll note is that Eisenstein's criterion really doesn't apply here. Eisenstein allows you to leverage data about the prime ideals the coefficients of your polynomial live in to conclude whether or not the polynomial must be irreducible. Since $\mathbb{F}_{3}$ is a field, all the ideals are trivial, and so you can't really make use of that information as you can over, say, $\mathbb{Z}[X]$, where Gauss's lemma allows you to extend that irreducibility to $\mathbb{Q}[X]$ as well. Over finite fields especially, the techniques become a little different. 
Your observations about the possible ways your polynomial can reduce is a good start! Generally, a powerful technique for low degree polynomials is to recursively build lists of irreducible polynomials of lower degree, and then perform division to determine whether any of the lower degree irreducibles divide your polynomial. We can use some tricks to speed up computation as well.
A degree $4$ polynomial that is reducible must either be written as a product of two quadratic polynomials, or the product of a linear polynomial and a cubic polynomial. Let's tackle the latter case first. If a linear polynomial divides $f(X) = X^{4}+X-1$, then that means it must have a root over $\mathbb{F}_{3}$. It's not so hard to check that this is impossible by simply plugging in. We see $f(0) = -1, f(1) = 1, f(2) = 17 \equiv 2 \pmod 3$, so $f$ has no roots over $\mathbb{F}_{3}$. We can therefore focus exclusively on the case where $f(X)$ is a product of irreducible quadratics (note that they must be irreducible, since otherwise a linear factor would divide $f$).
Let's compute the irreducible quadratics over $\mathbb{F}_{3}$. A quadratic polynomial is irreducible over $\mathbb{F}_{3}$ if and only if it has no roots over $\mathbb{F}_{3}$, since the only way a quadratic polynomial can factor is into a product of linear factors. Hence, we want to compute the quadratic polynomials over $\mathbb{F}_{3}$ which have no roots over $\mathbb{F}_{3}$. There aren't all that many possibilities to check. Since the leading coefficient must be nonzero, and the constant term must also clearly be nonzero (else $0$ would certainly be a root!), there are only $2\cdot 3 \cdot 2 = 12$ possibilities. It's not hard to compute that the only quadratics with no roots over $\mathbb{F}_{3}$ are $X^{2}+1, X^{2}+X+2,$ and $X^{2}+2X+2$. You should verify this to test your understanding! 
Now we're in the home stretch. We need to verify that none of these polynomials divides $f$, but we really only need to test that two of them do not divide $f$, since we're checking if $f$ splits into a product of TWO irreducibles. For this, you can use polynomial division, just as you might over $\mathbb{Q}[X]$; $\mathbb{F}_{3}$ is a field, so $\mathbb{F}_{3}[X]$ is a Euclidean domain. I leave this last task to you, though feel free to comment if you need more assistance here. 
A note on your questions on why $\mathbb{F}_{81}$ is the splitting field for $f$ over $\mathbb{F}_{3}$: it is actually a bit of a subtle matter. Since $f$ is irreducible of degree $4$, it follows that $\mathbb{F}_{3}[x]/\langle f\rangle \cong \mathbb{F}_{3^{4}} = \mathbb{F}_{81}$. Hence $\mathbb{F}_{81}$ must contain a root of $f$. There is a nice theorem that says for any finite field $F$, any finite extension of $F$ is normal, whence any extension of $F$ containing a root of $f$ must contain all roots of $f$. This takes a bit of work to show, of course, but there are some good resources on the web which explain why this is true. These notes, for example, are a wonderful resource.
