# A polynomial with integer coefficients with prescribed set of roots modulo infinitely many primes

Given an infinite set of distinct prime numbers $p_1, p_2,\ldots,p_n,\ldots$, and arbitrary integres $a_1, a_2,\ldots,a_n,\ldots$, is there a nonzero polynomial $f(x)$ with integer coefficients such that $f(a_i)\equiv 0\pmod {p_i}$ for all $i\geq1$?

For example, let $p_1, p_2,...,p_n,...$ be all prime integers which are congruent to $1$ mod $4$. By a theorem of Euler, for every $i\geq1$, there exists some integer $a_i$, such that $a_i^2+1\equiv 0$(mod $p_i$). Thus the polynomial $f(x)=x^2+1$ has the required property.

• Is the sequence $(a_n)$ also arbitrary? Because in the example you give you do not choose them beforehand. – punctured dusk Jan 12 '16 at 10:54

## 2 Answers

Not in general. There are only countably many candidate polynomials, but uncountably many possible choices of input sequences.

To elaborate: Let us enumerate all nonzero polynomials in $\Bbb Z[X]$ as $f_1,f_2,f_3,\ldots$. For each $i\in\Bbb N$ pick $a_i\in\Bbb Z$ with $f_i(a_i)\ne 0$. Then there are infinitely many primes that do not divide $f(a_i)$. Let $p_i$ be the smallest such prime that does not occur among $p_1,\ldots, p_{i-1}$. Then we have a sequence $p_1,p_2,\ldots$ of distinct primes and a sequence $a_1,a_2,\ldots$ such that no polynomial works. For if $f$ is a nonzero polynomial with integer coefficients, then $f=f_i$ for some $i$ and then $f(a_i)\not\equiv 0\pmod{p_i}$.

Not in general. If the sequence of primes increases exponentially but the sequence of integers increases linearly, then since a polynomial has only finitely many roots there would exist a polynomial s.t. its absolute value increases (at least) exponentially, which is impossible.