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.



Two polynomials which are "completely" coprime
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$.


