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}
T(a) ∩ T(b) = { 1 2 4 8}
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}
T(a) ∩ T(b) ∩ T(c) = { 1 3 13 39}
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;