After seeing the solution you gave, I thought that it is the hardest problem of number theory ever given! In fact, we can give a very short solution, using lemma 1 (Schur theorem, I think in the literature). Indeed, consider $p_1,...,p_k$ different large prime numbers such that there exist $n_1,...,n_k$ for which $p_i| f(n_i)$ and $f(n_i)$ is non-zero (this follows from lemma 1). Choose a number $n$ congruent to $n_i$ mod $p_i$. There are an infinite number of such numbers and thus in at least one of these numbers the polynomial does not vanish. Even more, the value of the polynomial in each such number is a multiple of $p_1,...p_k$. Finish!

My solution: I will reduce the problem to the following lemma: Lemma 1. The set of all primes p such that there is an integer x satisfying p | f(x) is infinite. This Lemma will be proved later. Now I will solve the problem with the help of this lemma. Since the set of all primes p such that there is an integer x satisfying p | f(x) is infinite, we can take u primes $p_1$, $p_2$, ..., $p_u$ out of this set, and there are some integers $x_1$, $x_2$, ..., $x_u$ such that $p_i \mid f\left(x_i\right)$ for every i with $1\leq i\leq u$. Now, if $y_i$ is an integer such that $y_i \equiv x_i \; \mathrm{mod} \; p_i$, then $p_i \mid y_i-x_i$, while $y_i-x_i \mid f\left(y_i\right)-f\left(x_i\right)$ (this is just because f(x) is a polynomial with integer coefficients), so that $p_i \mid f\left(y_i\right)-f\left(x_i\right)$, and since $p_i \mid f\left(x_i\right)$, this yields $p_i \mid f\left(y_i\right)$. Now, since the numbers $p_1$, $p_2$, ..., $p_u$ are prime and thus pairwisely coprime, the Chinese Remainder Theorem shows that there are infinitely many integers Y such that $Y \equiv x_i \; \mathrm{mod} \; p_i$ for every i with $1\leq i\leq u$. Among these infinitely many integers Y, there is at least one such that $f\left(Y\right) \neq 0$ (else, the polynomial f(x) would have infinitely many zeros, what is not possible for a non-constant polynomial). Denote this number Y satisfying $f\left(Y\right) \neq 0$ by n. Hence, for these number n, we have $f\left(n\right) \neq 0$ and $n \equiv x_i \; \mathrm{mod} \; p_i$ for every i such that $1\leq i\leq u$. But the latter congruence yields $p_i \mid f\left(n\right)$ for every i with $1\leq i\leq u$. In other words, the number f(n) is divisible by all the u primes $p_1$, $p_2$, ..., $p_u$, and hence, this number f(n) has at least u prime factors. This solves the problem. Now let's prove Lemma 1. Assume the contrary, i. e. assume that the set of all primes p such that there is an integer x satisfying p | f(x) is finite. Let this set be $\left\{p_1;\;p_2;\;...;\;p_s\right\}$, where s is a positive integer. Then, for every integer x, the value f(x) has the form $f\left(x\right)= \pm p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$, where $e_1$, $e_2$, ..., $e_s$ are nonnegative integers. Hence, of course, $\left|f\left(x\right)\right| = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$. On the other hand, let our polynomial f(x) be $f\left(x\right) = a_m x^m + a_{m-1} x^{m-1} + ... + a_1 x + a_0$, with integer coefficients $a_m$, $a_{m-1}$, ..., $a_1$, $a_0$. Hereby, of course, m is the degree of our polynomial. Since a polynomial of degree m cannot achieve one and the same value more than m times (without being a constant polynomial), our polynomial f(x) achieves every of its values at most m times. Clearly, this yields that the function $\left|f\left(x\right)\right|$ achieves every of its values at most 2m times (in fact, for each value v, we have f(x) = v for at most m different values of x and we have f(x) = -v for at most m different values of x, so that we can have $\left|f\left(x\right)\right| = v$ for at most 2m different values of x). Let B be an arbitrary positive integer. Then, for every positive integer x with $x\leq 2mB$, the triangle inequality shows that $\left|f\left(x\right)\right| = \left|a_m x^m + a_{m-1} x^{m-1} + ... + a_1 x + a_0\right|$ $\leq \left|a_m x^m \right| + \left|a_{m-1} x^{m-1}\right| + ... + \left|a_1 x \right| + \left|a_0\right|$ $= \left|a_m \right| x^m + \left|a_{m-1}\right| x^{m-1} + ... + \left|a_1\right| x + \left|a_0\right|$ (since x is positive) $\leq \left|a_m \right| \cdot \left(2mB\right)^m + \left|a_{m-1}\right| \cdot \left(2mB\right)^{m-1} + ... + \left|a_1\right| \cdot 2mB + \left|a_0\right|$ (since $x\leq 2mB$). In other words, we have $\left|f\left(x\right)\right| \leq t\left(B\right)$, where $t\left(B\right) = \left|a_m \right| \cdot \left(2mB\right)^m + \left|a_{m-1}\right| \cdot \left(2mB\right)^{m-1} + ... + \left|a_1\right| \cdot 2mB + \left|a_0\right|$. Of course, t(B) is a polynomial of B, and actually a polynomial which is always nonnegative for B > 0. This will become important later. Now, consider the interval [1; 2mB]. To each of the 2mB integers in this interval, there corresponds a value of the function $\left|f\left(x\right)\right|$ at this integer. Since the function $\left|f\left(x\right)\right|$ achieves every of its values at most 2m times, at least $\frac{2mB}{2m}=B$ of these values are different. But every such value is $\leq t\left(B\right)$ on the one hand, and on the other hand, every such value can be written in the form $\left|f\left(x\right)\right| = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$. Hence, there are at least B different numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$. Let r be such a number $r=p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$, with $r\leq t\left(B\right)$. Then, if we would have $e_1 > \log_2 t\left(B\right)$, we would get $r=p_1^{e_1} p_2^{e_2} ... p_s^{e_s} \geq p_1^{e_1} > p_1^{\log_2 t\left(B\right)}$ $\geq 2^{\log_2 t\left(B\right)}$ (since $p_1\geq 2$, as any prime is $\geq 2$) $=t\left(B\right)$, what contradicts $r\leq t\left(B\right)$. Thus, $e_1 \leq \log_2 t\left(B\right)$. Similarly, $e_2 \leq \log_2 t\left(B\right)$, ..., $e_s \leq \log_2 t\left(B\right)$. Therefore, all the integers $e_1$, $e_2$, ..., $e_s$ lie in the interval $\left[0;\;\log_2 t\left(B\right)\right]$. Consequently, the number of all possible numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$ doesn't exceed $\left(\log_2 t\left(B\right) +1\right)^s$. But remember that we have found at least B different numbers of the form $p_1^{e_1} p_2^{e_2} ... p_s^{e_s}$ which are all $\leq t\left(B\right)$. Hence, $B \leq \left(\log_2 t\left(B\right) +1\right)^s$. And this holds for every positive integer B ! But it is not hard to show that, for every polynomial t(B) and for every integer s, there is a positive integer $B_1$ such that $B_1 > \left(\log_2 t\left(B_1\right) +1\right)^s$. In fact, this is equivalent to $\sqrt[s]{B_1} > \log_2 t\left(B_1\right) +1$, what, using the substitution $C_1=\sqrt[s]{B_1}$, takes the form $C_1 > \log_2 t\left(C_1^s\right) +1$; since $\log_2 t\left(C_1^s\right) + 1 = \log_2 \left(2t\left(C_1^s\right)\right)$, this is equivalent to $C_1 > \log_2 \left(2t\left(C_1^s\right)\right)$. And this is clear, since $2t\left(C_1^s\right)$ is a polynomial of $C_1$ (since t is a polynomial), and a linear function always overtakes the logarithm of a polynomial. Hence, we have found a positive integer $B_1$ such that $B_1 > \left(\log_2 t\left(B_1\right) +1\right)^s$, contradicting our previous result $B \leq \left(\log_2 t\left(B\right) +1\right)^s$ for every positive integer B; hence, we have a contradiction, and Lemma 1 is proven. My apologies for the style. It's just the first time I solve and write down the solution of a slightly nontrivial number theory problem.

