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}
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;