Solución. Vamos a probar que $P(n)=\pm 1$ para todo $n\in\mathbb{N}$, lo que nos dirá que los únicos polinomios que cumplen dicha propiedad son los constantes $P(x)=\pm 1$. Por reducción al absurdo, supongamos que existe un primo $p$ tal que $P(n)$ es múltiplo de $p$. Podemos suponer que $p\gt 2$ ya que $p$ divide a $2^n-1$, que es un número impar. No obstante, $p=(n+p)-n$ divide a $P(n+p)-P(n)$, luego también divide a $P(n+p)$ y, por tanto, $2^{n+p}\equiv 1\ (\mathrm{mod}\ p)$. Como $p$ es impar, el teorema pequeño de Fermat nos dice que $2^p\equiv 2\ (\mathrm{mod}\ p)$, luego $2^{n+1}\equiv 1\ (\mathrm{mod}\ p)$, es decir, $p$ divide a $2^{n+1}-1$.
En resumen, $p$ divide tanto a $2^n-1$ como a $2^{n+1}-1$, luego también divide a $1=(2^{n+1}-1)-2(2^n-1)$, lo cual contradice que $p$ es un número primo y hemos encontrado la contradicción buscada.