Ingeniera en Sistemas

Algoritmo de Euclides (M.C.D.), Algoritmo de la División y Teorema Fundamental de la Aritmética
Se llama así por Euclides de Alejandría, un matemático griego que vivió en los tiempos del faraón Ptolomeo I, del que nos han quedado algunos textos recopilatorios del saber matemático y geométrico de su época. No es que Euclides escribiera tal cual éste algoritmo, sino que, aparentemente, dejóescritas algunas relaciones entre números que son la base de lo que hoy llamamos MCD.
EUCLIDES:
fue un matemático y geómetra griego Se le conoce como "El Padre de la Geometría"
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 ligeramodificació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.
El algoritmo de Euclides es un procedimiento para calcular el m.c.d. de dosnú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 resto obtenido y se continúa de esta forma hasta obtener una división exacta, siendo el último divisor el m.c.d.

Algoritmo 1 de Euclides
Entrada: Valores y pertenecientes a un dominio euclídeo
Salida: Unmáximo común divisor de y
1. ,
2.
3. Mientras haga lo siguiente:
1.
2.
4. El resultado es:

El algoritmo de Euclides es un método eficaz para calcular el máximo común divisor (mcd) de dos números enteros.
El algoritmo consiste en varias divisiones euclídeas sucesivas. En la primera división, se toma como dividendo el mayor de los números y como divisor el otro (se ahorra así un paso).Luego, el divisor y el resto sirven respectivamente de dividendo y divisor de la siguiente división. El proceso se para cuando se obtiene un resto nulo. El mcd es entonces el penúltimo resto del algoritmo.
Formalmente, si llamemos a, b los enteros iniciales, r1, rn ... rn-1 y rn = 0 los restos sucesivos, entonces:
mcd (a, b) = mcd (b, r1), con r1 = a - b·q (q es el cociente de a por b)
Enefecto los divisores comunes de a y b son los de a - b·q y b:  

porque si q divide a y b, obviamente divide a - b·q que es una combinación lineal de ambos, y recíprocamente a = (a - b·q) + b·q es una combinación lineal de b y a - b·q. Luego el menor de los divisores comunes es el mismo, y repitiendo la operación:
mcd (b, r1) = mcd (r1, r2) = mcd (r2, r3) = ... = mcd (rn-1, rn) = mcd (rn-1, 0) =rn-1.
Esto permite detallar el algoritmo efectivo:
datos de entrada a y b   -  si hace falta, cambiarlos a positivos
el algoritmo:
mientras b ≠ 0 repetir las tres instrucciones siguientes:
r ← resto de a / b     (dar a r el valor del resto de a dividido por b)      
a ← b     (el nuevo valor de a es el antiguo valor de b)
b ← r     (el nuevo valor de b es el valor de r)
el resultadoes a (su último valor).
Este algoritmo da como resultado 0 si a y b son nulos, mientras que en matemáticas, el mayor divisor de cero no existe.
teorema fundamental de la Aritmética
en la teoría de números, el teorema fundamental de la Aritmética o teorema de factorización única afirma que todo entero positivo se puede representar de forma única como producto de factores primos. Por ejemplo,El teorema fue prácticamente demostrado por primera vez por Euclides, aunque la primera prueba completa apareció en las Disquisitiones Arithmeticae de Carl Friedrich Gauss.
Aunque a primera vista el teorema parezca "obvio", no vale en sistemas numéricos más generales, entre estos muchos anillos de enteros algebraicos. Ernst Kummer fue el primero en notar esto en 1843, en su trabajo sobre el...