Algoritmo de Euclides

El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación, entre otras. Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido a su gran eficiencia.

En la concepción griega de la matemática, los números se entendían como magnitudes geométricas. Un tema recurrente en la geometría griega es el de la conmensurabilidad de dos segmentos: dos segmentos (números) AB y CD son conmensurables cuando existe un tercer segmento PQ que cabe exactamente un número entero de veces en los primeros dos; es decir, PQ «mide» (mensura: medida) a los segmentos AB y CD.

No cualquier par de segmentos es conmensurable, como encontraron los pitagóricos cuando establecen que el lado y la diagonal de un cuadrado no son conmensurables, pero en el caso de dos segmentos conmensurables se desea hallar la mayor medida común posible.

Euclides describe en la proposición VI I.2 de sus Elementos un método que permite hallar la mayor medida común posible de dos números (segmentos) que no sean primos entre sí, aunque de acuerdo a la época tal método se explica en términos geométricos, lo que se ilustra en la siguiente transcripción.

Sean AB y CD los dos números que no son primos uno al otro. Se necesita entonces encontrar la máxima medida común de AB y CD.

Si CD mide AB entonces es una medida común puesto que CD se mide a sí mismo. Y es manifiesto que también es la mayor medida pues nada mayor a CD puede medir a CD. Pero si CD no mide a AB entonces algún número quedará de AB y CD, el menor siendo continuamente restado del mayor y que medirá al número que le precede. Porque una unidad no quedará pues si no es así, AB y CD serán primos uno del otro [Prop. VII.1], lo cual es lo contrario de lo que se supuso.

Por tanto, algún número queda que medirá el número que le precede. Y sea CD midiendo BE dejando EA menor que sí mismo y sea EA midiendo DF dejando FC menor que sí mismo y sea FC medida de AE. Entonces, como FC mide AE y AE mide DF, FC será entonces medida de DF. Y también se mide a sí mismo. Por tanto también medirá todo CD. Y CD mide a BE. Entonces CF mide a BE y también mide a EA. Así mide a todo BA y también mide a CD. Esto es, CF mide tanto a AB y CD por lo que es una medida común de AB y CD.

Afirmo que también es la mayor medida común posible porque si no lo fuera, entonces un número mayor que CF mide a los números AB y CD, sea éste G. Dado que G mide a CD y CD mide a BE, G también mide a BE. Además, mide a todo BA por lo que mide también al residuo AE. Y AE mide a DF por lo que G también mide a DF. Mide también a todo DC por lo que mide también al residuo CF, es decir el mayor mide al menor, lo cual es imposible.

En lenguaje moderno, el algoritmo se describe como sigue:

El hecho de que los segmentos son conmesurables es clave para asegurar que el proceso termina tarde o temprano

Al dividir ${displaystyle a}$ entre ${displaystyle b}$ (números enteros), se obtiene un cociente ${displaystyle q}$ y un resto ${displaystyle r}$. Es posible demostrar que el máximo común divisor de ${displaystyle a}$ y ${displaystyle b}$ es el mismo que el de ${displaystyle b}$ y ${displaystyle r}$. Sea c el máximo común divisor de ${displaystyle a}$ y ${displaystyle b}$, como ${displaystyle a=bq+r}$ y ${displaystyle c}$ divide a ${displaystyle a}$ y a ${displaystyle b}$, divide también a ${displaystyle r}$. Si existiera otro número mayor que ${displaystyle c}$ que divide a ${displaystyle b}$ y a ${displaystyle r}$, también dividiría a ${displaystyle a}$ , por lo que ${displaystyle c}$ no sería el mcd de ${displaystyle a}$ y ${displaystyle b}$, lo que contradice la hipótesis). Este es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número ${displaystyle a}$ y ${displaystyle 0}$ es precisamente ${displaystyle a}$. Para fines prácticos, la notación ${displaystyle mathrm {mcd} (a,b)}$ significa máximo común divisor de ${displaystyle a}$ y ${displaystyle b}$.

