Puntos Extras... Algoritmo Euclidiano

<>

Definicion:

Pues principalmente el algoritmo de Euclides es un método simple y eficaz para encontrar el máximo común divisor entre dos números enteros diferentes de cero. Este algoritmo no requiere factorización.

El MCD de dos números enteros es el mayor entero que divide a ambos, mientras que el resto, el algoritmo de Euclides se basa en el principio de que el MDC no cambia si el menor número se resta de la más grande.

Ejemplo Paso a Paso:

Encontrar el MCD de 252 y 105:

OBTENEMOS COMO RESULTADO 21.

Animacion del algoritmo:

Otro ejemplo para que quede mucho mejor explicado:

Calcularemos el MCD de 348 y 156:

348	156
-312 36 ≠ 0	2

¿De qué otra no es cero, reemplazamos el dividendo y el divisor:

156	36
-144 12 ≠ 0	4

¿De qué otra no es cero, reemplazamos el dividendo y el divisor:

36	12
-36 0	3

Así que el máximo común divisor de los 348 enteros y 156 es 12.

cociente	2	4	3
348	156	36	12
resto	36	12	0

TEOREMA DEL ALGORITMO:

Bibliografia:

http://es.wikipedia.org/wiki/M%C3%A1ximo_com%C3%BAn_divisor

http://www.unalmed.edu.co/~earamosn/cursos/matematicas_discretas_09II/plan/notas-AlgNum.pdf

http://pt.wikipedia.org/wiki/Algoritmo_de_Euclides