Download MÁXIMO COMÚN DIVISOR Algoritmo de Euclides

MÁXIMO COMÚN DIVISOR
Algoritmo de Euclides
Algoritmo.- secuencia de pasos para conseguir un resultado.
Algoritmo de Euclides: es un procedimiento para calcular el
MÁXIMO COMÚN DIVISOR (m.c.d.) de dos números.
Paso 1.- Se divide el número mayor entre el menor.
Paso 2.a) La división es exacta, el divisor es el m.c.d.
b) 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.
m. c. d. ( 256, 96 )
256 96
64 2
96 64
32 1
64 32
00 2
m. c. d. (256, 96) = 32
Factorización para demostrar el algoritmo de Euclides
96
48
24
12
6
3
1
2
2
2
2
2
3
256
128
64
32
16
8
4
2
1
2
2
2
2
2
2
2
2
96 = 2 5 · 3
256 = 2 8
m. c. d. (256, 96)= 2 5 = 32