Según lo antes mencionado, para calcular el máximo común divisor de 2366 y 273 se puede proseguir de la siguiente manera:

La secuencia de igualdades ${displaystyle mathrm {mcd} (2366,273)=mathrm {mcd} (273,182)=mathrm {mcd} (182,91)=mathrm {mcd} (91,0)}$ implican que ${displaystyle mathrm {mcd} (2366,273)=mathrm {mcd} (91,0)}$. Dado que ${displaystyle mathrm {mcd} (91,0)=91}$, entonces se concluye que ${displaystyle mathrm {mcd} (2366,273)=91}$. Este mismo procedimiento se puede aplicar a cualesquiera dos números naturales. En general, si se desea encontrar el máximo común divisor de dos números naturales ${displaystyle a}$ y ${displaystyle b}$, se siguen las siguientes reglas:

Asuma que llamamos ${displaystyle a=r_{0}}$ y ${displaystyle b=r_{1}}$. Aplicando estas reglas se obtiene la siguiente secuencia de operaciones:

Como la sucesión de residuos va disminuyendo, al final un residuo tiene que ser cero y es en ese momento cuando el algoritmo termina. El máximo común divisor es precisamente ${displaystyle r_{n+1}}$ (el último residuo que no es cero).

En realidad, el algoritmo de Euclides funciona no sólo para los números naturales, sino para cualquier elemento en el que exista una "división con residuo". A este tipo de divisiones se les llama divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Por ejemplo, el conjunto de los números enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo (véase División polinomial). De esta manera, se puede calcular el máximo común divisor de dos números enteros o de dos polinomias

Por ejemplo, para calcular el máximo común divisor de los polinomios ${displaystyle P(x)=x^{5}+2x^{3}+x}$ y ${displaystyle Q(x)=x^{4}-1}$ el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:

De esta manera se concluye que su máximo común divisor es ${displaystyle -x^{2}-1}$.

Se puede expresar este algoritmo de manera más formal usando pseudocódigo. En este caso la expresión "${displaystyle x;{mod {;}}y}$" significa "el residuo de dividir ${displaystyle x}$ entre ${displaystyle y}$" (véase Aritmética modular).

Entrada: Valores ${displaystyle a}$ y ${displaystyle b}$ pertenecientes a un dominio euclídeo

Salida: Un máximo común divisor de ${displaystyle a}$ y ${displaystyle b}$

Vale la pena notar que este algoritmo no es eficiente ser implementado directamente en una computadora, ya que requeriría memorizar todos los valores de ${displaystyle r_{i}}$.

El algoritmo de Euclides extendido permite, además de encontrar un máximo común divisor de dos números enteros ${displaystyle a}$ y ${displaystyle b}$, expresarlo como la mínima combinación lineal de esos números, es decir, encontrar números enteros ${displaystyle s}$ y ${displaystyle t}$ tales que ${displaystyle mathrm {mcd} (a,b)=as+bt}$. Esto se generaliza también hacia cualquier dominio euclidiano.

Existen varias maneras de explicar el algoritmo de Euclides extendido, una de las más comunes consiste en la siguiente:

Sin embargo, en aras de la comprensión y memorización de este algoritmo, es conveniente conocer la siguiente caracterización. Para multiplicar dos matrices de tamaño ${displaystyle 2 imes 2}$ se usa la siguiente fórmula (véase Producto de matrices):

(1)${displaystyle {egin{bmatrix}e&f\g&hend{bmatrix}} imes {egin{bmatrix}a&b\c&dend{bmatrix}}={egin{bmatrix}ea+fc&eb+fd\ga+hc&gb+hdend{bmatrix}}}$

