# Algoritmo de Euclides

El algoritmo de Euclides es un método para calcular el máximo común divisor (MCD). Fue escrito por Euclides en su obra magna Elementos.

Dicho algoritmo funciona no sólo para los números naturales, sino para cualquier conjunto en el que exista una "división con residuo". A este tipo de divisiones en la que existe residuo se les nombra divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Con lo anterior podemos decir que el algoritmo de Euclides extendido es una ligera modificación del Algoritmo de Euclides 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.

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.

El algoritmo de Euclides se puede representar con la siguiente 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.

Para calcular el \(mcd \) de dos enteros \(a \) y \(b \) (ambos \(>0 \), suponemos \(a > b \)) se definen \(q_i \) y \(r_i \) recursivamente mediante las ecuaciones:

\[a = bq_1 + r_1 \ \ (0<r_1<b) \] \[b = r_1q_2 + r_2 \ \ (0<r_2<r_1) \] \[r_1=r_2q_3 + r_3 \ \ (0<r_3<r_2) \] \[.... \] \[r_{k-3} = r_{k-2}q_{k-1} + r_{k-1} \ \ (0<r_{k-1}<r_{k-2}) \] \[r_{k-2} = r_{k-1}q_k \ \ (r_k=0) \]

Y de la proposición anterior, se sigue que:

\[MCD(a,b) = MCD(b,r_1) = MCD(r_1,r_2) = ... = MCD(r_{k-2},r_{k-1}) = r_{k-1} \]

Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.

©
×

# Créditos

## Escena original

Diseño del contenido | Gustavo Magallanes Guijón
Diseño funcional | Gustavo Magallanes Guijón
Programación | Gustavo Magallanes Guijón
Diseño gráfico | Ricardo López Gómez
Coordinación | Leticia Montserrat Vargas Rocha

## Adaptación

Diseño funcional | Julio Arnoldo Prado Saavedra Victor Manuel Amezcua y Raz
Programación | Julio Arnoldo Prado Saavedra Victor Manuel Amezcua y Raz
Diseño gráfico | Francisco Varela Fuentes
Coordinación | Leticia Montserrat Vargas Rocha

Los contenidos de esta unidad didáctica interactiva están bajo una licencia Creative Commons Reconocimiento-NoComercial-CompartirIgual.

La unidad didáctica fue creada con Arquímedes, una herramienta de código abierto.

La unidad didáctica contiene escenas elaboradas con Descartes, una herramienta de código abierto.

LITE - UnADM 2014