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.

(Más información en Wikipedia)

Autor: fran

13 Comentarios

  1. 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?

    Publica una respuesta
  2. 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

    Publica una respuesta
  3. El mcd de tres números se podría definir como:

    mcd(a,b,c) = mcd(c, mcd(a,b))

    Publica una respuesta
  4. 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);
    }

    Publica una respuesta
  5. 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?

    Publica una respuesta
    • 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; 2; 3; 5; 7
      ninguna pareja de la lista debe ser divisible por 2, ni 3, ni 5. Es decir el MCD de cualquier pareja elegida es 1.

      QUINTA LISTA: 1; 2; 3; 5; 7; 11
      ninguna pareja de la lista debe ser divisible por 2, ni 3, ni 5, ni 7. Es decir el MCD de cualquier pareja elegida es 1.

      De continuar, observaremos que el conjunto de números que cumplen estas condiciones son: el 1 y todos los números primos menores que 5005.

      El ultimo primo menor que 5005 es 5003.

      la lista sera:
      1 un solo numero
      2; 3; 5; … ; 97 son 24 números primos
      101; 103; …; 997 son 143 números primo
      1009; 1013; …; 5003 son 518 números primos

      En total tendremos 1+24+143+518=686 números.

      Publica una respuesta
  6. 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.

    Publica una respuesta
  7. me gustaria que me ayuden con ejercicios hechos en C++, por que necesito practicar muchos ya no tengo mucho conocimiento en eso

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *