Comencemos por encontrar el máximo común divisor de 527 y 341 utilizando el algoritmo euclidiano estándar como calentamiento:
El algoritmo estándar es sucinto y sencillo y nos servirá de pequeña guía para implementar el algoritmo extendido.
Para el Algoritmo Euclidiano Extendido tomaremos la tercera ecuación (en azul), restaremos 155(1) a ambos lados, y haremos un pequeño reordenamiento para hacer una ecuación equivalente en la que se aísle 31.
A continuación sustituiremos 155 por 341-186(1), que se puede encontrar resolviendo la segunda ecuación para 155, dándonos lo siguiente:
Ahora vamos a limpiar esto. Asegúrate de distribuir el signo negativo a través del paréntesis y reemplaza 186 + 186 por 186-2.
Como puedes notar, simplemente estamos trabajando hacia atrás a través del algoritmo estándar. Tendremos que realizar este proceso una vez más para obtener una ecuación que incluya 527 y 341, que es en última instancia nuestro objetivo.
Para ello, sustituye 186 por 527 – 341(1), que proviene de la primera ecuación cuando resolvemos 186.
Vuelve a simplificar la ecuación distribuyendo los 2 y combinando en grupos de 527 y 341.
Ahora hemos expresado 31 como una combinación lineal de 527 y 341. Muy bien, ¿no?
Además, el número del lado opuesto de la combinación lineal es el máximo común divisor. Así que en este caso 31 es el máximo común divisor de 527 y 341.
El Algoritmo Euclidiano Extendido es útil porque da la Identidad de Bezout, así como destaca el gcd.
¡Gracias por leer!