Factorise $x^5+x+1$

If you suspect there exists a factorization over $\mathbb{Q}[x]$ into polynomials of degree 2 and 3, but you just don't know their coefficients, one way is to write it down as

$x^5 + x + 1 = (x^2 + ax + b)(x^3 + cx^2 + dx + e)$ where the coefficients are integers (by Gauss' lemma). And then expand and solve the system.

Then $a + c = 0, b + ac + d = 0, bc + ad + e = 0, ae + bd = 1, be = 1$. So we get $c = -a$ and $b = e = 1$ or $b = e = -1$.

In the first case we reduce to $1 - a^2 + d = 0, -a + ad + 1 = 0, a + d = 1$ which gives $d = 1 - a, 1 - a^2 + 1 - a = 0, 1 - a^2 = 0$ so $a = 1, b = 1, c = -1, d = 0, e = 1$.

Substituting gives us $x^5 + x + 1 = (x^2 + x + 1)(x^3 - x^2 + 1)$

If the factorization was not over $\mathbb{Q}[x]$ then things would get more complicated because I could not assume $b = e = +/- 1$.

With algebraic identities, this is actually rather natural:

Remember if we had all powers of $x$ down to $x^0=1$, we could easily factor: $$x^5+x^4+x^3+x^2+x+1=\frac{x^6-1}{x-1}=\frac{(x^3-1)(x^3+1)}{x-1}=(x^2+x+1)(x^3+1),$$ so we can write: \begin{align}x^5+x+1&=(x^2+x+1)(x^3+1)-(x^4+x^3+x^2)\\ &=(x^2+x+1)(x^3+1)-x^2(x^2+x+1)\\ &=(x^2+x+1)(x^3+1-x^2). \end{align}

Alternatively note that $$\begin{align}x^5 + x + 1 &= x^5 - x^2 + x^2 + x + 1\\ & =x^2(x^3-1) + \color{red}{x^2+x+1} \\ & = x^2(x-1)\color{red}{(x^2+x+1)} + \color{red}{x^2+x+1} \\& =\color{blue}{(x^3-x^2+1)}\color{red}{(x^2+x+1)} \end{align}$$

where we used the well known identity $x^3 - 1 = (x-1)(x^2+x+1)$ in the third equality.

---

Meta: whilst the first step may seem arbitrary and magical, it is natural to want to insert a term like $x^2$ or $x^3$ into the equation in order to get some traction with factorising $x^5 + x^k$.