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.
Solución
¡Gracias por tus comentarios!
single
Pregunte a AI
Pregunte a AI
Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla
Resumir este capítulo
Explicar el código en file
Explicar por qué file no resuelve la tarea
Awesome!
Completion rate improved to 7.69
Euclidean Algorithm
Desliza para mostrar el menú
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.
Solución
¡Gracias por tus comentarios!
Awesome!
Completion rate improved to 7.69single