Does there exist two non-constant polynomials $f(x),g(x)\in\mathbb Z[x]$ such that for all integers $m,n$, gcd$(f(m),g(n))=1$?

Does there exist two non-constant polynomials $f(x),g(x)\in\mathbb Z[x]$ such that for all integers $m,n$, gcd$(f(m),g(n))=1$?

I think there are no such polynomials, but how to prove?

• Where did you get this question from? – Adam Hughes Jul 10 '14 at 5:46
• @Adam Hughes This problem comes from my mind. – Next Jul 10 '14 at 5:53
• Anyone else thinks that such polynomials can't possibly exist? – Git Gud Jul 10 '14 at 6:59
• @GitGud, there's no way. Of course, I don't see how to prove it. If someone can show the contrary, it will automatically become one of my favorite results. – Kaj Hansen Jul 10 '14 at 7:03
• mathforum.org/kb/message.jspa?messageID=6105994 (pretty original question) – user26857 Jul 10 '14 at 7:48

Assume that $f, g$ is a monic counterexample. In particular, $\gcd(f(x), g(x)) = 1$ in $\mathbb{Z}[x]$. If $f$ has repeated roots we can replace it with $\frac{f}{\gcd(f, f')}$ and similarly for $g$, so we may assume WLOG that $f$ and $g$ have no repeated roots and share no roots, so that the product $fg$ has no repeated roots.
Theorem (Frobenius): Let $q(x) \in \mathbb{Z}[x]$ be a monic polynomial with no repeated roots. Then the proportion of primes $p$ for which the factorization of $q(x) \bmod p$ has multiset of degrees $(d_1, d_2, ..., d_n)$ is precisely the proportion of elements of the Galois group $G$ of the splitting field $K$ of $q(x)$ which have cycle type $(d_1, d_2, ..., d_n)$ acting on the roots of $q(x)$.
Corollary: The proportion of primes $p$ for which $q(x) \bmod p$ is a product of linear factors is $\frac{1}{|G|}$; in particular, infinitely many such primes exist; in particular, at least one such prime exists.
Now apply the corollary to $q = fg$. We conclude that there is a prime $p$ such that $f(x)$ and $g(x)$ both split into linear factors $\bmod p$; in particular, the set of integers $n$ for which $f(n) \equiv 0 \bmod p$ and the set of integers $m$ for which $g(m) \equiv 0 \bmod p$ contain arithmetic progressions, so by picking suitably large $n$ and $m$ the conclusion follows.