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}
Ejemplo 3:
Además, se determina la suma de todos los divisores s(n) y la suma de los divisores propios s*(n).
Los números que son iguales a la suma de sus divisores propios se llaman números perfectos.
a = 6
b = 28
c = 496
d = 8128
e = 33550336
f = 8589869056
g = 137438691328
Máximo factor común MFC = 2
Minimo común múltiplo mcm = 1,21993659586792E25
Conjunto de divisores :
T(a) = { 1 2 3 6 }
T(b) = { 1 2 4 7 14 28 }
T(c) = { 1 2 4 8 16 31 62 124 248 496 }
T(d) = { 1 2 4 8 16 32 64 127 254 508 1016 2032 4064 8128 }
T(e) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16382 32764 65528 131056 262112 524224 ... }
T(f) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131071 262142 524284 ... }
T(g) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524287 ... }
T(a) n T(b) n T(c) n T(d) n T(e) n T(f) n T(g) = { 1 2 }
Sumas de divisores :
σ(a) = 12 σ*(a) = 6 Número perfecto
σ(b) = 56 σ*(b) = 28 Número perfecto
σ(c) = 992 σ*(c) = 496 Número perfecto
σ(d) = 16256 σ*(d) = 8128 Número perfecto
σ(e) = 67100672 σ*(e) = 33550336 Número perfecto
σ(f) = 17179738112 σ*(f) = 8589869056 Número perfecto
σ(g) = 274877382656 σ*(g) = 137438691328 Número perfecto
La primera mitad del conjunto divisor obviamente siempre forma la secuencia de las potencias de 2..
(Ver también: Factorización prima)
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;