Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Division algorithm for polynomials

  1. Mar 6, 2010 #1
    1. The problem statement, all variables and given/known data

    M and N are positive integers with M>N. The division algorithm for integers tells us there exists integers Q and R such that M=QN+R with 0[tex]\leq[/tex]R<N. The division algorithm for real polynomials tells us that there exist real polynomials q and r such that xM - 1 = q(xN - 1) + r with r = 0 or deg r < N. Find q and r.

    2. Relevant equations

    3. The attempt at a solution

    I have rewritten it as xQN+R - 1 = q(xN - 1) + r, so I think q must be of degree QN+R-N = N(Q-1)+R

    However, it is not then always (in fact more likely not) true that N(Q-1)+R<N so 1 must have more than 1 term. But I am struggling to know where to go from here.

    Thanks for any help :)
  2. jcsd
  3. Mar 6, 2010 #2
    Take p(x) = xm - 1. What are the roots of p(x)? There is a clearly a root, 1, so x-1 is a factor. Now divide p(x) by x-1.
  4. Mar 6, 2010 #3
    So I get to

    xM-1 + xM-2 + ... + 1 = q(xM-1 + xM-2 + ... + 1) + r

    But I don't know what to do now?
  5. Mar 6, 2010 #4
    You are trying to figure out q and r in: xM - 1 = q(xN - 1) + r

    You are aware that x-1 is a factor, which is clearly of the form xN - 1 (N=1). That gives you a hint on what the degree of r is.
    You have also correctly identified the polynomial q(x) = 1 + x + x2 + .. + xm-1. So what is (x-1)q(x)? Does this give you your original polynomial xM - 1? So then what is r?
  6. Mar 6, 2010 #5


    User Avatar
    Science Advisor
    Homework Helper

    Why don't you use the division algorithm? Practice on something like x^14-1=q(x^3-1)+r. It's actually pretty easy. You just have to replace the numbers with M, Q, R and N.
  7. Mar 6, 2010 #6
    Sorted! Thanks for all the help :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook