Máximo común divisor (MCD)

El "divisor" de un entero $x$ es un número natural porel cual $x$ puede ser dividido sin residuo.

El máximo divisor común $\text{MCD}$ de dos o más números es el mayor número natural por el que todos estos números pueden ser divididos.

Por ejemplo, al calcular con fracciones, es útil determinar el $\text{MCD}$ del numerador y del denominador para simplificar con él.

Notación Matemática

La tarea de encontrar el máximo común divisor de dos números $x$ y $y$ se denota así $MCD(x,y)$

¿Cómo se obtiene el MCD?

A continuación se presentan 3 métodos diferentes para calcular el MCD:

1. Método con lista de divisores

2. Método del factor primo

3. Método del algoritmo de Euclides

1- Lista de divisores

ste método funciona con números pequeños, donde es fácil comprobar qué divisores tienen.

Ejemplo

buscamos el MCD de $16$ y $20.$ Este ejemplo se denota así: $MCD(16{,}20)$.

El mayor número, que es a la vez un divisor de $16$ y también de $20,$ es $4$ $⇒MCD(16{,}20)=4$

2- Factor primo

El factor primo de dos (o más) números, se puede calcular fácilmente a partir del máximo común divisor.

El $\text{MCD}$ de dos (o más) números es el producto de todos los factores primos que ambos números tienen en común.

Ejemplo 1

Busca el $MCD(12{,}18)$

Paso 1.

Indentificamos los factores para el $12$

Paso 2.

Identificamos los factores para el $18$

Paso 3.

Observando el paso 1 y 2, identificamos los factores comunes que tienen el $12$ y el $18$. En este caso los factores primos comunes son el $2$ y el $3$.

Paso 4.

El producto de sus factores primos comunes es:

Ejemplo 2

Busca el $MCD(120{,}900)$

Ambos números tienen el 2, el 3 y el 5 como factores primos comúnes. Inclusive el factor primo 2 está dos veces tanto para el 120 como para 900.

Ejemplo 3

Busca el $MCD(150{,}26)$

Podemos observar que estos números no tienen ningún factor primo en común. Por esta razón, solo podemos decir que el único factor primo común el el $1$. Así pues, el 150 y el 26 son números primos relativos, pues su máximo común divisor es el $1$.

3- Algoritmo de Euclides

Con el algoritmo de euclides se puede calcular el máximo común divisor con relativa facilidad. A veces es un poco laborioso, pero una vez que lo entiendes, te lleva con seguridad a la meta, incluso con números grandes.

Acá tenemos una descripción sencilla del procedimiento:

Si vas a calcular el $MCD(a,b)$ y $a>b,$ entonces:

Paso 1: Divide $a$ entre $b$, $r$ es el residuo.

Paso 2: Si el residuo es cero, entonces el $MCD(a,b)=b$

Paso 3: Si el residuo es diferente de cero, entonces ahora calcula el $MCD(b,r)$ y vuelve a ejecutar todos los pasos hasta que el residuo sea cero.

Ejemplo

Busca el $MCD(27{,}12)$

Paso 1:

Paso 2:

El residuo es diferente de cero. Seguimos al paso 3.

Paso 3:

Calculamos ahora $MCD(12{,}3)$

... regresamos al paso 1...

Paso 1:

Paso 2:

El residuo es cero, entonces $MCD (12{,}3)$$=4$

Solución: