Thread: 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?
Thaks in advance.

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?
Thaks in advance.

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






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

x=2, y=-1

Originally Posted by aidan

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






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


x=2, y=-1

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