Algoritmo di Euclide
Calcola il Massimo Comune Divisore fra due numeri mostrando ogni passaggio, con i due metodi: divisioni successive e sottrazioni successive.
Come funziona
Cos'è
Il Massimo Comune Divisore (MCD) di due numeri è il più grande numero che li divide entrambi senza resto. Il MCD di 48 e 18 è 6: entrambi si dividono per 6, e nessun numero più grande di 6 li divide tutti e due.
L'algoritmo di Euclide lo trova senza scomporre in fattori primi. È scritto negli Elementi di Euclide, intorno al 300 a.C., ed è ancora il modo più veloce che conosciamo.
Quando si usa
- Per semplificare una frazione: dividendo numeratore e denominatore per il loro MCD si ottiene la frazione ridotta ai minimi termini. 48/18 → 8/3, perché MCD(48, 18) = 6.
- Per capire se due numeri sono primi fra loro: lo sono quando il loro MCD è 1.
- Per ritagliare pezzi uguali più grandi possibile: da due nastri di 48 cm e 18 cm si ricavano pezzi da 6 cm senza avanzi.
Il metodo
Divisioni successive — è quello veloce. Si basa su un'osservazione: se a = b × q + r, allora ogni divisore comune di a e b è anche divisore di r. Quindi:
- dividi il numero maggiore per il minore e tieni il resto;
- ripeti usando il vecchio divisore come nuovo dividendo, e il resto come nuovo divisore;
- quando il resto è zero, l'ultimo divisore usato è il MCD.
Sottrazioni successive — è la versione originale, più lenta ma più facile da vedere: si sottrae ripetutamente il minore dal maggiore finché i due numeri diventano uguali. Quel valore è il MCD. Serve a capire perché funziona; per calcolare conviene il primo.
I casi limite
- I due numeri sono uguali — il MCD è il numero stesso: si divide per sé stesso con resto zero, e si finisce al primo passaggio.
- A è più piccolo di B — non serve scambiarli: il primo passaggio dà quoziente 0 e resto a, e li scambia da solo. Lo strumento mostra anche questo passaggio, perché è parte dell'algoritmo.
- Uno dei due è 1 — il MCD è 1: i due numeri sono primi fra loro.
- Numeri primi fra loro (per esempio 8 e 15) — si arriva sempre a MCD 1, mai a 0.
- Lo zero — MCD(a, 0) vale a, ma qui non si accetta: con lo zero il metodo delle sottrazioni non finirebbe mai.
Le parole
- Dividendo
- il numero che viene diviso: la a in a = b × q + r.
- Divisore
- il numero per cui si divide: la b.
- Quoziente
- quante volte il divisore sta nel dividendo: la q. Qui è sempre intero, perché si lavora coi resti.
- Resto
- quello che avanza: la r. È sempre più piccolo del divisore, ed è il motivo per cui l'algoritmo finisce sempre.
- Primi fra loro
- due numeri il cui unico divisore comune è 1. Non vuol dire che siano numeri primi: 8 e 15 non lo sono, ma sono primi fra loro.
Il calcolo si automatizza, il ragionamento no
Percorsi personalizzati di Matematica con un docente di ruolo: dai numeri alle regole, per capire il perché e non solo il come.