Supóngase que se utiliza el algoritmo de Euclides tradicional para calcular los valores ${displaystyle q_{i}}$ y ${displaystyle r_{i}}$ que ahí se describen. Por cada valor ${displaystyle q_{i}}$ calculado se puede formar la matriz ${displaystyle extstyle Q_{i}={egin{bmatrix}0&1\1&-q_{i}end{bmatrix}}}$. Usando la ecuación (1) de manera repetida se puede calcular el producto de las primeras ${displaystyle i}$ matrices de este tipo:

${displaystyle {egin{bmatrix}s_{i}&t_{i}\s_{i+1}&t_{i+1}end{bmatrix}}={egin{bmatrix}0&1\1&-q_{i}end{bmatrix}} imes {egin{bmatrix}0&1\1&-q_{i-1}end{bmatrix}} imes cdots imes {egin{bmatrix}0&1\1&-q_{1}end{bmatrix}}}$

Resulta ser que los valores ${displaystyle s_{i}}$ y ${displaystyle t_{i}}$ tienen la propiedad de que ${displaystyle r_{i}=as_{i}+bt_{i}}$, es decir, expresan a ${displaystyle r_{i}}$ como una combinación lineal de ${displaystyle a}$ y ${displaystyle b}$. Particularmente, como ${displaystyle mathrm {mcd} (a,b)=r_{n+1}}$ entonces se tiene ${displaystyle mathrm {mcd} (a,b)=as_{n+1}+bt_{n+1}}$, lo cual es la solución del problema. Esta propiedad no debería ser sorprendente, pues esta multiplicación de matrices equivale al método antes descrito donde se substituye cada ecuación en la anterior. Es importante calcular ${displaystyle Q_{i} imes cdots imes Q_{3} imes Q_{2} imes Q_{1}}$ en ese mismo orden. La matriz ${displaystyle Q_{1}}$ aparece en el extremo derecho y la matriz ${displaystyle Q_{i}}$ en el izquierdo.

Regresando al primer ejemplo, la sucesión de cocientes es ${displaystyle q_{1}=8}$, ${displaystyle q_{2}=1}$ y ${displaystyle q_{3}=2}$. Entonces se puede calcular

${displaystyle {egin{bmatrix}-1&9\3&-26end{bmatrix}}={egin{bmatrix}0&1\1&-2end{bmatrix}} imes {egin{bmatrix}0&1\1&-1end{bmatrix}} imes {egin{bmatrix}0&1\1&-8end{bmatrix}}}$

Utilizando el primer renglón de esta matriz se puede leer que ${displaystyle 91=2366(-1)+273(9)}$, es decir, se ha encontrado la manera de expresar al máximo común divisor de 2366 y 273 como una combinación lineal.

Para expresar el algoritmo de Euclides extendido es conveniente notar la manera en que se calculan los valores ${displaystyle s_{i}}$ y ${displaystyle t_{i}}$ con la multiplicación de matrices:

${displaystyle {egin{bmatrix}s_{i}&t_{i}\s_{i+1}&t_{i+1}end{bmatrix}}={egin{bmatrix}s_{i}&t_{i}\s_{i-1}-q_{i}s_{i}&t_{i-1}-q_{i}t_{i}end{bmatrix}}={egin{bmatrix}0&1\1&-q_{i}end{bmatrix}} imes {egin{bmatrix}s_{i-1}&t_{i-1}\s_{i}&t_{i}end{bmatrix}}}$

De esta manera ${displaystyle s_{i+1}=s_{i-1}-q_{i}s_{i}}$ y además ${displaystyle t_{i+1}=t_{i-1}-q_{i}t_{i}}$. Por lo tanto el algoritmo en pseudocódigo se puede expresar como sigue:

Entrada: Valores ${displaystyle a}$ y ${displaystyle b}$ pertenecientes a un dominio euclídeo

Salida: Un máximo común divisor de ${displaystyle a}$ y ${displaystyle b}$, y valores ${displaystyle s}$ y ${displaystyle t}$ tales que ${displaystyle mathrm {mcd} (a,b)=as+bt}$

