1
$\begingroup$

Find all integer polynomials $f(x)$ such that $f(n)\mid 2^n-1$ for all $n\in\mathbb{N}^+$.

So far, I have tried to plug in values of $n$, and see where that takes me. For example, plugging in $n=1$ shows that $f(1)\mid 1$, which means that $f(1)=-1,1$. Similarly, if $n=2$, $f(2)\mid 3\implies f(2)=-3,-1,1,3$ etc. In general, if $2^n-1$ is prime, $f(n)$ can only be $2^n-1, 1, -1, -2^n+1$. However, this isn't taking me anywhere, and I'm not sure what to do next. I have also tried to write $2^n$ as $2^0+2^1+2^2\cdots+2^{n-1}$, but this also doesn't do much.

Thanks in advance!

$\endgroup$
3
  • $\begingroup$ If there are infinitely many Mersenne primes, then the only such polyn9mial are constants $f(n)=1$ or $f(n)=-1.$ $\endgroup$ Commented Jul 17, 2023 at 20:38
  • $\begingroup$ Since we don't know 8f there are or are not infinitely many Mersenne primes, we certainly can only solve this if the answers are the constant polynomials $\pm1,$ unless we magically solve a famous unsolved problem. So that gives an idea what to try. $\endgroup$ Commented Jul 17, 2023 at 20:47
  • $\begingroup$ Welcome to Math SE. Note the duplicate question was found using an Approach0 search. There are also several AoPS threads, e.g., Find all polynomials, Polynomials, Find all P(n) dividing 2^n-1, Polynomial problem 2, etc. $\endgroup$ Commented Jul 17, 2023 at 21:47

1 Answer 1

6
$\begingroup$

Let $p$ be a prime divisor of $f(n)$ for some $n$. Hence $p|2^n-1$. It's a theorem on integer polynomials that $a-b|f(a)-f(b)$. With $a=n+p$ and $ b=n$ we get $p|f(n+p)-f(n)$ so $p|f(n+p)$. Thus $p|2^{n+p}-1$. Therefore $2^{n+p}\equiv 1\pmod{p}$ and $2^n\equiv 1\pmod{p}$ which implies $2^p\equiv 1\pmod{p}$. This never holds by Fermats little theorem, so we cannot have any prime divisors of $f(n)$. Hence $f(n)$ is always either $1$ or $-1$. Suppose $f(n)$ is $1$ for infinitely many $n$, then $f$ must be identically one because $f(n)-1$ has infinite roots and it's a polynomial. Likewise if $f(n)=-1$ for infinitely many $n$ then $f$ is identically $-1$. Hence the solution set is $f(n)=1\forall n$ and $f(n)=-1\forall n$.

$\endgroup$