¿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)

Print Friendly, PDF & Email