Problem 2326

The answer is all functions of the form $f(x) = kx$ for some $k \in \mathbb{N}$. These clearly work: now let us prove they are the only possibilities.

Since $x + a$ has an integer root (namely, $-a$) for any $a \in \mathbb{N}$, so does $f(1)x + f(a)$, implying $f(1)|f(a)$ for all $a \in \mathbb{N}$. Now the function $g : \mathbb{N} \rightarrow \mathbb{N}$ defined by $g(x) = f(x)/f(1)$ satisfies the same conditions as $f$, so WLOG, we may assume $f(1) = 1$.

Now the polynomial for any $n \in \mathbb{N}$, $nx^2 + (n+1)x + 1$ has a root $-1$, so $f(n)x^2 + f(n+1)x + f(1) = f(n)x^2 + f(n+1)x + 1$ has an integer root, which must be negative. Call this number $-k$. Therefore
$$f(n+1)k = f(n)k^2 + 1 > f(n) \cdot k \implies f(n+1) > f(n),$$
so that $f(n+1) \ge f(n) + 1$.

Now we prove by induction that $f(n) = n$ for every $n \in \mathbb{N}$. The base case is clear, now consider some $m = n+1 > 1$ and assume $f(n) = n$. The polynomial $x^2 + (n+1)x + n$ has the root $-1$, so $f(1)x^2 + f(n+1)x + f(n) = x^2 + f(n+1)x + n$ has an integer. Since the sum of its roots is $-f(n+1)$, an integer, both roots are in fact integers. Further, the roots must be negative and their product is $n$, so they are $-d$ and $-n/d$ for some positive divisor $d$ of $n$. Therefore $f(n+1) = d + \frac{n}{d}$. However, the inequality
$$d + \frac{n}{d} \le n + 1 \iff (n - d) \left(1 - \frac{1}{d}\right) \ge 0$$
holds, so we must have
$$n + 1 \ge d + \frac{n}{d} = f(n + 1) \ge f(n) + 1 = n + 1,$$
forcing $f(n+1) = n+1$ as desired. $\square$