Indeed, I did not realize that the longest proof was for the lemma 1 and this is because this lemma has a super short solution. I will give some hints: assuming that $f(0)$ is non-wero, show that we can reduce to the case $f(1)=1$ and then consider the sequence $f(1+n!)$. But I particularly like your proof of this lemma. Although long, it has nice ideas.

Oh yes, Darij's long solution misleads about difficulty of this problem. Well known lemma 1 has short nice proof.

You probably know that well-known and known to me are different things. And I must say I couldn't see anything from Harazi's hint. Anyway, the proposed solutions have a very nice and simple proof, so I guess it should be something of the same kind... Darij

Here's what Harazi's hint is supposed to mean: if you have $f(1)=1$, then assume that the elements of the set $\{f(n)|n\in\mathbb Z\}$ have only finitely many prime divisors, $p_1,p_2,\ldots,p_k$. Now take $n>\max (p_i)$, and show that $p_i\not |f(1+n!)$, thus getting a contradiction. It's in fact pretty similar to the idea used to show the infinitude of primes.

Thanks, Grobber, for this. Now it remains only one question (to you, Harazi and everyone): Why can I assume f(1) = 1 ? And, please, give a detailed explanation, not just a hint. Thanks! Darij

I remember Harazi's other hint was to use a polynomial transformation. I don't really know what he was talking about, so we'll just have to wait and see. Meanwhile.. Here's how I see this thing: take a number $t$ for which $f(t)\ne 0$. Let $p_1,p_2,\ldots,p_k$ be the primes dividing the elements of $f(\mathbb Z)$ (just as before). Now take $n$ so large that the exponent of $p_i$ in $n!$ is larger than the exponent of $p_i$ in $f(t)$. Now the exponent of $p_i$ in $f(n!+t)=n!\cdot N+f(t)$ is bounded by the exponent of $p_i$ in $t$, and since we can take arbitrarily large such $n$'s, we get a contradiction (the polynomial can only take a finite number of values in infinitely many points of the form $n!+t$, where $t$ is the $t$ fixed above and $n$ increases indefinitely). This is somewhat of a change of plan, but I think it gives a better idea of what's going on: even if $f(1)\ne 1$, it can't be that important (as long as $f(1)\ne 0$). I expect Harazi to have a different answer, since he didn't mention $f(1)\ne 0$, so maybe he has a nice way around that.

Grobber, thanks for the explanation! grobber wrote: This is somewhat of a change of plan, but I think it gives a better idea of what's going on: even if $f(1)\ne 1$, it can't be that important (as long as $f(1)\ne 0$). Well, guarranteeing $f\left(1\right)\neq 0$ is not hard: The polynomial f can have only finitely many roots, hence it can have only finitely many integer roots, and consequently, there is a greatest integer root v of this polynomial; now, after replacing f(x) by f(x + v), it is clear that f(0) = 0 and $f\left(1\right) \neq 0$. Darij

I've posted a solution of this problem some time ago, why it isn't here??

Zorro wrote: I've posted a solution of this problem some time ago, why it isn't here?? Probably due to the problems with database which occured last week