1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenging exercise about polynomials

  1. May 17, 2015 #1
    1. The problem statement, all variables and given/known data

    If ##P,Q## are polynomials of ##\mathbb{Z}[X]##, and ##p## is a prime number that divides all the coefficients of ##PQ##, show that ##p## divides the coefficients of ##P## or the coefficients of ##Q##.

    2. Relevant equations

    ##c_n = \sum_{k=0}^{n} a_k b_{n-k} ## is the n-th coefficient of ##PQ##, where the ##(a_k)_{k=0..N}## are the coefficients of ##P##, and the ##(b_k)_{k=0..M}## are the coefficients of ##Q##

    3. The attempt at a solution

    That exercise gave me a serious headache, but it was an interesting one. Some people may want to try it for themselves.

    @ homework helplers: Do you agree with my solution ?

    I'll do it by induction.

    • Since ## p ## divides ## c_0 = a_0b_0 ##, and since ## p ## is prime, then ##p## divides ##a_0## or ##b_0##.

    • Assume that ##p|a_0, ..., a_n ## or ##p|b_0,...,b_n##.
      If ## n \ge \min\{\text{deg}(P),\text{deg}(Q)\} ## then there is nothing to prove, so we will assume that ## n < \min\{\text{deg}(P),\text{deg}(Q)\} ##. That last inequality and the fact that ##\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q) ## tell us that ##2n+2 \le \text{deg}(PQ) ##

    Case 1: ##p|a_0, ..., a_n ## and there is ## k \in \{0...n\} ## such that ##p|b_0,...,b_{k-1}## and ##p\not | \ b_k ##.
    Since ##p## divides ##c_{n+k+1} = (a_0b_{n+k+1} + ... + a_n b_{k+1}) + a_{n+1} b_k + (a_{n+2} b_{k-1} +...+a_{n+k-1}b_0)## , then ## p | a_{n+1}b_k ##, and with Gauss lemma, ##p|a_{n+1}##

    Case 2: ##p|a_0, ..., a_n ## and ##p|b_0,...,b_n##.
    Since ##p## divides ##c_{2n+2} = (a_0b_{2n+2} + ... + a_n b_{n+2}) + a_{n+1} b_{n+1} + (a_{n+2} b_{n} +...+a_{2n+2}b_0)##, then ## p | a_{n+1}b_{n+1} ##. Since ##p## is prime, it divides ##a_{n+1} ## or ##b_{n+1}##

    Case 3 and 4: They are the symetric cases but assuming this time that ##p|b_0,...,b_n##
    • So by induction, ##p## divides the coefficients of ##P## or the coefficients of ##Q##


     
  2. jcsd
  3. May 17, 2015 #2

    Zondrina

    User Avatar
    Homework Helper

    I really think you could elaborate more here:

    You seem to jump without explaining much detail. Perhaps show there is nothing to prove where you claim, and show some additional inequalities.

    If I may offer an alternative argument, there is an easier way to express the requirement. I will provide an intro to the proof if you are interested:

    Supposing ##p## is a prime number that divides all the coefficients of ##PQ##, we wish to show ##p## divides the coefficients of ##P## or the coefficients of ##Q##.

    Please note: When I write something like ##p|Q## below, I am strictly speaking about dividing the coefficients.

    Suppose ##p|Q##, but ##p \nmid P##. We must show ##p|Q##.

    Since ##p \nmid P##, ##\exists s, t \in \mathbb{Z} \space | \space 1 = \cdots##.

    The proof is almost complete, but there would be no fun in just seeing the answer.
     
  4. May 17, 2015 #3

    Hi, thanks for replying !

    I meant that if ## n \ge \min\{\text{deg}(P),\text{deg}(Q)\}##, and with the induction hypothesis, ##p## divides by definition all the coefficients of ##P## or ##Q##. The interesting part is when ## n < \min\{\text{deg}(P),\text{deg}(Q)\} ##.

    If ## n < \min\{\text{deg}(P),\text{deg}(Q)\} ## then ##\text{deg}(PQ) = \text{deg}(P)+\text{deg}(Q) \ge 2 \min\{\text{deg}(P),\text{deg}(Q)\} \ge 2 (n+1) = 2n +2 ##, and since ##p## divides all the coefficients of ##PQ##, ##p | c_{0},...,c_{2n+2}, ..., c_{\text{deg}(PQ)}##


    I was almost sure there was some easier proof, but did not manage to find it. Please explain.
     
  5. May 18, 2015 #4

    Zondrina

    User Avatar
    Homework Helper

    Suppose ##p|Q##, but ##p \nmid P##. We must show ##p|Q##.

    Since ##p \nmid P##, ##\exists s, t \in \mathbb{Z} \space | \space 1 = Ps + pt \Rightarrow Q = PQs + pQt##.

    Now, ##p## divides the right hand side, so ##p## also divides ##Q##.

    Q.E.D.
     
  6. May 18, 2015 #5
    That works for you too !


    I don't understand the notations that are used. What I get is the following

    You say ##p| c_0,...,c_{\text{deg}(P)+\text{deg}(Q)} ## and you assume ##p\not | a_0,...,a_{\text{deg}(P)} ##, and you want to show ##p|b_0,...,b_{\text{deg}(Q)} ##
    So what I understand is :
    There is some ##a_k## such that ##\text{gcd}(p,a_k) = 1##, so that the family ##(a_0,...,a_{\text{deg}(P)},p)## is relatively prime.
    And now I understand you use Bezout theorem. You say there are ##s_0,...,s_{\text{deg}(P)},t## in ##\mathbb{Z}## such that
    ## 1 = a_0 s_0 + .... +a_{\text{deg}(P)}s_{\text{deg}(P)} + tp ##

    What's the next step?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Challenging exercise about polynomials
Loading...