# Restriction on polynomial with integer coefficients

Let $P$ be a polynomial with integer coefficients such that for every positive integer $n$, $P(n)$ divides $2^n - 1$.

Show that $P(x) =1$ or $P(x) = -1$ for all $x$.

-
If $b=P(n)>1$ for some $n$, then $b\mid P(n+kb)$ for all naturals $k$. Therefore $b$ divides the gcd of the numbers $2^{n+kb}-1$. This gcd is $2^{\gcd(n,b)}-1$ by a well known argument (been repeated in this forum many times). Is it possible for an odd integer $b>1$ to be a factor of $2^{b'}-1$, where $b'\mid b$? Can't happen if $b$ is prime, but what about the general case? –  Jyrki Lahtonen Sep 21 '12 at 12:03
If $d\mid b$, and $b\mid2^d-1$, then $d\mid2^d-1$, but it's a nice exercise (and it was once a Putnam problem) to show that that can't happen. –  Gerry Myerson Sep 21 '12 at 12:49
To be precise, it was Problem A5 on the 1972 exam. The exam is at mks.mff.cuni.cz/kalva/putnam/putn72.html, with a link to the solution. –  Gerry Myerson Sep 23 '12 at 12:54