Results 1 to 7 of 7

Math Help - Division algorithm for polynomials

  1. #1
    Member
    Joined
    Dec 2010
    Posts
    107

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    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) + ????
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2010
    Posts
    107
    That gives r=x^M-N -1, but then the degree of r is not necessarily less than n.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762
    right. remember M = QN + R. M-N is not necessarily < N, you have to keep going until it is.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2010
    Posts
    107
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 28th 2010, 08:02 AM
  2. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 01:51 PM
  3. The Division Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 16th 2009, 01:45 PM
  4. Division Algorithm
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 18th 2009, 04:11 PM
  5. division algorithm
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: September 7th 2007, 02:39 PM

Search Tags


/mathhelpforum @mathhelpforum