# Euclidean algorithm

## Homework Statement

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]

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

Related Calculus and Beyond Homework Help News on Phys.org
Hurkyl
Staff Emeritus
Gold Member
To begin with, I can't understand why they wrote:
...
What formula/theorem were they using here?
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.

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

P.S. GCD's are only defined up to an invertible constant.
I think I understand, but could you explain a bit more please?

ideasrule
Homework Helper
Why? Where did the $$(x+1)(x^2-2x+1)$$ term come from?
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).