Diophantine Equation(Example Run-Through)

[PolyFX]

Extended Euclidean Algorithm(Example Run-Through)

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.

 

[icystrike]

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.

you need to divide by the gcd respectively to get all the solutions

 

[PolyFX]

Hi icystrike,

I'm not sure what you mean.

After getting all the equations you just continue to use back substitution, right?

I'm having trouble simplifying the expression after using back substitution.

For example in the text
gcd(330,156):
330 = 156 * 2 + 18 which implies 18 = 330 - 156 *2
156 = 18 * 8 + 12 which implies 12 = 156 - 18 * 8
18 = 12 * 1 + 6 which implies 6 = 18 - 12 * 1
12 = 6 * 2 + 0 which implies that gcd(330,156) = 6


By Back Substitution

6 = 18 - 12 * 1
=18 - ( 156 - 8 * 18) * 1 ==> Substituting 156-18*8 for 12
=9 * 18 + (-1) * 156

That last line is where I get stuck. How have they gone from 18 - ( 156 - 8 * 18) * 1 to 9 * 18 + (-1) * 156. In the book it labels the step as "By Algebra" but I'm just not seeing it right now.

 

[icystrike]

x=11+(b/d)t
Such that d is gcd:
x=11+29t

y=-14(a/d)t
y=-14-37t

You can probably change the -14 in the expression of y to positive value if you want to..