Given $f(x) \in \mathbb{Z} [x] $ a polynomial, that evaluated in any $a \in \mathbb{N} $, results always in a multiple of 101 or a multiple of 107 (both prime numbers). Prove then, that $f(x)$ is always divisible by 101 for all the values of $a$, or $f(x)$ is always divisible by 107 for all $a$.

Any suggestions on how should I start?

  • $\begingroup$ What should I do if I don't know where to start? $\endgroup$
    – dfeuer
    Dec 10 '13 at 16:42
  • 1
    $\begingroup$ I'm stunned: it says that $\;f(a)\;$ is always divisible by $\;101\;$ or by $\;107\;$ , and then it asks to prove...this! Am I missing something here? $\endgroup$
    – DonAntonio
    Dec 10 '13 at 16:47
  • 1
    $\begingroup$ @DonAntonio, I think he has $f(a)=0(mod 101\times 107)$ and wants to prove $f(a)=0(mod 101)$ and $f(a)=0(mod 107)$. $\endgroup$
    – Michael
    Dec 10 '13 at 16:49
  • $\begingroup$ exactly, sorry that might have been lost in my translation $\endgroup$
    – FranckN
    Dec 10 '13 at 16:51
  • $\begingroup$ Hmmm...I'm not sure, @Michael : it says "multiple of 101 or multiple of 107" ...Perhaps the OP means that under the assumption that an integer polynomial is always divisible either by one prime or by other prime then in fact it is always divisible by only one of those primes... $\endgroup$
    – DonAntonio
    Dec 10 '13 at 16:52

You have a very valuable hypothesis that $f\in\Bbb Z[x]$: the coefficients are integers (if this were not given you could only prove them to be rational). This allows reducing the polynomial itself modulo any number$~n$, and conclude that the evaluated polynomial $f(k)$ modulo$~n$ depends only on the congruence class of the value$~k$ (at which it was evaluated) modulo$~n$. Now for a proof by contradiction assume $f(k)$ is not divisible by$~107$ and $f(l)$ is not divisible by$~101$. Using that $107$ and $101$ are relatively prime (which is all that matters here), can you find a value to evaluate at the will give a contradiction?

  • $\begingroup$ I'm not seeing it right now. By intuition, I suppose, $f(kl)$ will give a contradiction but i need to think it a little more, thanks. $\endgroup$
    – FranckN
    Dec 10 '13 at 17:00
  • $\begingroup$ No that's not it. Which values are certainly congruent to $f(k)$ modulo$~107$? Which values are certainly congruent to $f(l)$ modulo$~101$? Do these two sets intersect? $\endgroup$ Dec 10 '13 at 17:04

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.