Two polynomials which are "completely" coprime

Question

I would like to ask the following question:

Is it possible to find two non-constant polynomials $p(x), q(x)$ with integer coefficients, such that $\gcd(p(n), q(m))=1$ for every $(n, m)\in \mathbb{N}^2$?

If such $p(x), q(x)$ exist, we will call them "completely" coprime, since all of their values will be coprime.
Obviously $p(x), q(x)$ must not have the same root, but this does not seem to help. The problem seems to be quite simple and I suspect that the answer is no, but I was unable to prove this.

Answer 1

Gro-Tsen's solution is elegant. Here's a more elementary solution that doesn't directly use any algebraic number theory. I'll change the polynomials to $f(x)$ and $g(x)$. We'll assume that $$\gcd(f(n),g(m))=1 \quad\hbox{for all $m,n\in\mathbb N$ } \qquad(*) $$ and derive a contradiction. We may assume, WLOG, that $f(x)$ and $g(x)$ have no common factors in $\mathbb Q[x]$. We first note that if there is a prime $p$ that divides the resultant $\operatorname{Res}_x(f(x),g(x))$, then $f(x)$ and $g(x)$ have a common root mod $p$, and lifting that root to an integer $n\in\mathbb N$, we find that $p\mid\gcd(f(n),g(n))$, which contradicts $(*)$. More generally, for every integer $m\in\mathbb N$, if there is a prime $p$ dividing $\operatorname{Res}_x\bigl(f(x),g(x+m)\bigr)$, then we can repeat the argument to find an $n\in\mathbb N$ such that $p\mid\gcd(f(n),g(n+m))$, again contradicting $(*)$. To summarize, we've proven that $$ (*)\quad\Longrightarrow\quad\operatorname{Res}_x\bigl(f(x),g(x+m)\bigr)=\pm1\quad\hbox{for every $m\in\mathbb N$.}$$

This means that the polynomial $$\operatorname{Res}_x\bigl(f(x),g(x+y)\bigr)^2\in\mathbb Q[y]$$ is identically equal to $1$ for every $y\in\mathbb N$, which means that it's identically equal to $1$ as a polynomial. Taking square roots, for one of the choices $\epsilon\in\{\pm1\}$, we have proven that $$ \operatorname{Res}_x\bigl(f(x),g(x+y)\bigr) = \epsilon. $$ Using standard formal properties of the resultant over any ring (in our case, the ring $\mathbb Q[y]$), there are polynomials $A(x,y),B(x,y)\in\mathbb Q[x,y]$ satisfying $$ A(x,y)f(x) + B(x,y)g(x+y) = \epsilon \quad\text{in the polynomial ring $\mathbb Q[x,y]$.} $$ We are assuming that $f(x)$ is not a constant polynomial, so it has a root $x_0$ living in some finite extension $K$ of $\mathbb Q$. (This admittedly uses a little bit of field theory.) Substituting $x=x_0$, we find that $$ B(x_0,y)g(x_0+y) = 1 \quad\text{in the polynomial ring $K[y]$.} $$ It follows that $\deg_yg(x_0+y)=1$ in $K[y]$, and thus that $\deg_xg(x)=1$ in $\mathbb Q[x]$. Reversing the roles of $f$ and $g$ gives $\deg_xf(x)=1$. We have thus reduced to the case that $f$ and $g$ are non-constant linear polynomials, in which case $f$ and $g$ have roots modulo $p$ for all but finitely many primes $p$.

Answer 2

Let me rename to $f$ and $g$ the two polynomials (which you called $p$ and $q$ in the question) as this will make notations less confusing.

Clearly we can assume that $f$ and $g$ are irreducible and distinct. Let $K$ be the decomposition field of $fg$ over $\mathbb{Q}$. Possibly excluding finitely many primes that divide the leading coefficient of $f$ or $g$ or at which $f$ or $g$ ramifies, to say that a prime $p$ splits completely in $K$ means that $fg$ has $\deg f + \deg g$ roots in $\mathbb{Z}/p\mathbb{Z}$, and certainly implies that $f$ and $g$ have roots there. Now by Čebotarëv's density theorem (or something weaker), there is a positive density of such primes, so we can find $p$ such that both $f$ and $g$ have roots, say $\bar m,\bar n$ in $\mathbb{Z}/p\mathbb{Z}$. Lifting them arbitrarily to integers, we see that $p$ divides both $f(m)$ and $g(n)$, which are therefore not relatively prime.