Máximo común divisor
Máximo común divisor
Referencias
LECCIÓN 1 de 2
Máximo común divisor
Ecuaciones diofánticas: son un tipo de ecuación de dos incógnitas con
coeficientes enteros, a las cuales se les buscan soluciones también enteras;
por ejemplo, la ecuación x + y = 2 es una ecuación de este tipo, con infinitas
soluciones.
Definición:
Si a y b son enteros, decimos que el entero d es un máximo común divisor, o MCD, de a y b si:
1 d│a y d│b;
2 si c│a y c│b, entonces c│d;
3 d ≥ 0.
Y escribimos d = MCD(a, b).
Cálculo del MCD
En la educación inicial, en nuestra escuela primaria, se nos enseña a calcular el MCD por descomposición de factores
primos.
Figura 1 : Método para hallar el MCD para números pequeños
Fuente: [Imagen sin título sobre máximo común divisor]. (s. f.). Recuperada de https://goo.gl/61I8kz
Este procedimiento es útil siempre y cuando los enteros a y b sean números pequeños. En este curso, el método que
vamos a utilizar para hallar el MCD es el que utiliza el algoritmo de Euclides.
Ejemplo: Cómo encontrar el MCD de 2406 y 654 utilizando el algoritmo de Euclides.
Se empieza haciendo la división de los dos números para encontrar el resto y luego se aplica sucesivamente la
propiedad que dice :
MCD( a,b ) = MCD (b,r) , donde r es el resto de la división de a y b.
MCD(2406, 654) = MCD(654, 444), porque 2406 = 654 . 3 + 444;
= MCD(444, 210), porque 654 = 444 . 1 + 210;
= MCD(210, 24), porque 444 = 210 . 2 + 24;
= MCD(24, 18), porque 210 = 24 . 8 + 18;
= MCD(18, 6), porque 24 = 18 . 1 + 6;
= 6, porque 18 = 6 . 3;
MCD(2406, 654)= 6.
Este proceso debe detenerse, porque cada resto es estrictamente menor que el anterior.En el paso que el resto se hace
cero se obtiene el MCD , como el resto del paso anterior.
Esta forma de encontra el MCD es conocido como el algoritmo de Euclides en honor al matemático griego Euclides
(300 a. C.).
A continuación se va a enunciar un teorema muy importante y de aplicación a distintos ejercicios de la materia.Este
teorema nos dice que el MCD entre dos números a y b se puede expresar como combinación lineal de dichos
números
Teorema
Sean a y b enteros con b ≥ 0, y sea d =MCD(a, b), entonces podemos representar d = x.a + y.b, siendo x e y dos
números enteros.{\displaystyle \operatorname {mcd} (48;60)=2^{2}\cdot 3=12}
Veamos ahora cómo a partir de los cálculos usados para encontrar el MCD de 2406 y 654, podemos expresar al 6
como combinación lineal de ellos dos:
6 = 24 – 18.1 = 1.24 + (−1).18;
= 24 + (−1).(210 – 24.8) = (−1).210 + 9.24;
= −210 + 9.(444 – 210.2) = 9.444 + (−19).210;
= 9.444 +(−19).(654 – 444.1) = (−19). 654 + 28.444;
= (−19).654 + 28.(2406 – 654.3) = 28.2406 + (−103).654.
De este modo, la expresión requerida, d = x.a+ y.b, es:
6 = 28 .2406 + (−103).654.
Realmente parece un trabalenguas matemático, pero, con paciencia y
prolijidad, se desanda el camino que uno hace para encontrar el mcd y se
encuentra la forma de expresar el máximo común divisor como
“combinación lineal” de los enteros a y b. Solo se necesita aplicar una
forma de factor común para las expresiones que tienen los números claves.
Vamos a definir dos conceptos más que están asociados con el MCD: los números coprimos y el mínimo común
múltiplo, MCM.
Números coprimos
Dos números se dice que son coprimos si el MCD entre ellos es el 1.
Mínimo común múltiplo
Si a y b son enteros, decimos que el entero m es un mínimo común múltiplo, o MCM, de a y b si:
1 a│m y b│m;
2 si a│n y b│n, entonces m│n;
3 m ≥ 0.
Y escribimos m = MCM(a, b).
Relación entre el MCD y MCM.
Ejemplo de ejercicio resuelto:
Encuentra enteros n y m que satisfagan: 966n + 685m = 70 (ecuación diofántica).
Primer paso: encontrar el MCD (966, 685):
966 = 1.685 + 281;
685 = 2.281 + 123;
281 = 2.123 + 35;
123 = 3.35 + 18;
35 = 1.18 + 17;
18 = 1.17 + 1;
17 = 17.1 + 0;
MCD (966, 685) = 1.
Escribir el MCD como combinación lineal de 966 y 685.
1 = 18 – 1.17;
= 18 – 1.(35 – 1.18) = -1.35 +2.x 18;
= -1.35 + 2.(123 – 3.35) = 2.123 – 7.35;
= 2.123 – 7.(281- 2.123) = -7.281 + 16.123;
= -7.281 + 16.(685 – 2.281) = 16.685 – 39.281;
= 16.685 – 39.(966 - 1 . 685) = -39 . 966 + 55.685.
Se encontró, a partir del paso anterior, que 1 = -39.966 + 55.685.
Por ende, si se multiplican ambos miembros por 70, se obtiene la siguiente igualdad: 70 = 70.(-39.966 + 55.685).
Apliquemos la propiedad distributiva: 70 = 70 .(-39).966 + 70.55.685.
Solo basta observar qué es lo que buscábamos y a dónde llegamos:
Se deduce entonces que las incógnitas buscadas asumen los siguientes valores: n = -2730 y m = 385.
En este video podremos ver una forma de organizar las cuentas.
Cálculo del m.c.d. y m.c.m. utilizando el algoritmo de eucli…
Fuente: Aula4ALL.; [Aula4ALL]. (2014, Agosto 18). Cálculo del m.c.d. y m.c.m. utilizando el algoritmo de euclides -
Máximo Común Divisor; [Youtube]. Recuperado de https://www.youtube.com/watch?v=x6qFMSRpgpM
LECCIÓN 2 de 2
Referencias
Espinosa Armenta, R. (2010). Matemáticas discretas. México: Alfaomega.
[Imagen sin título sobre máximo común divisor]. (s. f.). Recuperada de
https://univiasecmatematicas1.files.wordpress.com/2012/11/mcd.png?w=419&h=233
