MatheAss 9.0 Álgebra

MFC y mcm

El programa determina para dos o más números el máximo factor común (MFC), el mínimo común múltiplo (mcm) y su respectivo conjunto de divisores.

El MFC es el elemento más grande en la intersección del conjunto de divisores de ay b. En aritmética fraccionaria, el MFC del numerador y del denominador es el número más grande por el que se puede reducir la fracción.

El mcm es el elemento más pequeño en la intersección del conjunto de múltiplos de a y b. Al calcular con fracciones, el mcm de dos denominadores se llama mínimo común denominador.

Si ya ha determinado el MFC(a,b), el mcm(a,b) está determinado por la fórmula

mcm(a,b) = a·b / MFC(a,b)

Ejemplo 1:

a = 24
b = 256

Máximo factor común         MFC  = 8
Minimo común múltiplo       mcm  = 768

Conjunto de divisores  : 
T(a) = { 1 2 3 4 6 8 12 24}
T(b) = { 1 2 4 8 16 32 64 128 256}

Ejemplo 2:

a = 195
b = 234
c = 273

Máximo factor común         MFC  = 39
Minimo común múltiplo       mcm  = 8190

Conjunto de divisores  : 
T(a) = { 1 3 5 13 15 39 65 195}
T(b) = { 1 2 3 6 9 13 18 26 39 78 117 234}
T(c) = { 1 3 7 13 21 39 91 273}

Método

El máximo factor común de dos números se puede determinar a partir de sus factorizaciones primas. Si los números son demasiado grandes, el algoritmo de Euclides da una solución.

Después de Euclides, el MFC no cambió si resta el número menor del mayor. Hoy en día es habitual dividir en lugar de restar y sustituir la diferencia de los dos números por el resto de su cociente.

Algoritmo de Euclides en PASCAL:

function GreatestCommonFactor(a,b:integer):integer;
  var 
    r: integer;
  begin
    repeat
      r:= a mod b;
      a:= b;
      b:= r;
    until r = 0;
    result := a;
  end;

See also:

Wikipedia: Greatest common divisor
Aviso legal esp.matheass.eu