Euclidean Algorithm

Let’s create a Euclidean algorithm for searching x and y for some integers a and b that

ax + by = gcd(a,b),

where gcd() is the greatest common divisor of a and b.

Searching for gcd(a,b)

We’ll use the fact that gcd(a, b) = gcd(b, a-b), where a >= b. Let’s be greedy and subtract each time as much as possible. The result will be:

gcd(a, b) = gcd(b, a%b)

The algorithm of gcd(a, b) stops when b=0, and the answer is a.

Euclidean Algorithm Realization

Let x and y be the solution of equation ax+by = gcd(a,b) and x1 and y1 are soltion for gcd(b, a%b) = b * x1+a%b*y1. After changing we'll get that `gcd(b, a%b) = b * x1+a%by1 = bx1 + (a - b*a//b)y1 = ay1 + b(x1-a//by1).

Since gcd(a,b) = gcd(b, a%b), multipliers near a and b are equal, so:

x = y1

y = x1-a//b*y1.

We'll use this fact in the algorithm.