Division algorithm for polynomials

  • Thread starter Kate2010
  • Start date
  • #1
146
0

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[tex]\leq[/tex]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.

Homework Equations





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

Answers and Replies

  • #2
614
0
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.
 
  • #3
146
0
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?
 
  • #4
614
0
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?
 
  • #5
Dick
Science Advisor
Homework Helper
26,260
619
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.
 
  • #6
146
0
Sorted! Thanks for all the help :)
 

Related Threads on Division algorithm for polynomials

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
2
Views
892
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
420
  • Last Post
Replies
3
Views
1K
Top