MCD e mcm
Dati a e b, si dice minimo comune multiplo quell’intero l = mcm(a,b) che è multiplo sia di a che di b ed è divisore di ogni altro numero con questa proprietà (equivalentemente, è il più piccolo tra i multipli sia di a che di b).
Similmente, si dice massimo comun divisore quell’intero g = MCD(a,b) che divide sia a che b ed è multiplo di ogni altro numero con questa proprietà (equivalentemente, è il più grande tra i divisori comuni di a e b).
Due numeri, infine, si dicono coprimi se MCD(a,b) = 1.
Per esempio, mcm(4, 6) = 12 e MCD(4, 6) = 2;
mentre mcm(10, 21) = 210 e MCD(10, 21) = 1, quindi i due numeri sono coprimi.
È semplice calcolare questi valori nel caso in cui sia nota la scomposizione in fattori primi dei due interi:
In questo caso infatti la scomposizione del minimo comune multiplo si ottiene prendendo per ogni primo pi il massimo tra gli esponenti αi e βi (assumendo 0 ad esponente per i primi non presenti); mentre la scomposizione del massimo comun divisore si ottiene prendendo per ogni primo pi il minimo tra gli stessi esponenti αi e βi (assumendo sempre 0 ad esponente per i primi non presenti).
Per esempio, mcm(25·5, 23·3) = 25·3·5 = 480 e MCD(25·5, 23·3) = 23 = 8.
Sfruttando la proprietà precedente, e considerando che a +b = min(a,b)+max(a,b), è facile dimostrare l’importante relazione
mcm(a,b)· MCD(a,b) = a ·b.
Per calcolare l’MCD (e di conseguenza, tramite la relazione precedente, anche l’mcm) anche nel caso di numeri grandi di cui non si conosce la scomposizione in fattori primi, è utile il seguente algoritmo di Euclide:
L’algoritmo consiste, in pratica, nell’applicare più volte la divisione con resto e alla fine ricavare il risultato tramite il fatto che MCD(a, 0) = a per ogni intero a.
ESEMPIO
I freni della macchina di Alberto si guastano regolarmente ogni 34 giorni; lui però usa la sua macchina solo ogni 44 giorni. Ogni quanti giorni Alberto è costretto a compiere un incidente?
È sufficiente calcolare il mcm(34, 44). Per farlo calcoliamo prima l’MCD:
MCD(34, 44) =
= MCD(44, 34 mod 44) = MCD(44, 34) =
= MCD(34, 44 mod 34) = MCD(34, 10) =
= MCD(10, 34 mod 10) = MCD(10, 4) =
= MCD(4, 10 mod 4) = MCD(4, 2) =
= MCD(2, 4 mod 2) = MCD(2, 0) = 2
e poi calcoliamo mcm(34, 44) = 34·44/MCD(34,44) = 34·44/2 =748.
Per finire, citiamo il noto Teorema di Bezout:
Teorema di Bezout
Dati due interi qualunque a e b, gli interi ottenibili come combinazioni lineari dei due (cioè come h · a + k · b al variare di h e k interi qualunque) sono tutti e soli i multipli del massimo comun divisore (a,b).
I coefficienti h e k che consentono di ricavare esattamente il massimo comun divisore sono spesso non facili da trovare, anche se è solitamente possibile procedere per tentativi.
(556)