• Support PF! Buy your school textbooks, materials and every day products Here!

Euclidean algorithm

  • Thread starter roam
  • Start date
  • #1
1,266
11

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]

Homework Equations





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:

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #3
1,266
11
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:

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


P.S. GCD's are only defined up to an invertible constant.
I think I understand, but could you explain a bit more please?
 
  • #4
ideasrule
Homework Helper
2,266
0
Why? Where did the [tex](x+1)(x^2-2x+1)[/tex] 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).
 

Related Threads on Euclidean algorithm

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
6
Views
335
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
Replies
5
Views
1K
Replies
0
Views
3K
Replies
10
Views
1K
  • Last Post
Replies
1
Views
1K
Top