Primitive polynomials $P$ with $\gcd(P(x),P(y))=1$ for infinitely many $x,y$ 
Characterize all primitive polynomials $P$ having integer coefficients such that there exist infinitely many natural numbers $x,y$ with $\gcd(P(x),P(y))=1$
NOTE: A primitive polynomial is defined as a polynomial whose coefficients are coprime.

CONTEXT:
I encountered the following problem a while ago. 

Let $P$ be a polynomial with integer coefficients such that $P(0)=0$ and
$\gcd(P(0), P(1), P(2), \ldots ) = 1.$ 
Show there are infinitely many $n$ such that
$\gcd(P(n)- P(0), P(n+1)-P(1), P(n+2)-P(2), \ldots) = n.$

I thought that the following lemma might be useful.
LEMMA: If a polynomial $P$ is primitive, then there exist infinitely many naturals $x,y$ with $(P(x),P(y))=1$.
Of course, as I soon figured out, the above lemma is wrong. An easy counterexample can be given using Fermat's little theorem. Just take $P(x)=x^p-x$, with $p$ a prime. The polynomial is primitive but has common factor $p$ for all $x$.
I am pretty sure this is a famous result, but can't seem to find it. Any help regarding this will be appreciated.
Thanks.
 A: You essentially found all the counterexamples, in a certain
sense. The precise answer to your question is : a polynomial
satisfies your conditions iff it is not divisible by 
$x^p-x$ in ${\mathbb Z}[x]$ for any prime $p$ (it suffices
to check the $p\leq {\textsf{deg}}(P)$, of course). This follows
from
THEOREM. Let $P$ be a (not necessarily primitive)
polynomial in ${\mathbb Z}[x]$. Then the following
are equivalent for $P$ :
(1) There are only finitely many pairs
$(x,y)\in{\mathbb Z}^2$ with ${\textsf{gcd}}(P(x),P(y))=1$.
(2) There is no pair $(x,y)\in{\mathbb Z}^2$ 
with ${\textsf{gcd}}(P(x),P(y))=1$.
(3) There is a fixed prime $p$ such that $P(x)$
is divisible by $p$, for any $x\in{\mathbb Z}$.
(4) There is a fixed prime $p$ such that $P(x)$
is divisible by $x^p-x$ in ${\mathbb Z}[x]$.
(note : Thanks to congruences, it is immaterial in your problem 
if we allow $x,y$ to be natural integers or signed integers. The latter
will be more convenient for me).
Proof of theorem. I will show 
$(1)\Leftrightarrow (2),(3)\Leftrightarrow (4)$
and $(2)\Rightarrow(3),(4)\Rightarrow(1)$
-Proof of $(1)\Leftrightarrow (2)$ : the only
nontrivial direction is $(1) \Rightarrow (2)$, which 
we show by contraposition.So suppose that $(x,y)$ is a "good" pair
(i.e. such that ${\textsf{gcd}}(P(x),P(y))=1$). If one
of $P(x)$ or $P(y)$ (say $P(x)$) is $\pm 1$, then any pair 
$(x,y')$ is good. Otherwise, both $P(x)$ and $P(y)$ are nonzero,
and any pair $(x,y+tP(x))$ (with $t\in{\mathbb Z}$) is good.
-Proof of $(3)\Leftrightarrow (4)$ : Perform an euclidean division
of $P(x)$ by $x^p-x$, then use the classical linear algebra exercise
which states that the family $1,x,x^2,\ldots,x^{p-1}$ is independent over 
${\mathbb F}_p$ (use a Van der Monde determinant).
-Proof of $(2)\Rightarrow (3)$ : again we reason by contraposition :
suppose that (3) is false, i.e. for every prime $p$, there is a value $t_p\in{\mathbb Z}$
such that $p\not| P(t_p)$. Let $x$
be such that $P(x)\neq 0$, and let $q_1,q_2,\ldots,q_r$ be the
prime divisors of $x$. By the hypothesis just made,
there are integers $t_1,t_2,\ldots,t_r$ with
$q_i\not| P(t_i)$. By the Chinese remainder theorem, there is a $y$
which satisfies $y\equiv t_j \ ({\textsf{mod}}\ q_j)$ for every $j$.  Then
$P(x)$ and $P(y)$ must be coprime.
-Finally, $(4)\Rightarrow (1)$ is obvious : if (4) holds then
$p|{\textsf{gcd}}(P(x),P(y))$ for any $x,y$.
