MASSIMO COMUN DIVISORE E MINIMO COMUNE MULTIPLO

Il Massimo Comun Divisore (MCD) di due numeri interi è il più grande numero intero per il quale possono essere entrambi divisi.
Consideriamo ad esempio i due numeri 28 e 36.
I divisori propri di 28 sono: 1, 2, 4, 7 e 14.
I divisori propri di 36 sono: 1, 2, 3, 4, 6, 9 e 18
Ricordiamo che si definiscono “divisori propri” di un numero tutti i suoi divisori, tranne il numero stesso.
Osservando i divisori propri di questi due numeri, notiamo subito che il più grande divisore comune è 4, per cui potremo scrivere:
MCD (28, 36) = 4
Se il Massimo Comun Divisore di due numeri è 1, come per esempio nel caso di 36 e 25, allora i due numeri si dicono “coprimi” o “primi fra loro”.
La definizione di Massimo Comun Divisore si estende anche nel caso di più di due numeri.
Consideriamo ad esempio i numeri 22, 28 e 36.
I divisori propri di 22 sono: 1, 2 ed 11.
I divisori propri di 28 sono: 1, 2, 4, 7 e 14.
I divisori propri di 36 sono: 1, 2, 3, 4, 6, 9 e 18.
Si vede subito che sarà:
MCD (22, 28, 36) = 2
Un metodo pratico per trovare il MCD tra due o più numeri, è quello che si insegna alla scuola media: si scompongono i numeri in fattori primi, si prendono solo i fattori comuni una sola volta con il minimo esponente ed infine si moltiplicano fra loro.
Facciamo un esempio.
Si voglia calcolare MCD (36, 120).
36 = 2² x 3²
120 = 2³ x 3 x 5
Tra 2² e 2³ prenderemo solo 2². Tra 3² e 3 prenderemo solo 3. Non ci sono altri fattori comuni.
Risulterà:
MCD (36, 120) = 2² x 3 = 12
A questo punto ricordiamo il metodo della scuola media per scomporre un numero in fattori primi: scriviamo il numero tracciando a destra dello stesso una riga verticale. Cerchiamo il più piccolo numero primo per cui è divisibile il numero di partenza e lo scriviamo a destra della linea verticale. Scriviamo il quoziente sotto al numero da scomporre e procediamo sempre così, fino a giungere ad un numero primo, quando la scomposizione sarà terminata.

Un metodo molto più efficiente per trovare il MCD tra due numeri è l’Algoritmo di Euclide:
Dati due numeri A e B di cui A è il maggiore, si divide A per B.
Sia R il resto della divisione.
Se R = 0, allora B = MCD (A, B)
Se R è diverso da zero, si divide B per R e si procede reiterando il procedimento finchè non si giunga ad R = 0.
Come esempio applichiamo l’Algoritmo di Euclide ai nostri due numeri 36 e 120:
120 : 36 = 3 con resto 12
36 : 12 = 3 con resto zero.
Dunque:
MCD (36, 120) = 12.
Se M = MCD (A, B), allora vale il lemma di Bezout: esisteranno sempre due numeri x ed y tali che:
Ax + By = M
Nel nostro esempio (36 e 120), l’identità di Bezout è soddisfatta per x = -3, y = 1 e per x = 7, y = -2 :
36 x (-3) + 120 x 1 = -108 + 120 = 12
36 x 7 + 120 x (-2) = 252 – 240 = 12

Il Minimo Comune Multiplo (mcm) di due numeri interi A e B è il più piccolo numero intero multiplo sia di A che di B.
Anche in questo caso la definizione si può estendere a più di due numeri.
Il mcm di due o più numeri si calcola facendo il prodotto di tutti i loro fattori primi, presi una sola volta, col massimo esponente.
Usiamo come esempio sempre i nostri due numeri 36 e 120:
36 = 2² x 3²
120 = 2³ x 3 x 5
mcm (36, 120) = 2³ x 3² x 5 = 8 x 9 x 5 = 360.
Esiste anche un metodo di calcolo più veloce se si conosce già MCD (A, B), perchè:
                                    A x B
mcm (A, B) = __________

                              MCD (A, B)

Nel nostro esempio:

mcm (36, 120) = (36 x 120) / 12 = 4320 / 12 = 360