, 2011

Suppose that $p_n(x)$ is a polynomial such that $p_n(1), p_n(2), \dots, p_n(n)$ are distinct powers of $2$. We claim that $\gcd(p_n(n+1), n!)$ is a power of $2$. Indeed, if there is a prime number $2 < q \le n$ that divides $p_n(n+1)$, then $q$ divides $p_n(n+1-q)$ (a power of $2$), which is a contradiction.

Let $2^m$ be the greatest power of $2$ that divides $n!$. So if $a = p_n(n+1)$, then $\gcd(a, \frac{n!}{2^m}) = 1$. By Euler's theorem, there exists a natural number $k$ such that $a^k - 1$ is divisible by $\frac{n!}{2^m}$, so $a^k - 1 = \frac{t \cdot n!}{2^m}$ for some integer $t$. Now define
$$p_{n+1}(x) = 2^m p_n(x)^k - t(x-1)(x-2)\dots(x-n).$$
For $1 \le i \le n$, we have $p_{n+1}(i) = 2^m p_n(i)^k$, which is a power of $2$, and
$$p_{n+1}(n+1) = 2^m a^k - t \cdot n! = 2^m \left( a^k - \frac{t \cdot n!}{2^m} \right) = 2^m.$$
Since the $p_n(i)$, $1 \le i \le n$ are distinct powers of $2$ and $k$ is positive, it follows that the $p_{n+1}(i)$, $1 \le i \le n+1$ are all distinct powers of $2$.