Máximo Común Divisor

En matemáticas, se define el máximo común divisor(MCD) de dos o más números enteros al mayor número entero que los divide sin dejar resto.

Un número entero d se llama máximo común divisor (MCD) de los números a y b cuando:

  1. d es divisor común de los números a y b y
  2. d es divisible por cualquier otro divisor común de los números a y b.

Ejemplo:

12 es el mcd de 36 y 60. Pues 12|36 y 12|60; a su vez 12 es divisible por 1, -1, 2, -2, 3, -3, 4, -4, 6, -6, 12 y -12 que son divisores comunes de 36 y 60.

Los tres métodos más utilizados para el cálculo del máximo común divisor de dos números son:

Por descomposición en factores primos

El máximo común divisor de dos números puede calcularse determinando la descomposición en factores primos de los dos números y tomando los factores comunes elevados a la menor potencia, el producto de los cuales será el MCD.

Usando el algoritmo de Euclides

Un método más eficiente es el algoritmo de Euclides, que utiliza el algoritmo de la división junto al hecho que el MCD de dos números también divide al resto obtenido de dividir el mayor entre el más pequeño.

Usando el mínimo común múltiplo

El máximo común divisor también puede ser calculado usando el mínimo común múltiplo. Si a y b son distintos de cero, entonces el máximo común divisor de a y b se obtiene mediante la siguiente fórmula, que involucra el mínimo común múltiplo (mcm) de a y b:

mcd

function Euclides(a , b)
Entrada: Dos números enteros, a y b, con a >= b >= 0
Salida: gcd(a; b)
 
if b = 0: return a
return Euclides(b, a mod b)
 
 

Deja un comentario

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