Polynomials over a field factor uniquely, just like integers. The hard part, as with integers, is telling whether a given polynomial is "prime," i.e. irreducible. This page collects the standard tools for that: roots, reduction mod $p$, shifting, and Eisenstein's criterion. Think of it as a toolbox. Most problems come down to picking the right tool.
Everything starts with long division, which works over any field.
Suppose $F$ is a field, $f, g \in F[x]$, and $g \neq 0$. Then $\exists$ unique polynomials $q, r \in F[x]$ s.t. $f = gq + r$ and ($r = 0$ or $\deg r < \deg g$).
Existence was sketched on Integral Domains. For uniqueness, suppose $gq + r = gq' + r'$ with both remainders $0$ or of degree $< \deg g$. Then $g(q - q') = r' - r$. If $q \neq q'$, the left side has degree $\ge \deg g$ (degrees add, since $F$ is an integral domain), but the right side has degree $< \deg g$ or is $0$. So $q = q'$, and then $r = r'$. $\blacksquare$
Watch it run. Each step kills the leading term of what's left by subtracting the right multiple of $g$, and the degree of the remainder drops until it's below $\deg g$. The one operation that needs a field is dividing by $g$'s leading coefficient; pick the $\mathbb{Q}$ example with $2x - 1$ to see fractions appear.
Since $F[x]$ is a Euclidean domain, the chain ED $\Rightarrow$ PID $\Rightarrow$ UFD gives the main structural fact for free.
If $F$ is a field then $F[x]$ is a UFD.
What about polynomials over $\mathbb{Z}$, which isn't a field? $\mathbb{Z}[x]$ isn't even a PID. The bridge is Gauss's Lemma, which lets you move between $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$ (and more generally between $R[x]$ and $F[x]$ for $F$ the field of fractions of $R$).
Suppose that $R$ is a UFD and $F$ is its field of fractions. If $f$ is a non-constant polynomial that is irreducible in $R[x]$, then it is irreducible in $F[x]$.
"Non-constant" matters. The constant $2$ is irreducible in $\mathbb{Z}[x]$ (it's not a unit there, and $2 = ab$ forces $a$ or $b = \pm 1$), but in $\mathbb{Q}[x]$ it's a unit, and units are never irreducible. Gauss's Lemma is about polynomials of degree $\ge 1$.
Gauss's Lemma is also the key step in proving the following, which is how we know $\mathbb{Z}[x]$ (and $\mathbb{Z}[x, y]$, and so on) are UFDs.
A ring $R$ is a UFD if and only if $R[x]$ is a UFD.
This is item 5 from the map on Integral Domains: $\mathbb{Z}$ is a UFD, so $\mathbb{Z}[x]$ is a UFD, even though it isn't a PID.
Now the tools for factoring. The first connects roots to linear factors.
If $F$ is a field and $f \in F[x]$ then an element $\alpha \in F$ is a root of $f \iff (x-\alpha) \mid f(x)$.
Proof.
The proof also shows that dividing by $x - \alpha$ always leaves the remainder $f(\alpha)$. (Try the $\mathbb{F}_5$ example in the long division widget.) Each root peels off a linear factor and lowers the degree by one, so:
If $F$ is a field then any non-zero polynomial $f \in F[x]$ has at most $\deg(f)$ roots.
"Field" is doing real work here. In $\mathbb{Z}/8\mathbb{Z}$, the degree-$2$ polynomial $x^2 - 1$ has four roots: $1, 3, 5, 7$. The proof breaks because $\mathbb{Z}/8\mathbb{Z}$ has zero divisors: $(x - 3)(x - 5)$ can vanish at $x = 1$ without either factor vanishing.
Next, irreducible polynomials behave like prime numbers with respect to gcds. A word first: a polynomial whose leading coefficient is $1$ gets its own name, because every nonzero polynomial over a field is a unit times exactly one of them.
A polynomial is monic if its leading coefficient is $1$.
Suppose $F$ is a field, $f, g \in F[x]$, and $f$ is irreducible. Then either $f \mid g$ or $\gcd(f, g) = 1$.
If $F$ is a field, $f, g \in F[x]$ are both monic and irreducible, then either $f = g$ or $\gcd(f, g) = 1$.
For small degrees, irreducibility is just a question about roots.
If $f$ is a polynomial with coefficients in a field $F$ and if $\deg(f) = 2$ or $3$ then $f$ is irreducible over $F$ if and only if $f$ has no roots in $F$.
Proof. If $f = gh$ with neither a unit (constant), then $\deg g + \deg h = 2$ or $3$ with both $\ge 1$, so one of them has degree $1$, say $g = ax + b$. Then $-b/a$ is a root of $f$. Conversely, a root gives a linear factor by Bezout. $\blacksquare$
Only degrees $2$ and $3$! A degree-$4$ polynomial can factor as two quadratics without having any roots: $x^4 + 2x^2 + 1 = (x^2 + 1)^2$ has no real roots but is reducible over $\mathbb{R}$. "No roots, so irreducible" is a classic wrong move for degree $\ge 4$.
Over a finite field, "no roots" is a finite check: plug in every element. Build some polynomials and test them.
Over $\mathbb{Q}$ you can't plug in everything, but you only have to try finitely many candidates.
Suppose $f \in \mathbb{Z}[x]$ is given by $f(x) = \sum_{i=0}^n a_i x^i$, $a_0, a_n \neq 0$. If $f(p/q) = 0$ for some $p/q \in \mathbb{Q}$ with $(p, q) = 1$ then $p \mid a_0$ and $q \mid a_n$.
Proof. Multiply $f(p/q) = 0$ by $q^n$: $a_n p^n + a_{n-1}p^{n-1}q + \dots + a_1 p q^{n-1} + a_0 q^n = 0$. Every term but the last is divisible by $p$, so $p \mid a_0 q^n$, and since $(p, q) = 1$, $p \mid a_0$. Similarly every term but the first is divisible by $q$, so $q \mid a_n p^n$, so $q \mid a_n$. $\blacksquare$
Find the rational roots of $f(x) = 2x^3 - 3x^2 - 3x + 2$.
$p \mid 2$ and $q \mid 2$, so the only candidates are $\pm 1, \pm 2, \pm \frac12$. Testing them: $f(2) = 0$, $f(-1) = 0$, $f(\frac12) = 0$, and the other three aren't roots. So $f(x) = 2(x - 2)(x + 1)(x - \frac12) = (x - 2)(x + 1)(2x - 1)$.
One last small tool: shifting the variable doesn't change irreducibility.
If $F$ is a field, $f, g \in F[x]$, $\deg f, \deg g \ge 1$, and $f(x) = g(x+a)$ for some $a \in F$, then $f$ is irreducible if and only if $g$ is.
(The map $h(x) \mapsto h(x + a)$ is a ring isomorphism of $F[x]$ that preserves degrees, with inverse $h(x) \mapsto h(x - a)$, so it carries factorizations to factorizations.) It looks useless on its own, but it's the secret weapon for Eisenstein below.
The last two tools work over $\mathbb{Z}$ (and then over $\mathbb{Q}$ by Gauss's Lemma). The first: if a polynomial is irreducible after you reduce its coefficients mod something, it was irreducible to begin with.
Suppose that $R$ is an ID and that $I \subseteq R$ is a proper ideal, and that $f \in R[x]$ is a non-constant monic polynomial. If the image of $f(x)$ in $(R/I)[x]$ cannot be factored into two polynomials of smaller degree, then $f$ is irreducible in $R[x]$.
The notes phrase the hypothesis as "the image of $f$ in $(R/I)[x]$ is irreducible." That's what it means when $R/I$ is a field (the usual case, like $\mathbb{Z}/p\mathbb{Z}$). We spelled it out above because "irreducible" was only defined in integral domains, and $R/I$ might not be one. The converse is false: $x^2 + 1$ is irreducible over $\mathbb{Z}$ but factors mod $2$ as $(x + 1)^2$. A factorization mod $p$ proves nothing.
$x^2 + 1 = (x + 1)^2$ in $\mathbb{F}_2[x]$ is exactly why $\mathbb{F}_2[x]/(x^2 + 1)$ had a zero divisor on Prime & Maximal Ideals.
And the most famous criterion of all.
Suppose $f(x) = \sum_{i=0}^n a_i x^i \in \mathbb{Z}[x]$, $\gcd(a_0, \dots, a_n) = 1$, that $p$ is a prime number, $p \mid a_i$ for $0 \le i < n$, $p \nmid a_n$, and $p^2 \nmid a_0$. Then $f$ is irreducible over $\mathbb{Z}$ (and therefore over $\mathbb{Q}$ by Gauss's Lemma).
Proof. Suppose $f$ satisfies the hypotheses and, by way of contradiction, $\exists g, h \in \mathbb{Z}[x]$ with $f(x) = g(x)h(x)$ and $\deg g, \deg h \ge 1$. (A factorization with a constant factor $c \neq \pm 1$ is impossible, because $c$ would divide every coefficient and $\gcd(a_0, \dots, a_n) = 1$.)
Let $\tilde{f}, \tilde{g}$, and $\tilde{h}$ be the images of $f, g$, and $h$ in $(\mathbb{Z}/p\mathbb{Z})[x]$. Then $\tilde{f}(x) = \overline{a_n} x^n = \tilde{g}(x)\tilde{h}(x)$. The leading coefficients of $g$ and $h$ multiply to $a_n$, so neither is $0 \pmod p$, and $\deg \tilde g = \deg g \ge 1$, $\deg \tilde h = \deg h \ge 1$.
Since $(\mathbb{Z}/p\mathbb{Z})[x]$ is a UFD, the only way to factor $\overline{a_n}x^n$ is $\tilde g = c x^k$, $\tilde h = c' x^{n-k}$ with $k, n - k \ge 1$. So the constant coefficients of $g$ and $h$ are both $0 \pmod p$. Then the constant coefficient of $f$, their product, is $0 \pmod{p^2}$. Contradiction $\implies f$ is irreducible over $\mathbb{Z}$. $\blacksquare$
Eisenstein's criterion is a vibe check. Every coefficient is divisible by $p$, except the boss at the top, and the one at the bottom is divisible by $p$ but only once. Pass the vibe check and you're irreducible. Fail it and... the test has nothing to say to you.
Time to use everything. Are the following polynomials irreducible in $\mathbb{Q}[x]$?
$f(x) = x^2 + x + 1$
Mod $2$: degree $2$ polynomial with no roots in $\mathbb{Z}/2\mathbb{Z}$ ($f(0) = 1$, $f(1) = 3 = 1$) $\implies$ irreducible over $\mathbb{Z}/2\mathbb{Z}$ $\implies$ irreducible over $\mathbb{Z}$ (reduction test; $f$ is monic) $\implies$ irreducible over $\mathbb{Q}$ (Gauss).
$f(x) = x^4 + 10x^3 + 6x + 2$
Irreducible by Eisenstein at $2$: $2$ divides $10, 0, 6, 2$, $2 \nmid 1$, and $4 \nmid 2$.
$f(x) = x^4 + 1$
Eisenstein doesn't apply directly (the constant term is $1$). But shift: $f(x+1) = (x+1)^4 + 1 = x^4 + 4x^3 + 6x^2 + 4x + 2$ is irreducible by Eisenstein at $2$ $\implies f(x)$ is irreducible.
$f(x) = x^{p-1} + x^{p-2} + \dots + x + 1$, $p$ a prime.
$f(x) = \dfrac{x^p - 1}{x - 1} \implies f(x+1) = \dfrac{(x+1)^p - 1}{x} = x^{p-1} + \binom{p}{1}x^{p-2} + \binom{p}{2}x^{p-3} + \dots + \binom{p}{p-2}x + \binom{p}{p-1}$.
$p \mid \binom{p}{i}$ for $1 \le i \le p-1$, and $p^2 \nmid \binom{p}{p-1} = p$, so this is Eisenstein at $p$ $\implies f$ is irreducible.
Work through those examples yourself in the checker. Each coefficient lights up green when it does what Eisenstein wants for the prime you picked.
Pick the right tool for each.
Is $x^3 + x + 1$ irreducible over $\mathbb{Q}$?
Yes. Either way works:
Is $x^4 - 10x^2 + 1$ irreducible over $\mathbb{Q}$? (Hint: it has no rational roots, but that isn't enough in degree $4$.)
Yes, but it takes work. Rational roots would be $\pm 1$, and $f(\pm 1) = -8$, so there are no linear factors. By Gauss's Lemma, any factorization over $\mathbb{Q}$ gives one over $\mathbb{Z}$ into monic quadratics: $(x^2 + ax + b)(x^2 - ax + c)$ (the $x^3$ coefficient is $0$, so the middle terms are $\pm a$).
Comparing coefficients: $bc = 1$, $a(c - b) = 0$, $b + c - a^2 = -10$. If $a = 0$ then $b + c = -10$ with $bc = 1$: no integer solutions. If $c = b$ then $b^2 = 1$ so $b = \pm 1$, and $a^2 = 2b + 10 \in \{12, 8\}$: not a square. So no factorization, and $f$ is irreducible. (Its roots are $\pm\sqrt2 \pm \sqrt3$.)
Find all monic irreducible polynomials of degree $2$ over $\mathbb{F}_3$.
There are $9$ monic quadratics $x^2 + bx + c$. By the Lemma, a quadratic is irreducible iff it has no roots in $\mathbb{F}_3 = \{0, 1, 2\}$. Checking each: the irreducible ones are
$$x^2 + 1, \qquad x^2 + x + 2, \qquad x^2 + 2x + 2.$$
(Count check: the reducible monic quadratics are $(x - r)(x - s)$ with $r \le s$, and there are $\binom{3}{2} + 3 = 6$ of those. $9 - 6 = 3$.)
Bezout's theorem plus the at-most-$\deg f$-roots corollary gives a famous number theory fact almost for free.
Let $p$ be prime. Prove that in $\mathbb{F}_p[x]$, $x^{p-1} - 1 = (x - 1)(x - 2)\cdots(x - (p-1))$, and deduce Wilson's theorem: $(p - 1)! \equiv -1 \pmod p$.
Proof. By Fermat's little theorem, $a^{p-1} = 1$ for every $a \in \mathbb{F}_p^\times$, so $1, 2, \dots, p - 1$ are all roots of $g(x) = x^{p-1} - 1$. By Bezout, $(x - 1)$ divides $g$; write $g = (x - 1)g_1$. Plugging in $a = 2$: $0 = (2 - 1)g_1(2)$, and $2 - 1 \neq 0$ in the field, so $g_1(2) = 0$, and $(x - 2) \mid g_1$. Continuing, $h(x) = (x - 1)(x - 2)\cdots(x - (p-1))$ divides $g$.
Both are monic of degree $p - 1$, so $g = h \cdot c$ with $c$ a constant, and comparing leading coefficients gives $c = 1$. So $g = h$.
Now compare constant terms: $g(0) = -1$, and $h(0) = (-1)^{p-1}(p-1)!$. If $p$ is odd, $(-1)^{p-1} = 1$, so $(p-1)! = -1$ in $\mathbb{F}_p$. If $p = 2$, $(p-1)! = 1 = -1$ in $\mathbb{F}_2$. Either way, $(p-1)! \equiv -1 \pmod p$. $\blacksquare$