# Two polynomials which are "completely" coprime

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.

• How about $p=q=1$? Mar 21 at 10:53
• @ChrisBirkbeck I made an edit. Mar 21 at 10:55
• Does this answer your question? Noncoprime polynomial values Mar 22 at 0:28

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