Massimo comun divisore
Il massimo comun divisore di due numeri interi è quel numero che divide senza resto entrambi i numeri e per il quale non esiste nessun altro numero più grande che divida anche lui entrambi i numeri senza resto.
Come esempio prendiamo i numeri 24 e 32. Qual è il loro massimo comun divisore? Cerchiamo innanzitutto un numero che divida entrambi i numeri.
- Per esempio il numero 12 divide 24, ma non divide 32, perché 32 / 12 è uguale a 2,666… che non è un numero intero. Quindi il numero 12 non può essere il massimo comun divisore di 24 e 32.
- E il numero 4? Divide entrambi i numeri: 24 / 4 è uguale a 6 e 32 / 4 è uguale a 8. Il numero 4 è quindi il nostro primo candidato. Esiste un numero più grande che divida entrambi i numeri?
- Il numero 8 divide sia 24 sia 32 ed è più grande di 4.
- Non esiste nessun altro numero più grande di 8 che divida entrambi i numeri. Il numero 8 è quindi il massimo comun divisore di 24 e 32.
Algoritmo di Euclide per trovare il massimo comun divisore
Esiste un modo abbastanza semplice per trovare il massimo comun divisore di due numeri: l’algoritmo di Euclide. All’inizio abbiamo due numeri x e y di cui vogliamo trovare il massimo comun divisore. Come esempio proviamo con i numeri x = 50 e y = 35. Poi procediamo così:
- Dividiamo x / y e ricordiamo il resto della divisione. Chiamiamo questo resto z. Nel nostro esempio abbiamo 50 / 35, che dà resto z = 15.
- Ora scambiamo le variabili: nella variabile x mettiamo il valore di y e in y mettiamo il valore di z. Il valore originario di x lo buttiamo via. Dopo questo passo otteniamo x = 35 e y = 15.
- Ora controlliamo se y è uguale a zero. Se lo è, il massimo comun divisore è il numero x. Poiché y non è uguale a zero, andiamo avanti e ripetiamo tutto il procedimento dal primo punto.
- Dividiamo di nuovo x / y, cioè 35 / 15, che dà resto z = 5.
- Scambiamo le variabili, quindi otteniamo x = 15 e y = 5. Poiché y non è uguale a zero, andiamo avanti.
- Dividiamo x / y, cioè 15 / 5. Il resto della divisione è z = 0.
- Scambiamo le variabili e otteniamo x = 5 e y = 0.
- A questo punto y = 0 e il nostro algoritmo finisce. Il massimo comun divisore è il numero x = 5.
È importante notare che l’ordine dei numeri non conta. Se scambiassimo i numeri dell’esempio, otterremmo la coppia x = 35 e y = 50. Il procedimento sarebbe lo stesso:
- Dividiamo x / y, cioè 35 / 50, che dà resto z = 35.
- Scambiamo le variabili: x = 50 e y = 35.
- Vediamo che dopo questo passo abbiamo soltanto scambiato tra loro il contenuto delle variabili x e y…
Calcolatore
Questo calcolatore ti calcola il massimo comun divisore.
