1
$\begingroup$

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.

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

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}$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.