L’algoritmo di Euclide è un metodo semplice ed efficace per trovare il  Massimo Comune Divisore (MCD) di due numeri. Il MCD è il numero più grande che divide entrambi i numeri senza lasciare resto.

Come funziona l’algoritmo

1. Si divide il numero più grande per il più piccolo.
2. Si prende il resto della divisione.
3. Si sostituisce il numero maggiore con il numero minore e il numero minore con il resto.
4. Si ripete il processo fino a quando il resto è 0.
5. Il numero rimasto sarà il MCD.

Esempio 1: MCD tra 48 e 18

1. Dividiamo 48 per 18: 48÷18=2 con resto 12
2. Ora sostituiamo: il numero maggiore diventa 18 e il numero minore diventa 12.
3. Dividiamo 18 per 12: 18÷12=1 con resto 6
4. Sostituiamo di nuovo: il numero maggiore diventa 12 e il numero minore diventa 6.
5. Dividiamo 12 per 6: 12÷6=2 con resto 0
6. Quando il resto è 0, il MCD è il numero rimasto, cioè 6.

Esempio 2: MCD tra 56 e 42

1. Dividiamo 56 per 42: 56÷42=1 con resto 14
2. Sostituiamo: il numero maggiore diventa 42 e il numero minore diventa 14.
3. Dividiamo 42 per 14: 42÷14=3 con resto 0
4. Quando il resto è 0, il MCD è il numero rimasto, cioè 14.

Perché funziona?

L’algoritmo si basa sul fatto che i divisori comuni di due numeri non cambiano quando sostituiamo il numero maggiore con il resto della loro divisione.

Quando si usa?

• Per semplificare frazioni: il MCD permette di ridurre le frazioni ai minimi termini.
• Per problemi che richiedono di dividere qualcosa in parti uguali senza lasciare resto.

Prova tu!

Trova il MCD di:

• 84 e 30
• 120 e 45

Scrivi tutti i passaggi e verifica se il risultato è corretto!