Proving that there exists $a_i \in \{a_1,\dots,a_k\}$ so that for any positive integer $n$ $F(n)$ is divisible by $a_i$

Given $F(x) \in \mathbb{Z}{[x]}$. For all positive integer $n$ , $F(n)$ is divisible by one of $a_1 , a_2 , \dots , a_k\in \mathbb{Z}$ .how to Prove that there exists $a_i \in \{a_1,\dots,a_k\}$ so that for any positive integer $n$ $F(n)$ is divisible by $a_i$

Solution 1:

Suppose that no $a_i$ divides $F(n)$ for every $n$.

For each $a_i$, there is a power of prime factor of $a_i$ that does not divide $F(n)$ for every $n$. This forms a set of prime powers from which we can extract the minimum elements with respect to divisibility: $p_1^{e_1},\dots,p_m^{e_m}$, with $p_1,\dots,p_m$ distinct primes. Call $q_j$ any number such that $p_j^{e_j} \nmid F(q_j)$.

By the Chinese remainder theorem, there is some $n_0$ such that for every $j$: $$n_0\equiv q_j \pmod{p_j^{e_j}}$$

Therefore: $$F(n_0)\equiv F(q_j)\pmod {p_j^{e_j}}$$ so by definition of $q_j$, $p_j^{e_j} \nmid F(n_0)$. As a consequence no $a_i$ can divide $F(n_0)$: this contradicts the hypothesis.

So there must be some $a_i$ that divides $F(n)$ for every $n$.