MCD e MCM
Dai due numeri a e b il massimo comune divisore, il minimo comune multiplo e gli insiemi dei divisori vengono calcolati.
Il MCD è l'inserto più grande dei set di divisori di a e b. Nel calcolo della frazione, il numeratore e denominatore MCD è il numero più grande con il quale è possibile ridurre la frazione.
Il MCM è l'inserto più piccolo degli insiemi di multipli di a e b. Nel calcolo della frazione, la MCM dei due denominatori è il denominatore comune.
Se il MCD (a, b) è già stato calcolato, il MCM (a, b) viene calcolato con la formula.
MCM (a, b) = a · b / MCD (a, b)
Esempio 1:
a = 24 b = 256
Il massimo comune divisore MCD = 8
Il minimo comune multiplo MCM = 768
Insieme di divisori:
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}
Exemple 2:
a = 195
b = 234
c = 273
Il massimo comune divisore MCD = 39
Il minimo comune multiplo MCM = 8190
Insieme di divisori:
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}
Esempio 3:
Inoltre, vengono determinate la somma di tutti i divisori σ(n) e la somma dei divisori propri σ*(n).
I numeri che sono uguali alla somma dei loro divisori propri sono chiamati numeri perfetti.
a = 6
b = 28
c = 496
d = 8128
e = 33550336
f = 8589869056
g = 137438691328
Massimo Comun Divisore M.C.D. = 2
Minimo Comune Multiplo M.C.M. = 1,21993659586792E25
Insiemi dei divisori:
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 }
Somme dei divisori:
σ(a) = 12 σ*(a) = 6 numero perfetto
σ(b) = 56 σ*(b) = 28 numero perfetto
σ(c) = 992 σ*(c) = 496 numero perfetto
σ(d) = 16256 σ*(d) = 8128 numero perfetto
σ(e) = 67100672 σ*(e) = 33550336 numero perfetto
σ(f) = 17179738112 σ*(f) = 8589869056 numero perfetto
σ(g) = 274877382656 σ*(g) = 137438691328 numero perfetto
La prima metà dell'insieme dei divisori forma ovviamente sempre la sequenza delle potenze di 2.
(Vedi anche Fattorizzazione in numeri primi)
Metodo
Il MCD di due numeri può essere determinato dalla decomposizione in fattori primi. Se i numeri sono troppo grandi, l'algoritmo di Euclide può aiutare.
L'algoritmo di Euclide in PASCAL:
function MCD (a, b: integer): integer;
var
r: integer;
begin
repeat
r := a mod b;
a := b;
b := r;
until r=0;
result := a;
end;
Vedi anche:
Wikipedia: Massimo comune divisore | Minimo comune multiplo | Numero perfetto