Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

up vote 6 down vote accepted
+350

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

 
discard

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.