# Homework Help: Division algorithm for polynomials

1. Mar 6, 2010

### Kate2010

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$$\leq$$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. Mar 6, 2010

### VeeEight

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.

3. Mar 6, 2010

### Kate2010

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?

4. Mar 6, 2010

### VeeEight

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?

5. Mar 6, 2010

### Dick

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.

6. Mar 6, 2010

### Kate2010

Sorted! Thanks for all the help :)