# 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$

-

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

-
What about F(n)=6 and $a_1=12$? There is no prime factor of $a_1$ that doesn't divide F for all n. –  Zander Jul 6 '12 at 14:15
Zander: I think you can make $p_i$ prime powers instead of primes and the proof works. You need only to assume that $p_1, \dots, p_m$ contain relatively prime powers, but you can remove all but the ones with smallest exponent. –  sdcvvc Jul 6 '12 at 14:28
@Zander: absolutely, I fixed it. Thanks! –  Generic Human Jul 6 '12 at 14:30