Bumping this

For $p(x)\in\Bbb{Q}[x]$ it is easy, the main problem is to be more accurate fo get integer coefficients.

pavel kozlov wrote: For $p(x)\in\Bbb{Q}[x]$ it is easy, the main problem is to be more accurate fo get integer coefficients. Let $M=\left|\prod_{i\neq j}(a_i-a_j)\right|$ and $x_1,x_2,\cdots,x_{n+1}\in\mathbb{N}^*$, the Lagrange interpolation formula tells us that a polynomial $p\in\mathbb{Z}[x]$ with degree $\le n$ exists, such that $p(a_i)=x_i M+1,i=1,2,\cdots,n+1$. Then by the CRT it's easy to get proper $x_1,x_2,\cdots,x_{n+1}\in\mathbb{N}^*$ satisfying the condition.

after arriving at $p(a_i)=x_i M+1,i=1,2,\cdots,n+1$ as above, one can use Dirichlet Theorem to find infinitely many primes $\equiv 1 \pmod M$, and let $p(a_i)$ be the product of some primes.

Darn this solution has basically already been found above , but I'll write it up. The answer is $\boxed{yes}.$ Define $M = \left | \prod_{i \neq j} (a_i - a_j) \right |.$ For each $1 \le i < j \le n+1$, select a prime $p_{ij}$ which is congruent to $1$ (mod $M$). Select these primes in such a way so that all $\binom{n+1}{2}$ of them are distinct, which is doable by Dirichlet's Theorem. By convention, we will let $p_{ji}$ for $j > i$ denote $p_{ij}.$ Now, consider the unique polynomial $P \in \mathbb{R} [x]$ of degree $\le n$ such that: $$P(a_i) = \prod_{j \neq i} p_{ij},$$ for each $1 \le i \le n+1.$ It's easily checked that this polynomial satisfies the conditions of the problem, so all that remains is to check that it has integral coefficients. Indeed, observe that $P(a_i)$ is an integer congruent to $1$ (mod $M$) for each $1 \le i \le n.$ Therefore, the following claim solves the problem. Claim. For any polynomial $Q$ of degree $\le n$ so that $Q(a_i)$ is an integer divisible by $M$ for each $1 \le i \le n+1$, $Q \in \mathbb{Z}[x].$ Proof. By Lagrange's Interpolation Formula, we know that $Q$ is given by: $$\sum_{i = 1}^{n+1} \frac{Q(a_i)}{\prod_{j \neq i} (a_i - a_j)} \cdot \prod_{j \neq i} (x-a_j).$$ It suffices only to observe that $\frac{Q(a_i)}{\prod_{j \neq i} (a_i-a_j)} \in \mathbb{Z}$ since $\prod_{j \neq i} (a_i - a_j) | M | Q(a_i).$ $\blacksquare$ Now, applying the claim on $P - 1$, we've shown that $P -1 \in \mathbb{Z}[x] \Rightarrow P \in \mathbb{Z}[x],$ so we're done. $\square$

A bit too straightforward for a TST #3. Nevertheless , a cool problem

Let $N$ be the product of primes up to $\max\{a_1,\cdots, a_m\}$. We can get $N^k-1$ to be divisible by primes $p_{i,j}$ for $1\le i<j\le n+1$ We construct $P(x)=N^k(x^2+tx)+c$. We want $P(x)\equiv (x-a_i)(x-a_j)$ in $\mathbb{Z}_{p_{ij}}$ so we need $t\equiv a_j+a_i (\bmod\; p_{i,j})$ since $N^k\equiv 1(\bmod\; p_{i,j})$. We select $c$ such that $c\equiv 1(\bmod\; N)$ and $c\equiv a_ia_j(\bmod\; p_{i,j})$. We can construct $t,c$ via the Chinese Remainder Theorem since $\gcd(N, p_{i,j})=1$. I claim $P$ works. Note $p_{i,j}|P(a_i)$ and $p_{i,j}|P(a_j)$. Assume for contradiction $p$ divides $P(a_i), P(a_j)$ and $P(a_k)$. We know $P(x)\equiv 1(\bmod\; p)$ for all primes less than $\max\{a_1,\cdots,a_{n+1}\}$ so $a_1,\cdots,a_{n+1}$ must be injective mod $p$. Then in $\mathbb{Z}_p[x]$, $(x-a_i)(x-a_j)(x-a_k)|P(x)$. Since $\deg P=2$ it follows that $P$ is the zero polynomial. However, $\gcd(N^k,c)=1$ so p cannot divide both simultaneously, contradiction!