Solución. La división de polinomios nos dice que podemos expresar
\[P(x)=(x^3+ax+b)Q_1(x)+R(x)=(x^3+ax^2+b)Q_2(x)+R(x),\]
donde $Q_1(x)$ y $Q_2(x)$ son los cocientes y $R(x)$ es el resto común a ambas divisiones. Evaluando la igualdad anterior en $x=0$, obtenemos que
\[P(0)=b Q_1(0)=b Q_2(0),\]
luego $Q_1(0)=Q_2(0)$ puesto que $b\neq 0$. Evaluando ahora en $x=1$, tenemos que
\[P(1)=(1+a+b)Q_1(1)=(1+a+b)Q_2(1)\]
Si $a+b+1\neq 0$, entonces esto nos da $Q_1(1)=Q_2(1)$. Por tanto, tendríamos que $Q_1$ y $Q_2$ son dos polinomios de grado $2$ con el mismo coeficiente de $x^2$, el mismo término independiente y la misma suma de coeficientes. Deducimos que $Q_1=Q_2$, lo que nos lleva en la división original a que $x^3+ax+b=x^3+ax^2+b$, pero esto no es posible porque $a\neq 0$ según el enunciado. Esta contradicción nos asegura que $a+b+1=0$, es decir, $a+b=-1$.
Nota. Una pregunta natural es si realmente existen polinomios en las condiciones anteriores (para ser rigurosos, podrían no existir tales polinomios y entonces no tener ningún valor $a+b$). Planteando la ecuación coeficiente a coeficiente y suponiendo que $Q_1(x)$ y $Q_2(x)$ tienen coeficiente $1$ en $x^2$, dejamos como ejercicio ver que tiene que ser
\[Q_1(x)=x^2+x-b,\qquad Q_2(x)=x^2-bx-b.\]
El resto $R(x)=cx+d$ es un polinomio arbitrario de grado $1$, luego tendríamos las soluciones
\[P(x)=x^5-b x^4-(2b+1)x^3+(b+2)bx^2+(b+c)x+(d-b^2)\]
para cualesquiera $b,c,d\in\mathbb{R}$ con $b\not\in\{-1,0\}$.