Algoritmo De Euclides

Algoritmo de Euclides tradicional

Al dividir entre (números enteros), se obtiene un cociente y un residuo . Es posible demostrar que el máximo común divisor de y es el mismo que el de y (Sea c el máximo común divisor de y ,.Como a=bq+r y c divide a y a 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 m.c.d. de y , 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 y es precisamente . Para fines prácticos, la notación significa máximo común divisor de y . 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

2 273 dividido entre 182 es 1 y sobran 91

3 182 dividido entre 91 es 2 y sobra 0

La secuencia de igualdades implican que . Dado que , entonces se concluye que . 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 y , se siguen las siguientes reglas:

1. Si entonces y el algoritmo termina

2. En otro caso, donde es el resto de dividir entre . Para calcular se utilizan estas mismas reglas

Asuma que llamamos y . Aplicando estas reglas se obtiene la siguiente secuencia de operaciones:

Paso Operación Significado

1 dividido entre es y sobran

2 dividido entre es y sobran

3 dividido entre es y sobran

dividido entre es y sobran

dividido entre es y sobra

Como la sucesión de residuos va disminuyendo, eventualmente un residuo tiene que ser cero y es en ese momento cuando el algoritmo termina. El máximo común divisor es precisamente (el último residuo que no es cero).

Generalización

En realidad el algoritmo de Euclides funciona no sólo para los números naturales, sino para cualesquiera elementos donde 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 polinomios. Por ejemplo, para calcular el máximo común divisor de los polinomios y el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:

Paso Operación Significado

1 dividido entre es y sobra

2

...