Problem 1987

Answer: All polynomials of the form $P(x) = \pm x^l$ where $l$ is a non-negative integer.

Firstly, we show that all prime divisors of $P(n)$ are divisors of $n$. Suppose that there is a prime number $q$ dividing $P(n)$ but not dividing $n$. Obviously $P(n+q) \equiv P(n) \equiv 0 \pmod{q}$; but then $\text{gcd}(n, n+q) = 1$ while $\text{gcd}(|P(n)|, |P(n+q)|) \ge q > 1$, contradicting the assumption.

Next we show that only polynomials of the form $P(x) = \pm x^l$ where $l \ge 0$ satisfy the conditions of the problem. We proceed by induction on the degree of $P(x)$. If $P(x)$ is a constant polynomial then the constant must be coprime with itself in order to satisfy the conditions of the problem. This is possible only if $P(x) = \pm 1 = \pm x^0$. Assume now that $P(x)$ is a non-constant polynomial of degree $l$. Then $|P(q)| > 1$ for infinitely many prime numbers $q$. In each such case, namely $q$ must divide $P(q)$. Hence the constant term of $P(x)$ must be divisible by $q$. As the constant term does not depend on $q$, it must be divisible by infinitely many prime numbers. Hence the constant term equals 0, i.e., $P(x) = xP_1(x)$ where $P_1(x)$ is a polynomial with integral coefficients. The polynomial $P_1(x)$ satisfies the conditions of the problem, because $\text{gcd}(|P_1(u)|, |P_1(v)|) > 1$ for coprime $u$ and $v$ would imply $\text{gcd}(|P(u)|, |P(v)|) = \text{gcd}(|uP_1(u)|, |vP_1(v)|) > 1$, contradicting the choice of $P(x)$. By the induction hypothesis, $P_1(x) = \pm x^{l-1}$. Thus $P(x) = \pm x^l$.

On the other hand, all such polynomials satisfy the condition of the problem as $\text{gcd}(u, v) = 1$ implies $\text{gcd}(u^l, v^l) = 1$.

As in Solution 1, we show that all prime divisors of $P(n)$ are divisors of $n$. Letting $q$ be any prime number, we conclude that $P(q) = \pm q^k$ for some natural number $k$. Let the degree of $P(x)$ be $l$. Then $x^{l+1} > |P(x)|$ for every $x > N$ where $N$ is a large enough integer. Thus for infinitely many prime numbers $q$, there exists a natural number $k$ not exceeding $l$ such that $P(q) = \pm q^k$. As there are finitely many such natural numbers, one can fix $k$ such that either $P(q) = q^k$ for infinitely many primes $q$ or $P(q) = -q^k$ for infinitely many primes $q$. This implies that either $P(x) = x^k$ or $P(x) = -x^k$ (as a matter of fact, $k = l$). All such polynomials satisfy the conditions of the problem as $\text{gcd}(u, v) = 1$ implies $\text{gcd}(u^l, v^l) = 1$.