Al momento de hacer cálculos con fracciones, es de gran importancia saber cómo simplificarlas. Por ejemplo, la fracción ${displaystyle extstyle {frac {65}{91}}}$ es equivalente con ${displaystyle extstyle {frac {5}{7}}}$ (véase Número racional). De manera más general, ${displaystyle extstyle {frac {a}{b}}={frac {ca}{cb}}}$ siempre que ${displaystyle c eq 0}$. Para reducir una fracción cualquiera ${displaystyle extstyle {frac {a}{b}}}$, sólo se necesita dividir ${displaystyle a}$ y ${displaystyle b}$ entre su máximo común divisor.

Por ejemplo, si se desea reducir ${displaystyle extstyle {frac {166}{249}}}$, primero se usa el algoritmo de Euclides para encontrar ${displaystyle mathrm {mcd} (166,249)=83}$. Se hacen las divisiones ${displaystyle extstyle 166div 83=2}$ y ${displaystyle extstyle 249div 83=3}$. Luego entonces se concluye que ${displaystyle extstyle {frac {166}{249}}={frac {2}{3}}}$.

La sucesión de divisiones que se efectúan al seguir el algoritmo de Euclides puede ser utilizada para expresar una fracción cualquiera ${displaystyle extstyle {frac {a}{b}}}$ como fracción continua. Esto se debe a que si ${displaystyle a=bq+r}$ y ${displaystyle r eq 0}$, entonces

(3)${displaystyle {frac {a}{b}}=q+{frac {1}{frac {b}{r}}}}$

Por ejemplo, para encontrar el máximo común divisor de ${displaystyle 93164}$ y ${displaystyle 5826}$ el algoritmo genera la siguiente secuencia de divisiones:

Todas estas ecuaciones las podemos hacer parecidas a la ecuación (3 3):

Si se sustituye la segunda ecuación en la primera, se obtiene

${displaystyle {frac {93164}{5826}}=15+{frac {1}{1+{frac {1}{frac {5774}{52}}}}}}$

Si se repite este proceso de substitución entonces se obtiene la expresión deseada:

${displaystyle {frac {93164}{5826}}=15+{frac {1}{1+{frac {1}{111+{frac {1}{26}}}}}}}$

De manera más general, la fracción continua encontrada con este algoritmo siempre es de la forma

${displaystyle {frac {a}{b}}=q_{1}+{frac {1}{q_{2}+{frac {1}{q_{3}+{frac {1}{ddots q_{n-1}+{frac {1}{q_{n}}}}}}}}}}$

Decimos que dos números enteros son congruentes módulo ${displaystyle m}$ (aunque también se puede generalizar para cualquier otro dominio euclídeo) si al dividirlos entre ${displaystyle m}$ obtenemos el mismo residuo (véase Congruencia). Por ejemplo, 7 es congruente con 12 módulo 5 porque al dividir 7 entre 5 y 12 entre 5, en ambos casos obtenemos el mismo residuo (que es 2). Cuando ${displaystyle a}$ es congruente con ${displaystyle b}$ módulo ${displaystyle m}$ se escribe ${displaystyle aequiv b{pmod {m}}}$, en el ejemplo anterior se tiene ${displaystyle 7equiv 12{pmod {5}}}$. Supóngase que se conocen los valores de ${displaystyle a}$, ${displaystyle b}$ y ${displaystyle m}$, pero que se desconoce el valor ${displaystyle x}$ en la siguiente congruencia:

(2)${displaystyle axequiv b{pmod {m}}}$

Basta encontrar un valor ${displaystyle a^{-1}}$ que satisfaga: ${displaystyle a^{-1}aequiv 1{pmod {m}}}$, pues de esta manera al multiplicar la ecuación (2) por ${displaystyle a^{-1}}$ se tendrá la solución deseada:

${displaystyle xequiv a^{-1}b{pmod {m}}}$

