¿Cuál es la intuición detrás del algoritmo euclidiano extendido?

Answer 1

Imagine un edificio infinitamente alto e infinitamente profundo con un elevador que solo tiene cuatro botones: [matemática] + a [/ matemática], [matemática] -a [/ matemática], [matemática] + b [/ matemática] y [matemática ] -b [/ matemáticas]. Si presiona un botón, sube o baja tantos pisos. Comenzamos en el piso 0.

Sea [math] d = {\ rm gcd} (a, b) [/ math]. Claramente, cualquier piso que podamos alcanzar será divisible por [math] d [/ math]. Menos obvio, lo contrario también es cierto: se puede llegar a cualquier piso presionando los botones la cantidad correcta de veces.

Para poder llegar a cualquier piso de este tipo, todo lo que necesitamos es una “fórmula” para llegar al piso [math] d [/ math]. (Si repetimos la fórmula tres veces, llegaremos al piso [matemática] 3d [/ matemática]. Para llegar al piso [matemática] -7d [/ matemática], repita la fórmula siete veces pero intercambie cada [matemática] + [ / math] para un [math] – [/ math] y viceversa)

¿Cómo encontramos la fórmula?

Caso base: si [matemática] a> 0 [/ matemática] pero [matemática] b = 0 [/ matemática], la solución es fácil: [matemática] d = a [/ matemática], por lo que solo debemos presionar [matemática ] + a [/ math] una vez.

Caso resuelto recursivamente: si tanto [matemática] a [/ matemática] como [matemática] b [/ matemática] son ​​positivas, imagine un edificio diferente en el que los botones del elevador sean [matemática] + b [/ matemática], [matemática] – b [/ math], [math] + c [/ math] y [math] -c [/ math], donde [math] c = a \ bmod b [/ math]. Sabemos que [math] {\ rm gcd} (a, b) = {\ rm gcd} (b, c) [/ math]: esta es la propiedad utilizada en el algoritmo euclidiano estándar.

El algoritmo euclidiano extendido tiene el siguiente aspecto:

1. Encuentre recursivamente la “fórmula” para el nuevo edificio. La fórmula debe tener la forma “presione el botón” [matemática] + b [/ matemática] “[matemática] x [/ matemática] veces y el botón” [matemática] + c [/ matemática] “[matemática] y [/ matemática] veces (donde [matemática] x [/ matemática] y [matemática] y [/ matemática] pueden ser negativas, lo que significa que debe presionar el botón con el signo opuesto).
   Formalmente, hemos encontrado [math] (d, x, y) [/ math] tal que [math] {\ rm gcd} (b, c) = d [/ math] y [math] bx + cy = d [ /matemáticas].
2. Tenga en cuenta que en nuestro edificio original podemos simular cada botón “[matemática] + c [/ matemática]” presionando “[matemática] + a [/ matemática]” una vez y luego “[matemática] -b [/ matemática]” a Número adecuado de veces. (Es decir, exactamente [math] z = a \ mathop {\ rm div} b [/ math] veces).
   Esto nos da la fórmula para el edificio original: presione el botón “[matemática] + a [/ matemática]” exactamente [matemática] y [/ matemática] veces y presione el botón “[matemática] + b [/ matemática]” exactamente [matemáticas] x-zy [/ matemáticas] veces.

Answer 2

Consideremos un ejemplo.

Deje a = 45 yb = 17. Claramente, el mcd es 1.

El teorema de Euclides establece (suponiendo que a> b) que el mcd (a, b) = mcd (b, a mod b).

Por lo tanto, el mcd de 45 y 17 es el mismo que el mcd de 17 y 11, que es el mismo que el mcd de 11 y 6, etc.

No solicitó la intuición detrás de esto, aunque las otras respuestas en este hilo lo explican bien.

Preguntaste sobre los coeficientes. Es decir, está interesado en calcular los enteros x e y de modo que ax + by = gcd (a, b).

Digamos que notas que 2 (6) – 1 (11) = 1. Es decir, (de alguna manera) lograste encontrar múltiplos de 6 y 11 que difieren según su máximo divisor común.

Tomemos este hecho afortunado, 2 (6) – 1 (11) = 1, y usémoslo para obtener coeficientes para 17 y 11. Los múltiplos de 11 pueden permanecer, pero los múltiplos de 6 son un obstáculo. Recuerde, sin embargo, de dónde provienen los 6 en primer lugar (17 mod 11). Por lo tanto, 6 es la diferencia de múltiplos de 17 y 11. Es decir, 6 = 17 – 1 (11). Entonces podemos reemplazar el 6 en 2 (6) – 1 (11) = 1, con 17 – 1 (11), para darnos 2 (17 – 1 (11)) – 1 (11) = 1. Reunir todo los 11 y 17 da:

2 (17) – 3 (11) = 1.

Podemos repetir esta idea nuevamente para obtener 1 como la diferencia de múltiplos de 45 y 17. Esta vez, son los 11 que no queremos. Entonces reemplazamos el 11 con 45-2 (17). Esto da

2 (17) – 3 (45 – 2 (17)) = 8 (17) – 3 (45) = 1.

Entonces, una vez que tenga el mcd como una combinación lineal de cualquier par de números en la lista de pares en el algoritmo de Euclides, puede rastrear el par de números original con el que comenzó.

Si sigue el algoritmo de Euclides hasta el final, la primera combinación lineal es fácil.

Answer 3

Paso del algoritmo eucleadean: deje que a> b> 0. Luego, el par (a, b) se reemplaza por el par (b, r) donde r es renainder de a por mod b. Al darse cuenta de que el MCD de ambos pares es el mismo, el procedimiento continúa hasta el par (c, 0), y “c” es el MCD.

El siguiente paso es notar que el resto r es una combinación lineal (es decir, expresión lineal con coeficientes enteros) de a y b. De hecho a = n * b + r, y

r = a – n * b

Después de eso, recordemos la propiedad de tranzitividad: si los valores x e y son una combinación lineal de los valores a y b, entonces cualquier combinación lineal de x e y será una combinación lineal de a y b. La prueba es sencilla. En la combinación lineal de x e y, las sustituye con expresiones lineales correspondientes que utilizan los valores a y b. Obtendrá una expresión lineal de a y b en el resultado. Además, calculará los coeficientes si la expresión lineal final es explícita.

Todo eso significa: si comenzó el proceso Euvleadean para los valores A y B, todos los resultados intermedios y el GCS final serán una combinación lineal de A y B. Y los coeficientes en expresiones lineales que necesite se calcularán en cada paso del algoritmo.

Esa es la “intuición” detrás del cálculo de coeficientes en el algoritmo Eucleadean. Francamente, no di idea por qué se llama “extendido”, nos llama el mismo algoritmo.

En la mayoría de las aplicaciones del algoritmo Eucleadean, lo más importante es el hecho de que GCD es una combinación lineal de valores iniciales.