Factor $x^5-x+15$

One can factor $$f(x) := x^5 - x \pm 15$$ manually (over $\Bbb Z$) without too much fuss.

First, if $f$ has a linear factor, it has a rational root and (because $f$ is monic) any rational root must be an integer. But $f(0) \equiv f(1) \equiv 1 \pmod 2$, so $f$ has no root modulo $2$ and hence no integer root and hence no linear factor. (Alternatively, we can show this with the Rational Root Theorem; see the bottom of this answer.)

Thus, if $f$ factors, it must factor as a product of a cubic and a quadratic, that is, (where we denote $\Lambda = \pm 15$) $$x^5 - x + \Lambda = (x^3 + A x^2 + B x + C) (x^2 + D x + E)$$ for some integers $A, B, C, D, E$. Distributing the right-hand side and comparing coefficients gives various (at most) quadratic conditions on those integers: \begin{align} A + D &= 0 \\ A D + B + E &= 0 \\ A E + B D + C &= 0 \\ B E + C D &= - 1 \\ C E &= \Lambda \\ \end{align} We can quickly reduce this system: The first equation gives $D = -A$, so the second equation gives $E = A^2 - B$, and then the third equation becomes $C = -A^3 + 2 A B$. Substituting leaves the system \begin{align*} A^4 - A^2 B - B^2 &= -1 \\ A (A^2 - 2 B) (A^2 - B) &= \Lambda . \end{align*} Since $A, A^2 - 2 B, A^2 - B$ are all integers and the prime factorization of $|\Lambda| = 15$ is $3 \cdot 5$, there are only a small number of combinations to check (in fact, since $15$ is a product of two primes, one of the three factors must be $\pm 1$), and we can quickly recover the factorization mentioned in the question.

Remark For readers unfamiliar with reducing polynomial equations modulo primes, we can conclude that $f$ has no linear factor with just a little more work, using the Rational Root Theorem, which in this case implies that the only possible rational roots are $\pm 1, \pm 3, \pm 5, \pm 15$; substituting shows that none of these are roots. One can even avoid most of this work: The derivative of the polynomial is $f'(x) = 5 x^4 - 1$, so $f$ is increasing where $|x| \geq 1$, but $f(-3) = -69, f(-1) = 13, f(1) = 15$, from which we can conclude none of the eight candidates are roots.

The statement on Wikipedia cites a 1998 paper dealing with the solutions of $x^k-x=n$ for nonnegative integer $n$ and $k=3,4,5$. In turn this paper cites another paper by Rabinowitz ("The Factorization of $x^5\pm x+n$", Math. Magazine 61.3 (1988), 191–193) showing that if $x^5-x-r$ has no linear factor yet is reducible over the integers, then one of the two equations below is true: $$r=\pm F_{2j-1}F_{2j}\sqrt{F_{2j+2}}\tag1$$ $$r=\pm F_{2j}F_{2j+1}\sqrt{F_{2j-2}}\tag2$$ The three specific $r$ that cause the quintic to split (into a quadratic and cubic factor) then correspond to the only nonzero square Fibonacci numbers of even index, $F_2=1$ and $F_{12}=144$:

• $(2)$ with $j=2$ gives $r=\pm15$
• $(1)$ with $j=5$ gives $r=\pm22440$
• $(2)$ with $j=7$ gives $r=\pm2759640$

Because there are only three special quintics, memorising the quadratic factors is feasible:

• $x^2\pm x+3$ divides $x^5-x\pm15$
• $x^2\mp12x+55$ divides $x^5-x\pm22440$
• $x^2\pm12x+377$ divides $x^5-x\pm2759640$

Then long division should suffice to find the cubic cofactor.

I see there is an answer to 15. I tried, it appears there is no integer root to $x^5 - x \pm 22440.$ As 7 gives 16800 but 8 gives 32760. We arrive at $$ (x^3 + A x^2 + B x + C)(x^2 + D x + E) = x^5 - x \pm 22440 $$ The point is not to solve the whole system at once, rather do one coefficient at a time and rewrite the system. The degree four term must be 0, so $A+D = 0$ $$ (x^3 + A x^2 + B x + C)(x^2 -A x + E) = x^5 - x \pm 22440 $$ Next the cubed term is zero, so $E-A^2 + B = 0, $ or $E = A^2 - B.$ $$ (x^3 + A x^2 + B x + C)(x^2 -A x + (A^2 - B)) = x^5 - x \pm 22440 $$ Next $x^2$ has 0, or $A^3 - AB -AB + C = 0,$ or $C = 2AB - A^3,$ $$ (x^3 + A x^2 + B x + (2AB -A^3))(x^2 -A x + (A^2 - B)) = x^5 - x \pm 22440 $$ Linear coefficient is $-1,$ so $A^2 B - B^2 - 2 A^2 B + A^4 = -1,$ or $A^4 - A^2 B - B^2 = -1.$

Getting there; taking $x = A^2, y = B,$ we have $x^2 - xy - y^2 = -1,$ meaning that $x,y$ are consecutive Fibonacci numbers... as $(3,2), (8,5), (21,13), (55,34), (144, 89).$ Since $x$ needs to be a square, we will try $A^2 = 144,$ $A = 12,$ $B = \pm 89$

One selection is $$ (x^3 + 12 x^2 + 89 x + 408)(x^2 - 12 x + 55) = x^5 - x + 22440$$ Just negating $x$ gives $$ (-x^3 + 12 x^2 - 89 x + 408)(x^2 + 12 x + 55) = -x^5 + x + 22440,$$ $$ (x^3- 12 x^2 + 89 x - 408)(x^2 + 12 x + 55) = x^5 - x - 22440,$$

So there you go. We were able to use the first Fibonacci number that is also a square. Bigger than $1$ I guess.