Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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, with a link to the solution. – Gerry Myerson Sep 23 '12 at 12:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.