Download El algoritmo de Euclides para calcular el MCD de

El algoritmo de Euclides para calcular el MCD de dos números.
Un algoritmo viene a ser un conjunto de instrucciones o reglas para resolver un problema o realizar
un cálculo.
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 “Los Elementos” hace más de 2300 años.
El algoritmo de Euclides puede describirse así:
Para calcular el máximo común divisor de dos números naturales a y b, dividimos el mayor, digamos
a, entre el menor, digamos b. Esta división nos proporcionará un primer cociente c1, y un primer resto r1. Si
r1 = 0, entonces MCD (a, b) = b. Si no es cero, dividimos el divisor c1 entre el resto r1, obteniendo un
segundo cociente c2, y un segundo resto r2. Si r2 = 0, entonces MCD (a, b) = r1. Si no es cero volvemos a
dividir divisor entre resto. Y así sucesivamente.
En otras palabras, el máximo común divisor de a y b es el último resto distinto de cero que
obtengamos con el procedimiento anterior.
Ejemplos.MCD (25134, 19185)
-----------------------------------------------------------------------MCD (721, 448)
------------------------------------------------------------------------
MCD (132132, 126126)
Algunos criterios de divisibilidad por:
Número
Criterio
Ejemplo(s)
2
El número termina en cero ó en cifra par
(2, 4, 6, 8).
378; porque la última cifra (8) es par.
3
La suma de sus cifras es múltiplo de 3.
480; porque 4+ 8+ 0 = 12 es múltiplo de 3.
El número formado por las dos últimas
cifras es múltiplo de 4 ó termina en doble
cero.
7324: porque 24 es múltiplo de 4.
4
5
La última cifra es 0 ó 5.
485; porque termina en 5.
6
El número es divisible por 2 y por 3 a la
vez.
18; es múltiplo de 2 y de 3 a la vez.
8200; porque termina en 00.
343; 34 − 2 · 3 = 28; 28 es múltiplo de 7, luego 343
también lo es.
105; 10 − 5 · 2 = 0, luego 105 es múltiplo de 7.
7
Un número es divisible por 7 cuando, al
separar la última cifra de la derecha,
multiplicarla por 2 y restarla de las cifras
restantes, la diferencia es igual a 0 ó es
múltiplo de 7.
8
El número formado por las tres últimas
cifras es múltiplo de 8.
27280; porque 280 es múltiplo de 8.
9
La suma de sus cifras es múltiplo de 9.
3744; porque 3+7+4+4= 18 es múltiplo de 9.
10
La última cifra es 0.
470: termina en cifra 0.
11
Se suman las cifras del número que
ocupan posición impar por un lado y las de
posición par por otro. Luego se resta el
resultado de ambas sumas (la mayor
menos la menor). Si este resultado es cero
ó múltiplo de 11, el número es divisible por
11.
34349; separamos el 9 (3434 9) y lo duplicamos
(18), entonces 3434 – 18 = 3416. Repetimos el
proceso separando el 6 (341 6) y duplicándolo
(12), entonces 341 – 12 = 329, y de nuevo,
separando el 9 (32 9), 9 · 2=18, entonces 32 – 18 =
14; por lo tanto, 34349 es múltiplo de 7 porque 14
también lo es.
4224; (4 + 2) − (2 + 4) = 0,
luego 4224 es múltiplo de 11.
42702; (4 + 7 + 2) − (2 + 0) = 13 – 2 = 11,
luego 42702 es múltiplo de 11.
90837197539;
(9 + 8 + 7 + 9 + 5 + 9) − (0 + 3 + 1 + 7 + 3) =
= 47 – 14 = 33, que es múltiplo de 11,
luego 90837197539 es múltiplo de 11.
Algoritmo para calcular la cantidad de divisores de un número
Primero se descompone el número en producto de potencias de factores primos. La cantidad de
divisores se obtiene sumando 1 a cada exponente y multiplicando los resultados obtenidos.
Ejemplos.2
12 = 2 · 3; la cantidad de divisores de 12 es (2 + 1) · (1 + 1) = 3 · 2 = 6 divisores
4
2
144 = 2 · 3 ; la cantidad de divisores de 144 es (4 + 1) · (2 + 1) = 5 · 3 = 15 divisores
4
2
2 520 = 2 · 3 · 5 · 7; la cant. de div. de 2 520 es (3 + 1) · (2 + 1) · (1 + 1) · (1 + 1) = 4 · 3 · 2 · 2 = 48 div.