So far the answers just (cleverly) elaborate on high school tricks and techniques. Therefore, I think it can be interesting to see, instead, how standard modern algorithms work in this special case. I will implement a small version of the Berlekamp-Zassenhaus algorithm. I will try to factor $F(x)=x^5+x+1$ over $\mathbb Z[x]$ as a product $f_1(x)f_2(x)$ of polynomials of degree 2 and 3; it will not be long (of course), nor difficult. I recall what is the plan:
- Bound the coefficients of the factors $f_1,f_2$;
- Factor $F(x)=g_1(x)g_2(x)$ over modulo $p$ for some prime $p$;
- Lift (in essence, by Hensel's lemma) the factorization modulo higher $p^k$.
Bound the coefficients of $f_1(x)$: The leading coefficient of $F$ is $c=1$, the degree of $f_1$ is $\delta=2$, and the roots $\alpha$ of $F$ satisfy ${|\alpha|}^5\leq 1+|\alpha|$, so for sure, say, $|\alpha|<\rho=1.5$. Therefore the (absolute values of the) coefficients of $f_1(x)$ are all dominated by those of $(x+\rho)^2$. In particular they are all $<3$. This is called the binomial bound. The same estimate can be obtained with the Knuth-Cohen bound. See Abbott, John. "Bounds on Factors in Z [x]." Journal of Symbolic Computation 50 (2013): 532-563.
Find $g_i(x)\equiv f_i(x)$ modulo 2: Since $F(0)=1$ and $F(1)=3$ we have that $g_1(0)=g_1(1)=1\bmod 2$. Thus the only possibility is $g_1(x)=x^2+x+1$. By polynomial long division in $\mathbb F_2[x]$ we get $g_2(x)=\frac{F(x)}{g_1(x)}=x^3+x^2+1$. Well, if you are clever enough, and not a computer, you might finish the exercise here, by doing long division in $\mathbb Z[x]$.
Factor modulo 4 as $F=(g_1+2 h_1)(g_2 + 2 h_2)$: In other words, we need $g_1 h_2+g_2 h_1 = \frac {F(x)-g_1(x)g_2(x)}{2} = x^4+x^3+x^2 \bmod 2$. Of course the solution is $h_1=0$ and $h_2=x^2$.
Conclusion: We have $f_1(x)\equiv x^2+x+1\bmod 4$. Since the absolute value of the coefficients of $f_1(x)$ is at most $2$, we get $f_1(x)= x^2+x+1$. It works.
Supplement: actually I am deeply convinced that the most natural technique to factor $F(x)$ is the one provided by the OP (although all the other approaches, included the one I described above, are interesting). I'll try to justify this claim. Suppose you want to factor $7763073514021$ in prime numbers. The factor $7$ is easy to find (actually, this completes the factorization). Why? Because you decompose $7-7-63-0-7-35-14-0-21$ and you factor out termwise. "Piecewise" factorization is by far the most natural, and easy to spot, approach to factorization "by hand". Another example is $x^6-x^4-20x^3+14x^2+20 x -14$, where you may wish to take advantage of the pattern $(1,-1),(-20,20),(14,-14)$. Now, suppose you want to factor the number $636362236363$. It's very similar to the example before, only that you must be able to see the "negative": you are just subtracting a "14" from $636363636363$. Although the pattern of coefficients $[1,0,0,0,1,1]$ of $F(x)$ might be irregular at first glance, I find it very natural to see it as a $0-111-00$ subtracted from a $111-111$.