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?

  • $\begingroup$ Where did you get this question from? $\endgroup$ – Adam Hughes Jul 10 '14 at 5:46
  • 1
    $\begingroup$ @Adam Hughes This problem comes from my mind. $\endgroup$ – Next Jul 10 '14 at 5:53
  • $\begingroup$ Anyone else thinks that such polynomials can't possibly exist? $\endgroup$ – Git Gud Jul 10 '14 at 6:59
  • $\begingroup$ @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. $\endgroup$ – Kaj Hansen Jul 10 '14 at 7:03
  • 2
    $\begingroup$ mathforum.org/kb/message.jspa?messageID=6105994 (pretty original question) $\endgroup$ – user26857 Jul 10 '14 at 7:48

There do not exist such polynomials which are in addition monic, and I would be surprised if this restriction turned out to be fundamental.

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.

The key tool is the following weaker version of the Chebotarev density theorem.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.