Problem 2103

Answer: All polynomials of the form $f(x) = x^m$ for some $m \in \mathbb{Z}^+$ and $f(x) = c$ for some $c \in \mathbb{Z}^+$ with $\omega(c) \le 2023^{2023} + 1$.

First of all we prove the following (well-known) Lemma.

Lemma. Let $f(x)$ be a non-constant polynomial with integer coefficients. Then, the number of primes $p$ such that $p|f(n)$ for some $n$ is infinite.

Proof. If $f(0) = 0$, then the Lemma is obvious. Otherwise, define the polynomial
$$g(x) = \frac{f(xf(0))}{f(0)},$$
which has integer coefficients. Observe that $g(0) = 1$ and if $g$ satisfies the property of the Lemma, then so does $f$. So, we need to prove that there are infinitely many primes $p$ such that $p|g(n)$ for some $n$. Suppose, for the sake of contradiction that the number of such primes is finite, and let those be $p_1, \dots, p_k$. Then, set $n = Np_1 \cdots p_k$ for some large $N$, such that $|g(n)| > 1$. It is evident that $g(n)$ has a prime divisor, but it is none of the $p_i$'s. This is a contradiction and therefore the result follows. $\square$

Let $M = 2023^{2023} + 1$. Observe that constant polynomials $f(x) = c$ with $c \in \mathbb{N}$ such that $\omega(c) \le M$ satisfy the conditions of the problem. On the other hand, if $f(x) = c$ with $\omega(c) > M$, we can choose some $n$ such that $\omega(n) = M$ to see that the condition of the problem is not satisfied. Next, we look for non-constant polynomials that satisfy the conditions of the problem. Let $f(x) = x^m g(x)$, where $m \ge 0$ and $g(x)$ is a polynomial with $g(0) \ne 0$. We claim that $g$ is a constant polynomial. Indeed, if it is not, then (due to the Lemma) there exist pairwise distinct primes $q_1, \dots, q_{M+1}$ and non-zero integers $n_1, \dots, n_{M+1}$ such that $q_i > |g(0)|$ and $q_i|g(n_i)$ for $i = 1, 2, \dots, M + 1$. Set $n = p_1 p_2 \cdots p_M$, where $p_1, \dots, p_M$ are distinct primes such that
$$p_1 \equiv n_i \pmod{q_i}, \quad \forall i = 1, 2, \dots, M + 1$$
and
$$p_j \equiv 1 \pmod{q_i}, \quad \forall i = 1, 2, \dots, M + 1, \quad \forall j = 2, 3, \dots, M.$$
Observe that since $q_i > |g(0)|$, it is impossible to have $q_i|n_i$, so the existence of such primes is guaranteed by the Chinese Remainder Theorem and the Dirichlet's Theorem. Now, for every $i = 1, 2, \dots, M + 1$ we can see that $n = p_1 \cdots p_M \equiv n_i \pmod{q_i}$, which means that
$$g(n) \equiv g(n_i) \equiv 0 \pmod{q_i}, \quad \forall i = 1, 2, \dots, M + 1.$$
Thus, $\omega(f(n)) \ge \omega(g(n)) \ge M + 1 > M = \omega(n)$, which gives the desired contradiction. Therefore, $f(x) = cx^m$, for some $m \ge 1$ (since $f$ was non-constant). If $c < 0$, take some $n$ with $\omega(n) = M$ to see that $f(n)$ is negative and so, does not satisfy the conditions of the problem. If $c > 1$, choose some $n$ with $\omega(n) = M$ and $\gcd(n, c) = 1$ to observe that $f$ cannot satisfy the conditions of the problem. This means that $f(x) = x^m$ (which is for sure a solution to the problem) for some $m \ge 1$ and $f(x) = c$ for some $c \in \mathbb{Z}^+$ with $\omega(c) \le M$ are the only polynomials that satisfy the conditions of the problem.