Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.