all poly's such that $P(n)$ divides $2^n-1$

Question

Find all polynomials $P$ with integer coefficients such that $P(n)$ divides $2^n-1$ for all positive integers $n$.

Answer 1

Lemma: If $n | 2^n - 1$ for positive integer $n$, then $n = 1$. Proof: See here.

Main Proof:

Suppose $P(n) | 2^n - 1$ for all positive integers $n$. If $P(n)$ is constant, we know from the lemma that $P(n) = \pm 1$. Now suppose that $P$ is not constant. Thus,

$$P(x) = \sum_{k = 0}^j a_jx^j.$$

Now we claim that $a_0 \neq 0$. This follows directly from the lemma since $a_0 = 0$ implies $n|P(n) \implies n|2^n - 1$ for all integers $n$ which is a contradiction because only $n = \pm 1$ satisfy this condition from the lemma.

Now note that $$P(P(n) + n) = \sum_{k = 0}^j a_j(P(n) + n)^j \equiv \sum_{k = 0}^j a_jn^j \equiv 0 \pmod {P(n)}.$$

Thus, $P(n)$ divides $P(P(n) + n)$ and thus, divides $2^{P(n) + n} - 1.$ Therefore, $P(n)$ divides both of $2^n - 1$ and $2^{P(n) + n} - 1$ for all positive integers $n$.

Thus, $P(n)$ divides $2^{\gcd(n, P(n) + n)} - 1$. Now since $a_0$, the constant term of $P(n)$, is finite, it has finitely many prime factors. Pick $n$ to be one of infinitely many primes that don't divide $a_0$. Now if $n$ is a prime, $\gcd(n, P(n) + n) = n$ or $1$. It cannot be $n$ because $P(n) \equiv a_0 \pmod n$ and $n \nmid a_0$.

Thus, we can find infinitely many integers $n$ such that $\gcd(n, P(n) + n) = 1$. This means $$P(n)|2^{\gcd(n, P(n) +n)} - 1 \implies P(n) | 1$$ for infinitely many integers $n$.

Thus, $P(x)$ must be $\pm 1$ infinitely many times. By multiplying by a negative one if we need to, we must have $P(n) - 1$ has infinitely many roots which is a contradiction since the deg of $P$ is finite. Thus, only $P(x) = \pm 1$ work.