# 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$$\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.

## 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 :)

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.

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?

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?