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

  • $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Sep 21 '12 at 12:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Sep 21 '12 at 12:49
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Sep 23 '12 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.