- #1
PolyFX
- 31
- 0
Extended Euclidean Algorithm(Example Run-Through)
I need help tracing through an example of Diophantine Equations.
The question:
Find integers x and y such that 37x + 29y = 1.
The use of Euclidean Algorithm is required.
Here is the solution provided by the text:
gcd(29, 37) 37 = 1 · 29 + 8 ==> 8 = 37 − 1 · 29
gcd(29, 8) 29 = 3 · 8 + 5 ==> 5 = 29 − 3 · 8
gcd(8, 5) 8 = 1 · 5 + 3 ==> 3 = 8 − 1 · 5
gcd(5, 3) 5 = 1 · 3 + 2 ==> 2 = 5 − 1 · 3
gcd(3, 2) 3 = 1 · 2 + 1 ==> 1 = 3 − 1 · 2
*I understand this part requires the use of the euclidean algorithm and rearranging the equations to isolate the remainder. *
Cont'd
Now go backwards
1 = 3 − 1 · 2
= 3 − 1 · (5 − 1 · 3) = 2 · 3 − 5
= 2(8 − 1 · 5) − 5 = 2 · 8 − 3 · 5
= 2 · 8 − 3(29 − 3 · 8) = −3 · 29 + 11 · 8
= −3 · 29 + 11(37 − 1 · 29)
= 11 · 37 − 14 · 29
This is the part that I do not understand. So you are going backwords and subsituting the appropriate equations for the numbers.
I understand that you are subbing in 5-1·3 for 2 on the second line. However, how did they simplify 3 − 1 · (5 − 1 · 3) into 2 · 3 − 5? Furthermore, I do not understand how to get any of the "simplified" equations
This is probably a very easy question but I just can't figure it out.
Edit* I've renamed the thread title as I believe it is the concept of the "Extended Euclidean Algorithm" that I need assistance with.
Homework Statement
I need help tracing through an example of Diophantine Equations.
The question:
Find integers x and y such that 37x + 29y = 1.
Homework Equations
The use of Euclidean Algorithm is required.
The Attempt at a Solution
Here is the solution provided by the text:
gcd(29, 37) 37 = 1 · 29 + 8 ==> 8 = 37 − 1 · 29
gcd(29, 8) 29 = 3 · 8 + 5 ==> 5 = 29 − 3 · 8
gcd(8, 5) 8 = 1 · 5 + 3 ==> 3 = 8 − 1 · 5
gcd(5, 3) 5 = 1 · 3 + 2 ==> 2 = 5 − 1 · 3
gcd(3, 2) 3 = 1 · 2 + 1 ==> 1 = 3 − 1 · 2
*I understand this part requires the use of the euclidean algorithm and rearranging the equations to isolate the remainder. *
Cont'd
Now go backwards
1 = 3 − 1 · 2
= 3 − 1 · (5 − 1 · 3) = 2 · 3 − 5
= 2(8 − 1 · 5) − 5 = 2 · 8 − 3 · 5
= 2 · 8 − 3(29 − 3 · 8) = −3 · 29 + 11 · 8
= −3 · 29 + 11(37 − 1 · 29)
= 11 · 37 − 14 · 29
This is the part that I do not understand. So you are going backwords and subsituting the appropriate equations for the numbers.
I understand that you are subbing in 5-1·3 for 2 on the second line. However, how did they simplify 3 − 1 · (5 − 1 · 3) into 2 · 3 − 5? Furthermore, I do not understand how to get any of the "simplified" equations
This is probably a very easy question but I just can't figure it out.
Edit* I've renamed the thread title as I believe it is the concept of the "Extended Euclidean Algorithm" that I need assistance with.
Last edited: