algoritmo de eclides


El máximo común divisor de dos o más números es el número, más grande posible, que permite dividir a esos números.
Para calcularlo. De los números que vayas a sacar el máximo común divisor, se ponen uno debajo del otro, se sacan todos los divisores de los dos números y el máximo que se repita es el máximo común divisor (M.C.D.)
Ejemplo: Sacar el M.C.D. de 20 y 10:
20:
1, 2, 4, 5, 10 y 2010:
1, 2, 5 y 10
Esto sirve para números pequeños. Pero para números grandes hay otra manera: la descomposición de factores.
Forma rápida de calcular el Máximo común Divisor (M.C.D.).
Ejemplo: Sacar el M. C. D. de 40 y 60:
1º Tienes que saber las reglas divisibilidad. Haces la descomposición de factores poniendo números primos. Por ejemplo para 40, en la tabla de abajo, se va descomponiendoen 2, 2, 2 y 5.
40
 
2
60
 
2
20

2
30

2
10

2
15

3
5

5
5

5
1

 
1

 
 

 
 

 
2º De los resultados, se cogen los números repetidos de menor exponente y se multiplican y ese es el M.C.D.


MCD = 2x2x5= 20

M.C.D. 40 = 2x2x2x5
M.C.D. 60 = 2x2x3x5

El máximo común divisor (m.c.d. o mcd) de dos o más números es el mayor número que divide a todosexactamente.

Cálculo del máximo común divisor
1 Se descomponen los números en factores primos.
2 Se toman los factores comunes con menor exponente.
3 Se multiplican dichos factores y el resultado obtenido es el mcd.
Ejemplo de cálculo de máximo común divisor
Hallar el m. c. d. de: 72, 108 y 60:
1
Solución:
72 = 23 · 32
108 = 22 · 33
60 = 22 · 3 · 5
2 m. c. d. (72, 108, 60) = 22 · 3 =12
12 es el mayor número que divide a 72, 108 y 60.
Propiedades del máximo común divisor
1 Los divisores comunes de varios números coinciden con los divisores del máximo común divisor.
Ejemplo:
Calcular los divisores comunes de 54 y 90.
m.c.d (54, 90) = 18
Los divisores comunes de 54 y 90 son los divisores de 18, por tanto serían 1, 2, 3, 6, 9, 18.
2 Dados varios números, si semultiplican o dividen por otro número entonces su m.c.d también queda multiplicado o dividido por el mismo número.
Ejemplo:
m.c.d. (54, 90) = 18
Si multiplicamos los dos números por 3 queda:
54 · 3 = 162
90 · 3 = 270
m.c.d. (162, 270) = 54 = 18 · 3
3 Esta propiedad es consecuencia de la anterior: Dados varios números, si se dividen por su m.c.d los cocientes resultantes son primos entre sí (sum.c.d es 1).
Ejemplo:
m.c.d. (54, 90) = 18
54 : 18 = 3
90 : 18 = 5
m.c.d. (3, 5) = 1
4 Si un número es divisor de otro, entonces este es el m. c. d de los dos.
Ejemplo:
El número 12 es divisor de 36.
m.c.d. (12, 36) = 12

Algoritmo original de Euclides

B y CD los segmentos conmensurables.


Ejemplo del algoritmo original de Euclides.
En la concepción griega de la matemática, losnúmeros se entendían como magnitudes geométricas. Un tema recurrente en la geometría griega es el de la conmensurabilidad de dos segmentos: dos segmentos (números) AB y CD son conmensurables cuando existe un tercer segmento PQ el cual cabe exactamente un número entero de veces en los primeros dos, es decir, PQ «mide» (mensura: medida) a los segmentos AB y CD.
No cualquier par de segmentos esconmensurable, como encontraron los pitagóricos cuando establecen que el lado y la diagonal de un cuadrado no son conmensurables, pero en el caso de dos segmentos conmensurables se desea hallar la mayor medida común posible.
Euclides describe en la proposición VI I.2 de sus Elementos un método que permite hallar la mayor medida común posible de dos números (segmentos) que no sean primos entre sí,aunque de acuerdo a la época tal método se explica en términos geométricos, lo que se ilustra en la siguiente transcripción.
Para encontrar la máxima medida común de dos números que no sean primos entre sí.

Sean AB y CD los dos números que no son primos uno al otro. Se necesita entonces encontrar la máxima medida común de AB y CD.
Si CD mide AB entonces es una medida común puesto que CD se...