Let $p_1, \ldots, p_n$ be a finite sequence of nonconstant polynomials with integer coefficients. Does there exist a finite sequence of integers $x_1, \ldots, x_n$ such that the integers $p_1(x_1), \ldots, p_n(x_n)$ have a nontrivial common divisor?


Here's an argument that might be a bit too high-brow (it uses Chebotarev's density theorem).

Reduction 1. Your question is equivalent to: for $f_1, \ldots, f_n \in \mathbb Z[x]$, does there exist a prime $p$ such that all $f_i$ have a root in $\mathbb F_p$. Indeed, taking lifts $x_i \in \mathbb Z$ of roots $\bar x_i \in \mathbb F_p$ of $\bar f_i \in \mathbb F_p[x]$ gives $$f_i(x_i) \equiv 0 \pmod p$$ for all $i$, so the $f_i(x_i)$ have $p$ as common divisor.

Reduction 2. We may assume that all $f_i$ are irreducible. Indeed, a root (mod $p$) of a factor of $f_i$ gives a root of $f_i$ itself.

Proof of the assertion. Let $K_i = \mathbb Q[x]/(f_i)$ be the field extension defined by adjoining a root of $f_i$. Let $K$ be the Galois closure of the compositum of the $K_i$ (inside $\bar {\mathbb Q}$). By the Chebotarev density theorem, there exists a prime $p$ such that $(p)$ is completely split in $K$. Thus, all the $f_i$ have a root modulo $p$. $\square$

Remark. This actually proves more: there are infinitely many primes $p$ with this property (and their density is $1/[K:\mathbb Q]$). Moreover, there are many lifts $x_i$ of a root of $\bar{f}_i$, so we actually get many examples of such $x_i$. One can ask how many there are (I will not attempt this right now).


Here is a bit more pedestrian argument. We may assume that $p_i$ are irreducible. Take $\alpha_i$ a root of $p_i$; then $\mathbb Q[\alpha_1,\dots,\alpha_n]=\mathbb Q[\xi]$ by the primitive element theorem. Taking $q$ to be the monic minimal polynomial of $\xi$, we have $\alpha_i=r_i(\xi)$, so $q(x)\mid p_i(r_i(x))$. Now we may take any prime divisor $p$ of the values of $q$ which does not appear in the denominators of the coefficients of $q$ and $r_i$; $p$ divides appropriate values of $p_i$ as well.

  • $\begingroup$ It would help to say: we can choose $\xi$ so that the $r_i$'s all have integral coefficients. Then when $p$ is an appropriate divisor of $q(x_0)$, it also divides $p_i(r_i(x_0))$, and those are appropriate integer values of $p_i$. Without a careful choice of $\xi$, the $r_i(x_0)$ and $p_i(r_i(x_0))$ could be fractional. $\endgroup$
    – Matt F.
    Sep 10 '16 at 1:07
  • $\begingroup$ @Matt: That's why I speak on the prime divisors $p$ which do not divide the denominators of the coefficients (there exist such, because the values of $q$ have infinitely many prime divisors). I am not sure tha you can choose $\xi$ so that $q$ and all the $r_i$ have integer coefficients. $\endgroup$ Sep 10 '16 at 12:24
  • $\begingroup$ @IlyaBogdanov I don't quite see through the last step. You can assume $r_i\in\mathbb Z[x]$. Then $q$ would generally be in $\mathbb Q[x]$ rather than $\mathbb Z[x]$. If you write $p_i(r_i(x))=q(x)s_i(x)$, then generally $s_i\in\mathbb Q[x]$. Then you have to choose prime divisor of the numerator of $q(x)$ that is also coprime to the denominators of $s_i(x)$. Without any information on $s_i$, I can't see a way to show this without showing that $q(x)$ has roots in infinitely many $\mathbb F_p$, which is more or less Chebotarev's density theorem. $\endgroup$
    – Fan Zheng
    Jan 13 '17 at 1:26
  • 1
    $\begingroup$ @FanZheng: The fact that the values of a non-constant polynomial with integer coefficients at integer points have infinitely many prime divisors is elementary and easy. Arguing indirectly, assume that $q_0$ is the constant term, and $p_1,\dots,p_n$ are all prime divisors of the values; surely $q_0\neq 0$. Then it suffices to plug in $x=(Nq_0p_1\dots p_n)^2$, where $N$ is large enough to ensure that the value is greater than $q_0$ (in absolute value). $\endgroup$ Jan 20 '17 at 23:59

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.