there exist a polynomial $p(x)\in\Bbb{Z}[x]$ of degree $\le n$ that satisfies the following conditions?

$n>1$ and distinct positive integers $a_1,a_2,\ldots,a_{n+1}$ are  given. Does there exist a polynomial $p(x)\in\Bbb{Z}[x]$ of degree  $\le n$ that satisfies the following conditions?

a. $$\forall_{1\le i < j\le n+1}: \gcd(p(a_i),p(a_j))>1 $$ b. $$\forall_{1\le i < j < k\le n+1}: \gcd(p(a_i),p(a_j),p(a_k))=1 $$

This problem is from 2018 Iran Team Selection Test problem 3，I thought about it for a long time didn't do it, even there is no point to counterexamples

Solution 1:

Let $I = \{1, 2, \cdots, n+1\}$ and $J = \{S \subset I \ | \ |S| = 2\}$ (So $|J| = \binom{n+1}2$). For each $S \in J$, pick a prime $p_S$ such that $p_S$ does not divide any of the $a_i - a_j$ for $i, j \in I$ being distinct. Define for each $i \in I$

$$ P_i = \prod_{\substack{S \\ i \in S}} p_i. $$

For each $i \in I$, we construct a prime $Q_i$ satisfying the following conditions:

1. $Q_i \neq Q_j$ for any $j < i$ and $Q_i \notin \{p_S \ | \ S \in J\}$;
2. We have $$ Q_i \equiv P_i^{-1} \pmod{\prod_{j \neq i} (a_i-a_j)}. $$

Note that this construction is possible: we can just search for $i$ progressively: the element $P_i^{-1}$ in condition 2 is invertible thanks to our choice of $p_S$; and by Dirichlet's arithmetic progression we have infinitely many primes $Q_i$ satisfying the condition, and we just need to avoid finitely many primes prohibited in condition 1.

The claim is that the polynomial

$$ f(x) = \sum_{i=1}^{n+1}P_iQ_i\frac{\prod_{\substack{j \in I \\ j \neq i}}(x-a_j)}{\prod_{\substack{j \in I \\ j \neq i}}(a_i-a_j)} $$ is what we desire.

There are several things to check:

First, we need to see that $f(x)$ has integral coefficients.

$$ f(x) \pmod{\mathbb Z} \equiv \sum_{i=1}^{n+1}\frac{\prod_{\substack{j \in I \\ j \neq i}}(x-a_j)}{\prod_{\substack{j \in I \\ j \neq i}}(a_i-a_j)} = 1 \equiv 0. $$

Second, we need to verify the greatest common divisor conditions. Let $i, j, k\in I$ be distinct. Note that $f(a_i) = P_iQ_i$, so $\gcd(f(a_i), f(a_j)) = p_{\{i,j\}}$ and $\gcd(f(a_i),f(a_j),f(a_k)) = 1$.

So we are done.