# Division algorithm for polynomials

• April 15th 2011, 06:39 AM
worc3247
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 $\mathbb{R}[x]$ 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!
• April 15th 2011, 11:53 AM
Deveno
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) + ????
• April 15th 2011, 12:09 PM
worc3247
That gives r=x^M-N -1, but then the degree of r is not necessarily less than n.
• April 15th 2011, 01:15 PM
emakarov
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).
• April 15th 2011, 01:31 PM
Deveno
right. remember M = QN + R. M-N is not necessarily < N, you have to keep going until it is.
• April 15th 2011, 02:53 PM
worc3247
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?
• April 15th 2011, 04:26 PM
emakarov
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.