Maximo comun divisor

Máximo común divisor
En matemáticas el máximo común divisor (abreviado mcd o m.c.d.) de dos o más números enteros es el mayor número que los divide sin dejar resto. Por ejemplo, el mcd de 42 y 56 es14. En efecto, y y son primos entre sí (no existe ningún número natural aparte de 1 que divida a la vez al 3 y al 4).
Cálculo del MCD
Los dos métodos más utilizados para el cálculo del máximo comúndivisor de dos números son:
Descomposición en factores primos
El máximo común divisor de dos números puede calcularse determinando la descomposición en factores primos de los dos números y tomandolos factores comunes elevados a la menor potencia, el producto de los cuales será el mcd. Por ejemplo, para calcular el máximo común divisor de 48 y de 60 obtenemos la factorización en factores primosDe las factorizaciones de 48 y 60:
|
|
| |
|
|
El mcd son los factores comunes con su menor exponente, esto es:

En la práctica, este método solo es operativo para númerospequeños tomando en general demasiado tiempo calcular la descomposición en factores primos de dos números cualesquiera.
Algoritmo de Euclides
Artículo principal: Algoritmo de Euclides
Un método máseficiente es el algoritmo de Euclides, que utiliza el algoritmo de la división junto al hecho que el mcd de dos números también divide al resto de dividir el mayor por el más pequeño: se divide 60 por 48dando un cociente de 1 y un resto de 12. El mcd será por tanto divisor de 12. Después se divide 48 por 12 dando un resto de 0, lo que significa que 12 es el mcd. Formalmente puede describirse como:MCD de tres o más números
El máximo común divisor de tres números se puede calcular como sigue:
Propiedades
1. Si entonces
2. Si es un entero,
3. Si es un número primo, entonces o bien
4. Si ,entonces
5. Si es un divisor común de y , entonces
6. Si , entonces
7. Si , entonces:

La última propiedad dice que el máximo común divisor de dos números resulta ser el producto de sus...