Division algorithm for polynomials

Let M and N be positive integers with M > N. The division algorithm for Z implies that
there exist integers Q and R such that M = QN + R, where 0=<R<N. The division algorithm for tells us that there exist polynomials q and r such that
x^M -1=q(x^N-1)+r, where r = 0 or deg r < N.
Find q and r.

I understand the division algorithm, but am not quite sure how to go about finding q and r. Help please!

what happen when you try to carry out the long division of x^M - 1 by x^N - 1?

here is the first step:

x^M - 1 = x^(M-N)(x^N - 1) + ????

That gives r=x^M-N -1, but then the degree of r is not necessarily less than n.

Quote:

---

That gives r=x^M-N -1

---

No, this does not necessarily give the remainder x^M-N - 1. (This should be written as x^(M-N) - 1 or, in LaTeX style, as x^{M-N} - 1.) I suggest doing several examples, such as (x^10 - 1) / (x^6 - 1), (x^10 - 1) / (x^4 - 1) and (x^10 - 1) / (x^3 - 1).

right. remember M = QN + R. M-N is not necessarily < N, you have to keep going until it is.

Ok, but for this general case where you have M-N how are you supposed to know when to stop so that you can get a value for r?

Your question is a little vague. There is the long division algorithm. Applying it to x^M - 1 and x^N - 1 gives the quotient and the remainder. If you understand the algorithm, you understand when to stop. Basically, when, after subtraction and bringing down the next term from the numerator, you get a polynomial whose degree is smaller than that of the denominator, that is the remainder.

I suggest doing several examples and then forming a hypothesis about the quotient and the remainder in the general case.