Trova il massimo comune divisore (MCD) per i grandi numeri
Per i grandi numeri, la scomposizione in fattori primi è difficile. Se vogliamo stabilire il massimo comune divisore (MCD) di alcuni grandi numeri simili, allora si utilizzerà un metodo che non usa la scomposizione in fattori primi, ma utilizzerà l'algoritmo di Euclide... vedi l'esempio sotto.
Vediamo qual è il massimo comune divisore (MCD) dei numeri 53.667 e 25.527:
- 1) 53.667 = 25.527 × 2 + 2.613 (divido il numero più grande con il numero più piccolo)
- 2) 25.527 = 2.613 × 9 + 2.010 (divido il numero più piccolo al resto dell'operazione di sopra)
- 3) 2.613 = 2.010 × 1 + 603 (divido il resto della prima operazione con il resto della seconda operazione)
- 4) 2.010 = 603 × 3 + 201 (divido il resto della seconda operazione con il resto della terza operazione)
- 5) 603 = 201 × 3 (divido il resto della terza operazione con il resto della quarta operazione); in questo momento, non avendo più resto, ci fermiamo, 201 è il numero cercato.
Quindi il massimo comune divisore dei due numeri è l'ultimo resto (diverso da zero, ovviamente).
Se quest'ultimo resto è uguale a uno, allora i due numeri sono primi tra di loro.
Per le operazioni menzionate sopra, l'ultimo divisore, 201 è il massimo comune divisore (MCD) dei numeri 53.667 e 25.527.
Possiamo dimostrare con l'aiuto dell'algoritmo di Euclide anche il fatto che due numeri sono primi tra di loro.
Ad esempio, cerchiamo mcd (87, 41):
- 1) 87 = 41 × 2 + 5 (divido il numero più grande con il numero più piccolo)
- 2) 41 = 5 × 8 + 1 (divido il numero più piccolo con il resto dell'operazione di sopra)
- 3) 5 = 5 × 1 + 0 (divido il resto della prima operazione con il resto della seconda operazione, che però è uno, l'operazione non avrà più resto)
L'ultimo resto diverso da zero delle operazioni di sopra è uguale a 1.
mcd (87, 41) = 1, quindi i numeri sono primi tra di loro.
L'applicazione dell'algoritmo di Euclide per più di due numeri:
L'algoritmo di Euclide si può utilizzare anche per trovare il massimo comune divisore (mcd) per più numeri, ad esempio a, b e c. Si procederà in due tappe. Per primo troveremo il mcd (a, b) = d e poi troveremo il mcd (c, d) = e.
l'algoritmo di Euclide: trova il minimo comune multiplo (mcm) per grandi numeri
Nella situazione dei numeri più grandi diventa scomodo da calcolare il minimo comune multiplo (mcm), perché la scomposizione in fattori primi richiede più tempo.
Con l'aiuto dell'algoritmo di Euclide si trova il massimo comune divisore (mcd) - vedi di sopra, ma anche il minimo comune multiplo (mcm), secondo la regola:
mcm (a, b) = (a × b) / mcd(a, b);
Questo metodo non si può estendere a più di due numeri.