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!

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