Scribd
Cargar
121 vistas1 página

Algoritmo de Euclides para MCD

El algoritmo de Euclides es un método antiguo para calcular el máximo común divisor (MCD) de dos números enteros. Se basa en dividir sucesivamente el mayor número entre el menor hasta obtener un resto de cero. Originalmente fue descrito por Euclides en su obra Elementos. El algoritmo aprovecha que el MCD de dos números es igual al MCD de su resto y el divisor, permitiendo reducir progresivamente los números hasta encontrar el MCD.

Cargado por

Christian Avila
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
121 vistas1 página

Algoritmo de Euclides para MCD

El algoritmo de Euclides es un método antiguo para calcular el máximo común divisor (MCD) de dos números enteros. Se basa en dividir sucesivamente el mayor número entre el menor hasta obtener un resto de cero. Originalmente fue descrito por Euclides en su obra Elementos. El algoritmo aprovecha que el MCD de dos números es igual al MCD de su resto y el divisor, permitiendo reducir progresivamente los números hasta encontrar el MCD.

Cargado por

Christian Avila
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

ALGORITMO DE EUCLIDES

Algoritmo de Euclides es un mtodo antiguo y eficaz para calcular el


mximo comn divisor (MCD).
Fue originalmente descrito por Euclides en su obra Elementos.
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= b*q + r (esto es,
que r es el resto de la divisin de a por b)
Esta proposicin nos indica que es igual de vlido calcular el mcd(a,
b) que el mcd (b, r), con la ventaja de que r es un entero de menor
tamao que el original a. Esto es aprovechado por el algoritmo de
Euclides para el clculo del mximo comn divisor de dos nmeros
enteros.
El algoritmo de Euclides
Para calcular el m.c.d. de dos enteros a y b (ambos >0, suponemos a
> b) se definen qi y ri recursivamente mediante las ecuaciones:
a = bq1 + r1 (0<r1<b)
b = r1q2 + r2 (0<r2<r1)
r1 = r2q3 + r3 (0<r3<r2)
....
rk-3 = rk-2qk-1 + rk-1 (0<rk-1<rk-2)
rk-2 = rk-1qk (rk=0)
Y de la proposicin anterior, se sigue que:
m.c.d. (a, b) = m.c.d. (b, r1) = m.c.d. (r1, r2) =... = m.c.d. (rk-2, rk-1) =
rk-1
Adems se puede demostrar que el nmero de pasos necesarios para
calcular el mcd de dos nmeros es menor que 5 veces el nmero de
dgitos del menor de ellos.

También podría gustarte