Estonian Math Competitions

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(\mathrm{mod}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)=x{P}_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}(|u{P}_1(u)|,|v{P}_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$.

---

Alternative solution.

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$.