# Extended Euclidean Algorithm

Cheryl Scodario

Ranch Hand

Posts: 69

posted 5 years ago

Hi all, I am doing an encryption program, and need to find the x and y in this formula: gcd(a,b)=a*x+b*y;

I know the idea is to follow the steps of the actual Euclidean algorithm, and then just doing everything backwards, but I don't know how to put that in code.

One thing to note, gcd (a, b) will be 1 in my case, because a and b are coprime. so basically we are looking at 1=a*x+b*y and find x and y.

Please give me some hints!

Thanks.

I know the idea is to follow the steps of the actual Euclidean algorithm, and then just doing everything backwards, but I don't know how to put that in code.

One thing to note, gcd (a, b) will be 1 in my case, because a and b are coprime. so basically we are looking at 1=a*x+b*y and find x and y.

Please give me some hints!

Thanks.