Find all polynomials $P$ with integer coefficients such that $P(n)$ divides $2^n-1$ for all positive integers $n$.

  • 3
    $\begingroup$ Source of this problem, please? Partial results, if you know any? $\endgroup$ – Gerry Myerson Aug 15 '16 at 13:09
  • $\begingroup$ If there are infinitely many Mersenne primes, then all such polynomials $P$ must be constant. That is, $P\equiv -1$ or $P\equiv +1$. $\endgroup$ – Batominovski Aug 15 '16 at 13:15
  • $\begingroup$ Seems like either $P(n)\equiv +1\pmod{n}$ for all $n$ or $P(n)\equiv-1\pmod{n }$ for all $n$. $\endgroup$ – Batominovski Aug 15 '16 at 13:33
  • 1
    $\begingroup$ it's my own problem formulated while I was reading articles on Mersenne primes, I don't have any results (neither mine nor founded) $\endgroup$ – tong_nor Aug 15 '16 at 13:38
  • 1
    $\begingroup$ If one can show that the smallest prime divisors of Mersenne numbers are not polynomially bounded, then it is evident that $P$ is constant. However, I have not heard of any such bounds. $\endgroup$ – Batominovski Aug 15 '16 at 13:40

Lemma: If $n | 2^n - 1$ for positive integer $n$, then $n = 1$. Proof: See here.

Main Proof:

Suppose $P(n) | 2^n - 1$ for all positive integers $n$. If $P(n)$ is constant, we know from the lemma that $P(n) = \pm 1$. Now suppose that $P$ is not constant. Thus,

$$P(x) = \sum_{k = 0}^j a_jx^j.$$

Now we claim that $a_0 \neq 0$. This follows directly from the lemma since $a_0 = 0$ implies $n|P(n) \implies n|2^n - 1$ for all integers $n$ which is a contradiction because only $n = \pm 1$ satisfy this condition from the lemma.

Now note that $$P(P(n) + n) = \sum_{k = 0}^j a_j(P(n) + n)^j \equiv \sum_{k = 0}^j a_jn^j \equiv 0 \pmod {P(n)}.$$

Thus, $P(n)$ divides $P(P(n) + n)$ and thus, divides $2^{P(n) + n} - 1.$ Therefore, $P(n)$ divides both of $2^n - 1$ and $2^{P(n) + n} - 1$ for all positive integers $n$.

Thus, $P(n)$ divides $2^{\gcd(n, P(n) + n)} - 1$. Now since $a_0$, the constant term of $P(n)$, is finite, it has finitely many prime factors. Pick $n$ to be one of infinitely many primes that don't divide $a_0$. Now if $n$ is a prime, $\gcd(n, P(n) + n) = n$ or $1$. It cannot be $n$ because $P(n) \equiv a_0 \pmod n$ and $n \nmid a_0$.

Thus, we can find infinitely many integers $n$ such that $\gcd(n, P(n) + n) = 1$. This means $$P(n)|2^{\gcd(n, P(n) +n)} - 1 \implies P(n) | 1$$ for infinitely many integers $n$.

Thus, $P(x)$ must be $\pm 1$ infinitely many times. By multiplying by a negative one if we need to, we must have $P(n) - 1$ has infinitely many roots which is a contradiction since the deg of $P$ is finite. Thus, only $P(x) = \pm 1$ work.

  • $\begingroup$ You probably meant $n\nmid a_0$, rather than $p\nmid a_0$. Also, maybe it is worth mentioning how you use the lemma. I'm assuming that you used it to prove that $a_0\neq0$ (otherwise it wouldn't have finitely many prime divisors). Otherwise, I think the proof is perfect. $\endgroup$ – Batominovski Aug 15 '16 at 13:56
  • $\begingroup$ @Batominovski: Yup, Ill fix it. Thanks! (Also the post for the lemma is yours I believe.) $\endgroup$ – Sandeep Silwal Aug 15 '16 at 13:57
  • $\begingroup$ Yes, I proved the lemma. You got the same idea as I did (i.e., finding $m$ such that $P(n)$ divides $P(n+m)$) but I was unsuccessful at pursuing it. I thought about using the same lemma, but I didn't get as far as you. Bravo! $\endgroup$ – Batominovski Aug 15 '16 at 13:58
  • $\begingroup$ @Batominovski and Sandeep Do you know the source of this problem? It seems highly likely it was a contest problem. $\endgroup$ – Bill Dubuque Aug 15 '16 at 14:03
  • $\begingroup$ @Batominovski: Ok fixed all the errors I think. The main motivation for using $m = P(n)$ was that I wanted to use the gcd condition just like in the proof of the lemma and that choice made things a lot easier. $\endgroup$ – Sandeep Silwal Aug 15 '16 at 14:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.