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

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

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

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

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

x=2, y=-1

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

3. ## Where

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

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

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

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

x=2, y=-1

$ax + by = gcd(a,b)$
$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?