3

Let a polynomial $f$ be in $\mathbb{Z}[x]$. Assume that for every $n \in \mathbb{N}$ $f(x)=n$ has at least one integer solution. Than prove that $$f(x) = \pm x + c$$ I really don't know to start. Thanks in advance!

astrobarrel
  • 217
  • 4
    Try and prove that with $n$ outside of a range like $[M,-M]$ for some suitable (large) $M$ the values of $f$ are constrained to be in a set that excludes more than $2M+1$ integers. That is, unless A) $f$ is linear, and B) has leading coefficient $\pm1$. – Jyrki Lahtonen Aug 30 '19 at 19:35
  • Thanks for the input. Anyway, I was looking for a more conceptual-algebraic way to solve it, if possible. I remember that I saw this problem solved in an elegant way, a long time ago, but unfortunately I can't recall the proof! – astrobarrel Aug 30 '19 at 19:40
  • 2
    For $x$ large enough, $f$ is strictly increasing or decreasing. Furthermore, $f(x + 1) - f(x)$ is larger than $1$ unless $f$ fits the expression you have. – Ayman Hourieh Aug 30 '19 at 19:49
  • 2
    I had a recollection that the same question has been handled (hence no answer from me). Indeed, here is one. For better or for worse, the answer/comment there are along the lines of my suggestion. In order not to have this closed as a duplicate may be you need to specify better, what kind of a solution you are looking for? – Jyrki Lahtonen Aug 30 '19 at 19:49
  • A solution that is not "analytic" but instead uses something algebraic like divisors, roots... – astrobarrel Aug 30 '19 at 19:52
  • I take it that excludes the first derivative test? That's all you need to develop my comment to a full answer. – Ayman Hourieh Aug 30 '19 at 19:53
  • The derivative test is ok as long as you use it for its scope, that is, proving or disproving that you have a multiple root, i guess. I know that what i'm asking is really vague, but i wanted to see if someone knew that proof. It should not be really difficult as I saw it in my second year as an undergraduate. – astrobarrel Aug 30 '19 at 19:57
  • Possible duplicate of Surjective Linear Integer Polynomial. – Dietrich Burde Aug 30 '19 at 20:11

1 Answers1

6

Let $f(x)=a_0+a_1x+...+a_kx^k$ where we shall assume that $a_k\ne0$ and $k>1$.

Let $p$ be a prime greater than $1+|a_1|+|a_2|+...|a_k|$ and suppose that $t$ is an integer solution of $f(x)=a_0+p$.

Then $t(a_1+a_2t+ ...+a_kt^{k-1})=p$ and so $t$ is one of $-1,1,-p,p$.

If $t$ is $-1$ or $1$, then $|a_1|+|a_2|+...|a_k|\ge p$, a contradiction.

So suppose that $t$ is $-p$ or $p$. Then $$|a_k|p^{k-1}\le (1+|a_1|+|a_2|+...|a_{k-1}|)p^{k-2}$$ and so $$p\le (1+|a_1|+|a_2|+...|a_{k-1}|),$$ another contradiction.

Therefore $k$ must be $1$ and, for $t$ is an integer solution of $f(x)=a_0+p$, we have to solve $a_1t=p$. Then $a_1$ is a factor of all possible $p$ and so $a_1$ is $1$ or $-1$, as required.