Algoritmo de Euclides

El algoritmo de Euclides es un método antiguo y eficaz 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.

Proposición

Sean a,b enteros no nulos. Entonces mcd(a,b) = mcd(b,r) donde r es el único 0 < r < b tal que existe un entero q con a= bq + r (esto es, que r es el resto de la división de a por b)

Esta proposición nos indica que es igual de válido calcular el mcd(a,b) que el mcd(b,r), con la ventaja de que r es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros.

Algoritmo original de Euclides

AB y CD los segmentos conmensurables.

Ejemplo del algoritmo original de Euclides.

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 el cual 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.

Plantilla:Cita

En lenguaje moderno, el algoritmo se describe como sigue:

1. Dados dos segmentos AB y CD (con AB>CD), restamos CD de AB tantas veces como sea posible. Si no hay residuo, entonces CD es la máxima medida común.
2. Si se obtiene un residuo EA, éste es menor que CD y podemos repetir el proceso: restamos EA tantas veces como sea posible de CD. Si al final no queda un residuo, EA es la medida común. En caso contrario obtenemos un nuevo residuo FC menor a EA.
3. El proceso se repite hasta que en algún momento no se obtiene residuo. Entonces el último residuo obtenido es la mayor medida común.

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

Algoritmo de Euclides tradicional

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

Paso	Operación	Significado
1	2366 dividido entre 273 es 8 y sobran 182	$\mathrm{m}\mathrm{c}\mathrm{d}(2366,273)=\mathrm{m}\mathrm{c}\mathrm{d}(273,182)$
2	273 dividido entre 182 es 1 y sobran 91	$\mathrm{m}\mathrm{c}\mathrm{d}(273,182)=\mathrm{m}\mathrm{c}\mathrm{d}(182,91)$
3	182 dividido entre 91 es 2 y sobra 0	$\mathrm{m}\mathrm{c}\mathrm{d}(182,91)=\mathrm{m}\mathrm{c}\mathrm{d}(91,0)$

La secuencia de igualdades $\mathrm{m}\mathrm{c}\mathrm{d}(2366,273)=\mathrm{m}\mathrm{c}\mathrm{d}(273,182)=\mathrm{m}\mathrm{c}\mathrm{d}(182,91)=\mathrm{m}\mathrm{c}\mathrm{d}(91,0)$ implican que $\mathrm{m}\mathrm{c}\mathrm{d}(2366,273)=\mathrm{m}\mathrm{c}\mathrm{d}(91,0)$. Dado que $\mathrm{m}\mathrm{c}\mathrm{d}(91,0)=91$, entonces se concluye que $\mathrm{m}\mathrm{c}\mathrm{d}(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 $a$ y $b$, se siguen las siguientes reglas:

1. Si $b=0$ entonces $\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=a$ y el algoritmo termina
2. En otro caso, $\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=\mathrm{m}\mathrm{c}\mathrm{d}(b,r)$ donde $r$ es el resto de dividir $a$ entre $b$. Para calcular $\mathrm{m}\mathrm{c}\mathrm{d}(b,r)$ se utilizan estas mismas reglas

Asuma que llamamos $a=r_0$ y $b=r_1$. Aplicando estas reglas se obtiene la siguiente secuencia de operaciones:

Paso	Operación	Significado
1	$r_0$ dividido entre $r_1$ es $q_1$ y sobran $r_2$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_0,r_1)=\mathrm{m}\mathrm{c}\mathrm{d}(r_1,r_2)$
2	$r_1$ dividido entre $r_2$ es $q_2$ y sobran $r_3$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_1,r_2)=\mathrm{m}\mathrm{c}\mathrm{d}(r_2,r_3)$
3	$r_2$ dividido entre $r_3$ es $q_3$ y sobran $r_4$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_2,r_3)=\mathrm{m}\mathrm{c}\mathrm{d}(r_3,r_4)$
$⋮$	$⋮$	$⋮$
$n$	$r_{n-1}$ dividido entre $r_n$ es $q_n$ y sobran $r_{n+1}$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_{n-1},r_n)=\mathrm{m}\mathrm{c}\mathrm{d}(r_n,r_{n+1})$
$n+1$	$r_n$ dividido entre $r_{n+1}$ es $q_{n+1}$ y sobra $0$	$\mathrm{m}\mathrm{c}\mathrm{d}(r_n,r_{n+1})=\mathrm{m}\mathrm{c}\mathrm{d}(r_{n+1},0)$

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 $r_{n+1}$ (el último residuo que no es cero).

Descripción del algoritmo

1.dividir el numero que fue divisor en el paso anterior entre el resto obtenido en el paso anterior

2.despreciar el cociente

3.si el resto obtenido esta vez es 0, el mcd es el divisor de esta operacion, es decir, el último resto no nulo (recordemos que el divisor de esta operación fué el resto en la anterior.

4.Si el resto no es 0, ir al primer paso

Algoritmo de Euclides extendido

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

Fundamentos

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

1. Usar el algoritmo tradicional de Euclides. En cada paso, en lugar de "$a$ dividido entre $b$ es $q$ y de resto $r$" se escribe la ecuación $a=bq+r$ (véase algoritmo de la división).
2. Se despeja el resto de cada ecuación.
3. Se sustituye el resto de la última ecuación en la penúltima, y la penúltima en la antepenúltima y así sucesivamente hasta llegar a la primera ecuación, y en todo paso se expresa cada resto como combinación lineal.

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 $2\times 2$ se usa la siguiente fórmula (véase Producto de matrices): Plantilla:Ecuación Supóngase que se utiliza el algoritmo de Euclides tradicional para calcular los valores $q_i$ y $r_i$ que ahí se describen. Por cada valor $q_i$ calculado se puede formar la matriz $Q_i=\left[\begin{array}{cc}0& 1\\ 1& -q_i\end{array}\right]$. Usando la ecuación Plantilla:Eqnref de manera repetida se puede calcular el producto de las primeras $i$ matrices de este tipo: Plantilla:Ecuación

Resulta ser que los valores $s_i$ y $t_i$ tienen la propiedad de que $r_i=a{s}_i+b{t}_i$, es decir, expresan a $r_i$ como una combinación lineal de $a$ y $b$. Particularmente, como $\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=r_{n+1}$ entonces se tiene $\mathrm{m}\mathrm{c}\mathrm{d}(a,b)=a{s}_{n+1}+b{t}_{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 $Q_i\times \cdots \times Q_3\times Q_2\times Q_1$ en ese mismo orden. La matriz $Q_1$ aparece en el extremo derecho y la matriz $Q_i$ en el izquierdo.

Regresando al primer ejemplo, la sucesión de cocientes es $q_1=8$, $q_2=1$ y $q_3=2$. Entonces se puede calcular Plantilla:Ecuación Utilizando el primer renglón de esta matriz se puede leer que $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.

Descripción formal

Para expresar el algoritmo de Euclides extendido es conveniente notar la manera en que se calculan los valores $s_i$ y $t_i$ con la multiplicación de matrices: Plantilla:Ecuación De esta manera $s_{i+1}=s_{i-1}-q_i{s}_i$ y además $t_{i+1}=t_{i-1}-q_i{t}_i$. Por lo tanto el algoritmo en pseudocódigo se puede expresar como sigue: Plantilla:Algoritmo

Referencias

• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita publicación
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro
• Plantilla:Cita libro