Division algorithm for polynomials

[Kate2010]

Homework Statement

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\leqR<N. The division algorithm for real polynomials tells us that there exist real polynomials q and r such that x^M - 1 = q(x^N - 1) + r with r = 0 or deg r < N. Find q and r.

Homework Equations

The Attempt at a Solution

I have rewritten it as x^QN+R - 1 = q(x^N - 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 :)

 

[VeeEight]

Take p(x) = x^m - 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.

 

[Kate2010]

So I get to

x^M-1 + x^M-2 + ... + 1 = q(x^M-1 + x^M-2 + ... + 1) + r

But I don't know what to do now?

 

[VeeEight]

You are trying to figure out q and r in: x^M - 1 = q(x^N - 1) + r

You are aware that x-1 is a factor, which is clearly of the form x^N - 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 + x² + .. + x^m-1. So what is (x-1)q(x)? Does this give you your original polynomial x^M - 1? So then what is r?

 

[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.

 

[Kate2010]

Sorted! Thanks for all the help :)