Algoritmo

Un algoritmo es una secuencia de pasos para conseguir un resultado.

El algoritmo de Euclides es un procedimiento para calcular el m.c.d. de dos números. Los pasos son:1 Se divide el número mayor entre el menor.

2 Si:

1 La división es exacta, el divisor es el m.c.d.

2 La división no es exacta, dividimos el divisor entre el restoobtenido y se continúa de esta forma hasta obtener una división exacta, siendo el último divisor el m.c.d.

Ejemplo: División
m.c.d. (72, 16) = 8


En realidad elalgoritmo de Euclides funciona no sólo para los números naturales, sino para cualesquiera elementos en los que exista una "división con residuo". A este tipo de divisiones se lesllama 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 delos 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 puedecalcular el máximo común divisor de dos números enteros o de dos polinomios.

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

Paso Operación Significado
1 x^5+2x^3+x dividido entre x^4-1 es x y sobra 2x^3+2x\mathrm{mcd}(x^5+2x^3+x,x^4-1)=\mathrm{mcd}(x^4-1,2x^3+2x)
2 x^4-1 dividido entre 2x^3+2x es \textstyle{\frac12x} y sobra -x^2-1 \mathrm{mcd}(x^4-1,2x^3+2x)=\mathrm{mcd}(2x^3+2x,-x^2-1)
32x^3+2x dividido entre -x^2-1 es -2x y sobra 0 \mathrm{mcd}(2x^3+2x,-x^2-1)=\mathrm{mcd}(-x^2-1,0)
De esta manera se concluye que su máximo común divisor es -x^2-1....