2
$\begingroup$

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$.

  • 0
    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?2012-09-21
  • 1
    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.2012-09-21
  • 0
    To be precise, it was Problem A5 on the 1972 exam. The exam is at http://mks.mff.cuni.cz/kalva/putnam/putn72.html, with a link to the solution.2012-09-23

0 Answers 0