¿Qué son el máximo común divisor (MCD) y el mínimo común múltiplo (mcm)?
Sean a, b ∈ Z y a, b distintos de cero simultáneamente.
Se dice que un número entero “d” es el Máximo Común Divisor, denotado por mcd (a, b), al mayor de los divisores comunes de “a” y “b”. Si “a” y “b” fueran iguales a cero, se toma por convenio que el mcd (0, 0) sea igual a cero.
Se dice que un número entero “d” es el mínimo común múltiplo, denotado por mcm (a, b), al menor de los enteros que son divisibles tanto por “a” como por “b”.
Así partiendo del teorema fundamental de la aritmética:
mcd (a, b) = p1min (a1, b1) · p2min (a2, b2) · p3min (a3, b3) · … · pnmin (an, bn)
mcm (a, b) = p1max (a1, b1) · p2max (a2, b2) · p3max (a3, b3) · … · pnmax (an, bn)
(Anotación: Puede que haya factores elevados a cero)
Además, mcd (a, b) · mcm (a, b) = a · b
(Más información en Wikipedia: MCD y mcm)
Cálculo del MCD usando el algoritmo de euclídes
El Máximo Común Divisor también se puede calcular usando el algoritmo de euclídes (que viene del siglo III a. C.). Se fundamenta en el siguiente resultado:
Sean a, b ∈ Z, “b” distinto de cero y sea “r” el resto de la división euclídea de “a” por “b”. Entonces:
- Los divisores comunes de “a” y “b” son divisores de “r”.
- Los divisores comunes de “b” y “r” son divisores de “a”.
- mcd (a, b) = mcd (b, r)
- mcd (a, 0) = a
Con estos datos realizamos la división euclídea, de la siguiente forma, siendo r0 = a, r1 = b.
r0 = r1 · q1 + r2 (siendo r2 menor que r1 y mayor o igual a cero)
Se “mueven” las “r’s” hacia la izquierda.
r1 = r2 · q2 + r3 (siendo r3 menor que r2 y mayor o igual a cero)
Se “mueven” las “r’s” hacia la izquierda.
…….
Así seguiríamos “moviendo” las “r’s” hacia la izquierda hasta que en un paso algún resto (rm) sea igual a cero, y por la propiedad mcd (a, b) = mcd (b, r) antes mencionada, tendríamos que mcd (a, b) = mcd (r0, r1) = .. = mcd (rn, 0) = rn.
(Más información en Wikipedia)
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
jchr4, ¿tú sabes la solución?. Porque si es así podías darnos alguna pista, ya que parece que nadie tiene alguna idea interesante para comenzar. Podría dar juego que nos dieras algunas pautas para afrontar este problema.
Esto…máximo común divisor en el idioma de Cervantes
carajo q es el mcd en mi idioma xD JAJAJAJA
Veamos mis amigos gaussianos precisamente tengo una preguntita sobre mcd que me trae loco asi que tal vez acepten el desafio:
“Juan debe escribir en la pizarra varios números enteros positivos distintos entre sí, de modo que se cumplan las siguientes condiciones:
• El máximo común divisor de dos números cualesquiera tiene que ser mayor que 1.
• El máximo común divisor de tres números cualesquiera tiene que ser igual a 1.
• Cada número escrito tiene que ser menor que 5005.
¿Cuántos números, como máximo, podrá escribir Juan?
Con los datos que consignas El MCD(a;b)=1 MCD(a;b;c)=1 entonces los números buscados deben ser primos entre sí. RESUMEN Como desea tener la mayor cantidad de números, entonces iniciamos escribiendo la lista con el 1 y el 2. PRIMERA LISTA: 1; 2 MCD(1;2)=1 SEGUNDA LISTA: 1; 2; 3 ninguna pareja de la lista debe ser divisible por 2. Es decir el MCD de cualquier pareja elegida es 1. MCD(1;2)=MCD(1;3)=MCD(2;3)=1 TERCERA LISTA: 1; 2; 3; 5 ninguna pareja de la lista debe ser divisible por 2, ni 3. Es decir el MCD de cualquier pareja elegida es 1. MCD(1;2)=MCD(1;3)=MCD(1;5)=MCD(2;3)=MCD(2;5)=MCD(3;5)=1 CUARTA LISTA: 1;… Lee más »
El mejor algoritmo que conozco tiene esta pinta en C++:
int MCD(int a, int b){
if (b==0) return a;
return MCD(b, a%b);
}
neok: factores comunes con el mínimo exponente.
El mcd de tres números se podría definir como:
mcd(a,b,c) = mcd(c, mcd(a,b))
Yo recuerdo que para el MCD tengo por ahí un programa que se basa en recursividad, que son cuatro líneas de código y realiza bastante rápido el MCD, no es que sea un problema muy complicado jeje
Y respondiendo a tu pregunta, desde la posición de un no-matemático, supongo que sí habrá MCD de tres o más números y que se definirá igual que los otros, los factores comunes con su mínimo exponente para el MCD y como toque para el mcm.
Corregido, gracias Diamond
Un apunte:
Para el que se pregunte cómo se calcula el mcm de a y b aclaro que el “algoritmo de euclides” que ha explicado neok tiene muy buenas propiedades computacionales (es rápido y estable) de manera que es muy fácil para un ordenador calcular el MCD de a y b.
Usando además la propiedad MCD(a,b)·mcm(a,b)=a·b lo más sencillo es calcular el mcm así:
mcm(a,b) = a·b / MCD(a,b)
PD: Pregunta abierta: ¿Hay MCD de tres o más números (es fácil definirlo)? ¿Y mcm (idem)? ¿Cómo se calculan?
como maximo o como minimo????
me gustaria que me ayuden con ejercicios hechos en C++, por que necesito practicar muchos ya no tengo mucho conocimiento en eso
Explicame lo de MCD(a,b)*MCM(a,b)=a*b
Se que este post se realizó hace mucho tiempo, pero me ha causado inquietud conocer la razón por la cual se convino en que el MCD(0,0) = 0.
Dado que 0 es divisible por todos los enteros diferentes de cero, ¿no es lógico pensar que el MCD(0,0) no existe?, pues los enteros no tienen máximo. ¿O será debido a que el MCD(a,0) = MCD(0,a) = a, cuando a es diferente de cero? ¿Pero no sería esto como convenir que si a/a = 1 para todo a diferente de cero, entonces 0/0 = 1?
Gracias de antemano por la atención prestada.