Bay Area Mathematical Olympiad

Solution:
Answer: $P(x)= \pm x^{n}$ for each integer $n \geq 0$.

It is evident that these polynomials meet the condition, since the only possible prime factors of $P(a)$ are the prime factors of $a$, so if $a$, $b$ have no prime factors in common, $P(a)$, $P(b)$ can't either.

Consider any polynomial $P$ not of this form; we show that it does not meet the condition. Write
$$P(x)=c_{n} x^{n}+c_{n-1} x^{n-1}+\cdots+c_{0} .$$
Replacing $P(x)$ by $-P(x)$ if necessary, we may assume $c_{n}>0$.

Suppose that $c_{n}=1$ and the next nonzero coefficient $c_{k}$ is negative. Then we have $x^{n-1}<P(x)<x^{n}$ for all large enough $x$. In all other cases, we have $x^{n}<P(x)<x^{n+1}$ for all large enough $x$. In either situation, if we choose $q$ to be a large enough prime, then $P(q)$ is a positive integer lying between two consecutive powers of $q$. In particular, $P(q)$ cannot itself be a power of $q$, so it must have some other prime factor $r \neq q$.

Then the numbers $q$ and $q+r$ are relatively prime. But since
$$r=(q+r)-q \mid P(q+r)-P(q)$$
both $P(q)$ and $P(q+r)$ are divisible by $r$, so they are not relatively prime. Hence, the polynomial $P$ does not satisfy the required condition.