Máximo Común Divisor (M.C.D.
)
¿Qué es el Máximo Común Divisor (MCD)?
Es el mayor número que divide exactamente a dos o más números.
Términos
Divisor
El divisor de un número es el valor que divide al número en partes exactas, es decir, que
el resto sea cero.
Vamos a ver un ejemplo de esto:
Vamos a calcular los divisores de 15:
15 / 1 = 15, por lo que 1 y 15 son divisores de 15.
15 / 2 = 7, el resto es 1, por lo que 2 no es divisor de 15.
15 / 3 = 5, por lo que 3 y 5 son divisores de 15.
15 / 4 = 3, el resto es 3, por lo que 4 no es divisor de 15.
Ahora deberíamos dividir entre 5 pero como ya lo tenemos como divisor, ya hemos
acabado de calcular los divisores de 15.
Ahora vamos a calcular los divisores de 20.
20 / 1 = 20, por lo que 1 y 20 son divisores de 20.
20 / 2 = 10, por lo que 2 y 10 son divisores de 20.
20 / 3 = 6, el resto es 2, por lo que 3 no es un divisor de 20.
20 / 4 = 5, por lo que 4 y 5 son divisores de 20.
Ahora deberíamos dividir entre 5 pero como ya lo tenemos como divisor, ya hemos
acabado de calcular los divisores de 20.
Divisor Común
Es un número que es divisor a la vez de dos o más números, es decir, es un divisor
común a esos números.
Si seguimos con el ejemplo anterior, en el que hemos calculado los divisores de 15 y de
20, ahora vamos a ver cuales son los divisores comunes.
Y en este caso, los divisores comunes de 15 y 20 son el 1 y el 5.
Métodos para Hallar el M.C.D.
Para hallar el máximo común divisor, tenemos los siguientes métodos:
1.- Descomposición de los números en sus factores primos.
2.- Descomposición de los números en forma simultanea.
3.- Por divisiones sucesivas o Algoritmo de Euclides.
Descomposición de los Números en sus Factores Primos
Cuando los números son muy grandes y mentalmente no se puede
determinar por que números será divisible y nos resulta sumamente
laborioso se recurre a descomponer pacientemente cada uno de los números
en forma canónica (Teorema fundamental de la aritmética).
Regla:
Para hallar el M.C.D. de dos o más números, se les descompone en sus
factores primos y se multiplican los factores comunes afectados de sus
menores exponentes.
Ejemplo:
Hallar el M.C.D. de los números 2520; 720 y 540.
Descomposición Simultánea de los Números
El método consiste en dividir todos los números al mismo tiempo por un
factor común, los cocientes nuevamente se dividen por un factor común y
así sucesivamente hasta que nos queden cocientes o números primos entre
sí. Luego el M.C.D. de los números será el producto de los factores
comunes.
Ejemplo:
Hallar el M.C.D. de los números 1140; 780 y 960.
M.C.D. de dos Números por Divisiones Sucesivas
El siguiente teorema es la base para determinar el M.C.D. de dos números,
cuya forma esquemática lleva el nombre de “Algoritmo de Euclides”.
Teorema (Teorema Fundamental):
Si A no es múltiplo de B (A>b) , los divisores comunes del par de números
A y B son los mismos que los del par de números B y R y los del par de
números B y R’, siendo R v R’ los restos por defecto y por exceso de la
división entera A : B.
Demostración:
En efecto: se tienen los tres pares de números A, B; B, R; B y R’. Según (Si
un número divide a otros dos, divide a su suma, a su diferencia y a su
producto), todo divisor común del primer par, lo es de los otros dos, y
recíprocamente todo divisor común del segundo o del tercer par lo es del
primero, luego los tres pares de números tienen los mismos divisores
comunes.
Corolario 1º:
El M.C.D. de dos números no divisibles el uno por el otro, es el mismo que
el del menor y el resto por defecto o por exceso de su división.
Si los tres pares de números A, B; B, R; B y R’ tienen los mismos divisores
comunes, el mayor divisor común de cada par será el mismo en los tres
pares.
Corolario 2º:
La condición necesaria y suficiente para que dos números no divisibles el
uno por el otro, sean primos entre si, es que lo sea el menor con cualquiera
de los restos por defecto o por exceso.
La condición es necesaria, pues si A y B son primos entre sí, M.C.D.( A, B
)= 1, y como.
Se verificará:
La condición es suficiente, pues si cualquiera de los pares B, R; B, R’ son
primos entre sí como:
Teorema de Euclides
El corolario 1º de teorema mencionado anteriormente, nos indica
claramente el procedimiento a seguir para hallar el M.C.D. de dos números
naturales A y B, A>B.
En primer lugar se divide A entre B; si el resto es cero, M.C.D.(A,B) = B.
Si el resto no es cero, como M.C.D.(A,B) =M.C.D.(B,R1). Se dividirá B
entre R1. si el resto de esta división es cero M.C.D.(A,B)
=M.C.D.(B,R1)=R1. si la división de B entre R1 no da resto cero y da resto
R2, como M.C.D.(B,R1)=M.C.D.(R1,R2). M.C.D.(A,b) =M.C.D.(B,R1)=
M.C.D.(R1,R2).
Se divide R1 entre R2 y así sucesivamente, hasta llegar a un resto Rn = 0,
cosa que seguramente ocurrirá, pues como cada resto es menor que el
divisor, la sucesión de restos R1, R2, R3, Rn–1 y Rn va disminuyendo. Si:
Y la forma de proceder es la que indica a continuación, y se denomina
Algoritmo de Euclides.
En los cocientes sucesivos se colocan los cocientes enteros:
Es la parte superior para evitar la perdida de espacio que se produciría
colocando cada cociente debajo del divisor.
Ejemplo.
Hallar el M.C.D. de los números 1112 y 251 por el Algoritmo de Euclides.
Solución:
Hallamos el M.C.D. por el Algoritmo de Euclides:
Propiedades del M.C.D. de Dos Números
1.- El M.C.D. de dos números divisibles entre si es el menor de ellos.
Ejemplos:
• C.D.(40, 1200) = 40
• C.D.(2A, 6A) = 2A
• C.D.(37!, 51!) = 37!
2.- Todo divisor común de dos números, es divisor del M.C.D. de estos.
Ejemplo:
M.C.D.(120, 80) = 40. Los divisores comunes 2; 4; 5; 8; 10 y 20. Dividen a
40.
3.- Si se multiplican o dividen dos números por un mismo número, su
M.C.D. queda multiplicado o dividido por dicho número.
Ejemplo.
Si A = 120, B = 80. : M.C.D.(120, 80) = 40
• C.D. (3A, 3B) = 120
• C.D. (A/5, B/5) = 8
4.- Los cocientes de dividir dos números por su M.C.D. son primos entre sí.
Ejemplo:
Si M.C.D.(48, 66) = 6
Entonces:
• 48 : 6 = 8
• 66 : 6 = 11
Luego:
• 8 y 11 son primos entre sí.
5.- El M.C.D. de dos números de los cuales uno de ellos esta contenido en
el otro, es el menor.
Ejemplos:
• C.D.(15, 150) = 15
• C.D.(12k, 15k) = 12k
