Teoría de números elemental: MCD y mcm
¿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.
Papá Oso | 10 de Agosto de 2006 | 15:28
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?
neok | 10 de Agosto de 2006 | 16:54
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
mimetist | 10 de Agosto de 2006 | 19:46
El mcd de tres números se podría definir como:
mcd(a,b,c) = mcd(c, mcd(a,b))
^DiAmOnD^ | 10 de Agosto de 2006 | 19:51
neok: factores comunes con el mínimo exponente.
Papá Oso | 12 de Agosto de 2006 | 19:56
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);
}
jchr4 | 27 de Agosto de 2006 | 21:54
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?
yo | 30 de Agosto de 2006 | 19:59
carajo q es el mcd en mi idioma xD JAJAJAJA
^DiAmOnD^ | 30 de Agosto de 2006 | 20:12
Esto…máximo común divisor en el idioma de Cervantes
^DiAmOnD^ | 31 de Agosto de 2006 | 2:34
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.
Txomin Gutierrez Rivoal | 9 de Enero de 2007 | 19:59
como maximo o como minimo????
victor | 12 de Enero de 2007 | 0:08
me gustaria que me ayuden con ejercicios hechos en C++, por que necesito practicar muchos ya no tengo mucho conocimiento en eso