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) + ????
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!
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).That gives r=x^M-N -1
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.