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

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.

• If there are infinitely many Mersenne primes, then the only such polyn9mial are constants $f(n)=1$ or $f(n)=-1.$ Commented Jul 17, 2023 at 20:38
• 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. Commented Jul 17, 2023 at 20:47
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$$.