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.
Swipe to start coding
Complete the Euclidean Algorithm and test it.
Solution
Thanks for your feedback!
single
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Awesome!
Completion rate improved to 7.69
Euclidean Algorithm
Swipe to show menu
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.
Swipe to start coding
Complete the Euclidean Algorithm and test it.
Solution
Thanks for your feedback!
Awesome!
Completion rate improved to 7.69single