Al elemento ${displaystyle a^{-1}}$ se le llama "inverso módulo ${displaystyle m}$" de ${displaystyle a}$. Desafortunadamente este valor no siempre existe. Por ejemplo, con ${displaystyle a=4}$ y ${displaystyle m=6}$ no existe ningún número entero ${displaystyle a^{-1}}$ tal que ${displaystyle a^{-1}4equiv 1{pmod {6}}}$. De hecho este valor existe si y sólo si ${displaystyle mathrm {mcd} (a,m)=1}$ (la existencia de soluciones depende de la condición ${displaystyle mathrm {mcd} (a,m)|b}$, mientras que la unicidad depende de que el ${displaystyle mathrm {mcd} (a,m)=1}$). Más aún, si al usar el algoritmo de Euclides extendido (ahora con ${displaystyle b=m}$) se obtiene ${displaystyle 1=as+mt}$, entonces el valor ${displaystyle s}$ es el inverso módulo ${displaystyle m}$ de ${displaystyle a}$. Por ejemplo, se desea resolver la ecuación

${displaystyle 5xequiv 2{pmod {9}}}$

Entonces con el algoritmo de Euclides extendido se obtiene que ${displaystyle mathrm {mcd} (5,9)=1=5(2)+9(-1)}$. Como ${displaystyle mathrm {mcd} (5,9)=1}$ entonces 5 tiene un inverso módulo ${displaystyle 9}$. Más aún, como ${displaystyle 1=5(2)+9(-1)}$, entonces ese inverso es 2. Entonces

${displaystyle xequiv 2(2){pmod {9}}}$

Es decir que el valor de ${displaystyle x}$ es ${displaystyle 4}$.

El teorema de Lamé afirma que el caso peor para este algoritmo es cuando se le pide calcular el máximo común divisor de dos números consecutivos de la sucesión de Fibonacci. Por ejemplo, si se desea calcular el máximo común divisor de ${displaystyle f_{10}=55}$ y ${displaystyle f_{11}=89}$ se obtiene la siguiente secuencia de operaciones:

En este ejemplo se observa que con estos dos números de dos dígitos decimales, se necesita hacer 9 divisiones. En general, el número de divisiones efectuadas por el algoritmo nunca supera 5 veces el número de dígitos que tienen estos números. En términos de complejidad computacional, esto significa que se requieren ${displaystyle O(log n)}$ divisiones para calcular el máximo común divisor de ${displaystyle n}$ y ${displaystyle m}$ donde ${displaystyle n>m}$.

El número promedio de divisiones efectuadas por el algoritmo se estuvo investigando desde 1968, pero solo hasta apenas el año 2002, Brigitte Vallée demostró que si los dos números se pueden representar con ${displaystyle n}$ bits, entonces el número promedio de divisiones necesarias es ${displaystyle extstyle {{frac {pi ^{2}}{6}}n}}$.

Sin embargo, no basta con saber el número de divisiones. Hay que recordar que el algoritmo de Euclides funciona tanto para polinomios como para números enteros, y en general, cualquier dominio Euclídeo. En cada caso, la complejidad del algoritmo depende del número de divisiones efectuadas y del costo de cada división. En el caso de los polinomios, el número de divisiones es ${displaystyle O(log n)}$ donde ${displaystyle n}$ es el grado de los polinomios.

En general, los algoritmos 1 y 2 no son muy apropiados para implementarse directamente en un lenguaje de programación, especialmente porque consumen mucha memoria. Si no se necesitan los valores intermedios, y sólo se desea calcular el máximo común divisor de dos números enteros, conviene usar estas variantes:

Función ${displaystyle mathrm {mcd} (a,b)}$:

Función ${displaystyle mathrm {mcd} (a,b)}$:

Función ${displaystyle { m {Euclides}}(a,b)}$:

Función ${displaystyle { m {Euclides}}(a,b)}$:

Función ${displaystyle { m {Euclides}}(a,b)}$:

Acerca de la notación empleada:

---