Diferencia entre revisiones de «Algoritmo de Euclides»

Contenido eliminado Contenido añadido
HHHanzo (discusión | contribs.)
HHHanzo (discusión | contribs.)
Sin resumen de edición
Línea 1:
El '''algoritmo de Euclides''' es un método antiguo y eficaz para [[cálculo|calcular]] el [[máximo común divisor]] ('''MCD'''). Fue originalmente descrito por [[Euclides]] en su obra ''[[Elementos de Euclides|Elementos]]''. El '''algoritmo de Euclides extendido''' es una ligera modificació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.
 
==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.
 
== Algoritmo original de Euclides ==