1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Euclidean algorithm

  1. Sep 26, 2009 #1
    1. The problem statement, all variables and given/known data

    The following is a worked example, I circled around the part which I couldn't follow:

    http://img15.imageshack.us/img15/161/untitleou.jpg [Broken]

    2. Relevant equations

    3. The attempt at a solution

    To begin with, I can't understand why they wrote:

    [tex]x-1 = \frac{1}{3}(x^3-x^2+2x-2)-\frac{1}{3}(x+1)(x^2-2x+1)[/tex]

    (or [tex]3x-3 = (x^3-x^2+2x-2)-(x+1)(x^2-2x+1)[/tex])

    What formula/theorem were they using here? I can't follow what is done here. :redface:

    P.S. On the top it says [tex]gcd(2x^3+x^2-2x-1, x^3-x^2+2x-2)= x-1[/tex], but it previously said "the last non-zero remainder is a gcd". And when the Euclidean algorithem was applied we found that the last non-zero remainder is 3x-3 NOT x-1.
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Sep 26, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You're asking why it's true? Just use algebra to prove the identity!

    You're asking why they knew it to be true? It's the middle line of the preceeding calculation.

    You're asking why they thought it would help solve the problem? Presumably your textbook has explicitly presented a version of the extended Euclidean algorithm and is using that.

    P.S. GCD's are only defined up to an invertible constant.
  4. Sep 27, 2009 #3
    Before they apply the algebra to prove the identity they wrote:

    [tex]x-1 = \frac{1}{3}(x^3-x^2+2x-2)-\frac{1}{3}(x+1)(x^2-2x+1)[/tex]

    Why? Where did the [tex](x+1)(x^2-2x+1)[/tex] term come from?

    I think I understand, but could you explain a bit more please?
  5. Sep 27, 2009 #4


    User Avatar
    Homework Helper

    It came from the middle line of the solution to the previous example. The textbook took the 1/3 out of (1/3x+1/3), placed it into (3x^2-6x+3), and ended up with (x+1)(x^2-2x+1).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook