# Euclidean algorithm

1. Sep 26, 2009

### roam

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:

$$x-1 = \frac{1}{3}(x^3-x^2+2x-2)-\frac{1}{3}(x+1)(x^2-2x+1)$$

(or $$3x-3 = (x^3-x^2+2x-2)-(x+1)(x^2-2x+1)$$)

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

P.S. On the top it says $$gcd(2x^3+x^2-2x-1, x^3-x^2+2x-2)= x-1$$, 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. Sep 26, 2009

### Hurkyl

Staff Emeritus
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.

3. Sep 27, 2009

### roam

Before they apply the algebra to prove the identity they wrote:

$$x-1 = \frac{1}{3}(x^3-x^2+2x-2)-\frac{1}{3}(x+1)(x^2-2x+1)$$

Why? Where did the $$(x+1)(x^2-2x+1)$$ term come from?

I think I understand, but could you explain a bit more please?

4. Sep 27, 2009

### ideasrule

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