# Extended Euclidean algorithm

• Sep 21st 2009, 09:05 AM
geisonmcd
Extended Euclidean algorithm
Find the greatest common divisor D of the integers A and B, and write D with ax + by.

like in:
a = 60 b = 100

What i did to find the GCD:
100/60=1 remain 40.
60/40=1 remain 20.
40/20=2 remain 0.

GCD(60,100) = 20 that is the last remainder non-null.

Continuing:

40 = 100-1.60
20 = 60-1.40

But what do I do now?
• Sep 21st 2009, 12:09 PM
aidan
Quote:

Originally Posted by geisonmcd
Find the greatest common divisor D of the integers A and B, and write D with ax + by.

like in:
a = 60 b = 100

What i did to find the GCD:
100/60=1 remain 40.
60/40=1 remain 20.
40/20=2 remain 0.

GCD(60,100) = 20 that is the last remainder non-null.

Continuing:

40 = 100-1.60
20 = 60-1.40

But what do I do now?

Reduce both a & b by the gcd, making the revised GCD equal to 1.

$\displaystyle (a): \dfrac{60}{20} = 3$

$\displaystyle (b): \dfrac{100}{20} = 5$

3x + 5y = 1
3(2) + 5(-1) = 1

x=2, y=-1

$\displaystyle ax + by = gcd(a,b)$
$\displaystyle 60 \cdot 2 + 100 \cdot -1 = 20$
• Sep 21st 2009, 01:24 PM
geisonmcd
Where
Quote:

Originally Posted by aidan
Reduce both a & b by the gcd, making the revised GCD equal to 1.

$\displaystyle (a): \dfrac{60}{20} = 3$

$\displaystyle (b): \dfrac{100}{20} = 5$

3x + 5y = 1
3(2) + 5(-1) = 1

x=2, y=-1

$\displaystyle ax + by = gcd(a,b)$
$\displaystyle 60 \cdot 2 + 100 \cdot -1 = 20$

Hey,I didn't get it. From where the 2 and -1 after you have wrote 3x+ 5y = 1 came from?