Algoritmo di Euclide

L'**algoritmo di Euclide** è un modo veloce per trovare il **massimo comune divisore (MCD)** di due numeri naturali, senza elencare i divisori né costruire alberi dei fattori. Dividi il numero più grande $a$ per il numero più piccolo $b$ e scrivi il risultato come **divisione con resto**: $$a = q \times b + r, \quad 0 \le r < b$$ Qui $q$ è il **quoziente** e $r$ è il **resto**. Poi **sostituisci la coppia $(a, b)$ con $(b, r)$** e dividi di nuovo. Ripeti finché il resto è $0$. L'**ultimo resto diverso da zero** (il divisore dell'ultima riga) è il MCD. **Esempio:** $\text{MCD}(48, 18)$ - $48 = 2 \times 18 + 12$ - $18 = 1 \times 12 + 6$ - $12 = 2 \times 6 + 0$ Il resto è $0$, quindi $\text{MCD}(48, 18) = 6$. **Perché funziona:** se un numero $d$ divide sia $a$ sia $b$, divide anche $r = a - q \times b$. E se $d$ divide sia $b$ sia $r$, divide anche $a = q \times b + r$. Quindi le coppie $(a, b)$ e $(b, r)$ hanno esattamente gli stessi divisori comuni, e perciò lo stesso MCD: $$\text{MCD}(a, b) = \text{MCD}(b, r)$$ I numeri diventano più piccoli a ogni passo, quindi l'algoritmo termina sempre.

L'immagine geometrica: quadrati in un rettangolo 48 per 18

Un rettangolo misura $48$ per $18$. Taglia ogni volta i quadrati più grandi possibili. Qual è il lato dei quadrati che alla fine entrano esattamente?

Taglia quadrati di lato 18 dal lato lungo: Entrano due quadrati $18 \times 18$ e avanza $12$: $48 = 2 \times 18 + 12$ = Rettangolo rimasto $18 \times 12$

Taglia quadrati di lato 12 dal resto: Entra un quadrato $12 \times 12$ e avanza $6$: $18 = 1 \times 12 + 6$ = Rettangolo rimasto $12 \times 6$

Taglia quadrati di lato 6: Entrano esattamente due quadrati $6 \times 6$: $12 = 2 \times 6 + 0$ = Non avanza nulla

Ricopri tutto il rettangolo con l'ultimo quadrato: $6$ divide $48$ e $18$: $\frac{48}{6} \times \frac{18}{6} = 8 \times 3$ = $24$ quadrati di lato $6$ lo ricoprono

Answer: I quadrati di lato $6$ entrano esattamente, quindi $\text{MCD}(48, 18) = 6$. Ogni taglio è una riga dell'algoritmo.

Il metodo delle sottrazioni successive

Calcola $\text{MCD}(35, 14)$ usando solo sottrazioni: sottrai sempre il numero più piccolo dal più grande.

Sottrai 14 da 35: $35 - 14 = 21$ = Nuova coppia $(21, 14)$

Sottrai di nuovo 14: $21 - 14 = 7$ = Nuova coppia $(14, 7)$

Ora 7 è più piccolo: sottrai 7: $14 - 7 = 7$ = Nuova coppia $(7, 7)$

Sottrai un'ultima volta: $7 - 7 = 0$ = I numeri si fermano a $7$

Answer: $\text{MCD}(35, 14) = 7$. Sottrarre $14$ due volte equivale a una sola divisione: $35 = 2 \times 14 + 7$. La divisione è solo una scorciatoia per tante sottrazioni.

Un classico: il MCD di 1071 e 462

Calcola $\text{MCD}(1071, 462)$ con l'algoritmo di Euclide.

Dividi 1071 per 462: $462 \times 2 = 924$ e $1071 - 924 = 147$ = $1071 = 2 \times 462 + 147$

Sostituisci la coppia con (462, 147) e dividi: $147 \times 3 = 441$ e $462 - 441 = 21$ = $462 = 3 \times 147 + 21$

Sostituisci la coppia con (147, 21) e dividi: $21 \times 7 = 147$, non avanza nulla = $147 = 7 \times 21 + 0$

Leggi l'ultimo resto diverso da zero: Il resto è diventato $0$ dividendo per $21$ = $\text{MCD}(1071, 462) = 21$

Answer: $\text{MCD}(1071, 462) = 21$. Verifica: $1071 = 21 \times 51$ e $462 = 21 \times 22$.

Semplificare una frazione difficile

Riduci $\frac{391}{667}$ ai minimi termini.

Dividi 667 per 391: $667 = 1 \times 391 + 276$ = Resto $276$

Dividi 391 per 276: $391 = 1 \times 276 + 115$ = Resto $115$

Dividi 276 per 115: $276 = 2 \times 115 + 46$ = Resto $46$

Dividi 115 per 46, poi 46 per 23: $115 = 2 \times 46 + 23$ e $46 = 2 \times 23 + 0$ = $\text{MCD}(391, 667) = 23$

Dividi numeratore e denominatore per 23: $\frac{391 \div 23}{667 \div 23} = \frac{17}{29}$ = $\frac{17}{29}$

Answer: $\frac{391}{667} = \frac{17}{29}$. Poiché $17$ e $29$ sono entrambi primi, la frazione non si può semplificare oltre.

Il mcm a partire dal MCD

Calcola $\text{mcm}(84, 120)$ con l'algoritmo di Euclide.

Dividi 120 per 84: $120 = 1 \times 84 + 36$ = Resto $36$

Dividi 84 per 36: $84 = 2 \times 36 + 12$ = Resto $12$

Dividi 36 per 12: $36 = 3 \times 12 + 0$ = $\text{MCD}(84, 120) = 12$

Usa mcm = a × b ÷ MCD: $\frac{84 \times 120}{12} = \frac{10080}{12}$ = $840$

Verifica: $840 \div 84 = 10$ e $840 \div 120 = 7$ = Entrambi dividono $840$

Answer: $\text{mcm}(84, 120) = 840$.

L'algoritmo di Euclide ha più di 2300 anni (Euclide lo scrisse intorno al 300 a.C.) ed è ancora uno degli algoritmi più usati al mondo: - **Numeri grandi**: scomporre $1071$ o $391$ in fattori primi è lento, ma tre o quattro divisioni danno subito il MCD. Con numeri di centinaia di cifre la scomposizione è praticamente impossibile, mentre l'algoritmo di Euclide finisce al massimo in qualche migliaio di passi veloci. - **Frazioni**: per semplificare $\frac{391}{667}$ ti serve $\text{MCD}(391, 667) = 23$, difficile da vedere scomponendo ma rapido con l'algoritmo. - **mcm**: appena conosci il MCD, $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$, quindi un solo algoritmo ti dà entrambi. - **Piastrelle, ingranaggi e schermi**: la piastrella quadrata più grande per un pavimento, quando due ingranaggi tornano allineati e perché uno schermo $1920 \times 1080$ è $16:9$ si riducono tutti al MCD. - **Sicurezza su internet**: sistemi di crittografia come RSA usano una versione estesa di questo algoritmo ogni volta che apri un sito sicuro.

Mistake: Tenere il vecchio numero grande: dopo $48 = 2 \times 18 + 12$, continuare con $48$ e $12$

Why: L'algoritmo funziona perché $\text{MCD}(a, b) = \text{MCD}(b, r)$. Il numero $a$ non serve più dopo la prima divisione.

Correct: La coppia successiva è $(18, 12)$: il vecchio divisore e il resto. Quindi $18 = 1 \times 12 + 6$.

Mistake: Dare $0$ o l'ultimo quoziente come MCD

Why: L'ultima riga ha resto $0$, e questo dice solo che bisogna fermarsi. Il quoziente conta quanti quadrati entrano, non è un divisore comune.

Correct: Il MCD è l'ultimo resto diverso da zero, cioè il divisore dell'ultima riga. In $12 = 2 \times 6 + 0$ è $6$.

Mistake: Scrivere un resto troppo grande, come $1071 = 1 \times 462 + 609$

Why: L'uguaglianza è vera, ma $609 > 462$, quindi $462$ ci sta ancora una volta. Il resto deve essere più piccolo del divisore.

Correct: Prendi il quoziente più grande possibile: $1071 = 2 \times 462 + 147$ con $147 < 462$.

Mistake: Prendere $a \times b$ come mcm

Why: $a \times b$ è sempre un multiplo comune, ma di solito non il minimo: $84 \times 120 = 10080$ conta due volte il divisore comune $12$.

Correct: Dividi per il MCD: $\text{mcm}(84, 120) = \frac{84 \times 120}{12} = 840$.

Piastrellare un pavimento con le piastrelle quadrate più grandi

Un piastrellista vuole coprire un pavimento rettangolare con piastrelle quadrate uguali senza tagliarne nessuna. Il lato più grande possibile è il MCD delle due misure.

Un pannello di $48$ cm per $18$ cm è coperto esattamente da quadrati di $6$ cm: $\text{MCD}(48, 18) = 6$, cioè $8 \times 3 = 24$ piastrelle.

Ingranaggi e cicli che si ripetono

Quando due ruote dentate girano insieme, gli stessi due denti si incontrano di nuovo dopo un numero di denti pari al mcm dei numeri di denti. L'algoritmo di Euclide dà il MCD, e da lì si ricava il mcm.

Ruote con $18$ e $48$ denti: $\text{MCD} = 6$, quindi gli stessi denti si incontrano di nuovo dopo $\frac{18 \times 48}{6} = 144$ denti.

Il formato degli schermi

Una risoluzione come $1920 \times 1080$ diventa un formato dividendo entrambi i numeri per il loro MCD.

$1280 \times 1024$: $\text{MCD}(1280, 1024) = 256$, quindi il formato è $5:4$.

Algoritmo di Euclide: dividi $a$ per $b$ come $a = q \times b + r$ con $0 \le r < b$, poi sostituisci $(a, b)$ con $(b, r)$ finché il resto è $0$

Il MCD è l'ultimo resto diverso da zero, cioè il divisore dell'ultima riga

Funziona perché $\text{MCD}(a, b) = \text{MCD}(b, r)$: le due coppie hanno gli stessi divisori comuni

Geometricamente, l'algoritmo taglia un rettangolo $a \times b$ nei quadrati più grandi possibili; il lato dell'ultimo quadrato è il MCD

Il metodo delle sottrazioni successive toglie più volte il numero più piccolo; la divisione ne è la scorciatoia

Serve per semplificare frazioni, per calcolare $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$ e per capire se due numeri sono primi tra loro (MCD $= 1$)

Q: Conta da quale numero comincio?

A: No. Se cominci con il numero più piccolo davanti, la prima riga è del tipo $18 = 0 \times 48 + 18$, che scambia soltanto i due numeri. Cominciare dal più grande ti risparmia quel passo.

Q: L'algoritmo di Euclide è più veloce della scomposizione in fattori primi?

A: Con numeri piccoli come $12$ e $18$ entrambi i metodi sono veloci. Con numeri grandi sì, di gran lunga: non devi trovare nessun numero primo. $\text{MCD}(1071, 462)$ richiede tre divisioni, mentre la scomposizione richiede $1071 = 3^2 \times 7 \times 17$ e $462 = 2 \times 3 \times 7 \times 11$.

Q: Che cosa significa se l'algoritmo finisce con MCD 1?

A: Allora i due numeri sono **primi tra loro** (coprimi): non hanno divisori comuni tranne $1$. Due numeri di Fibonacci vicini, come $144$ e $89$, sono sempre primi tra loro, ed è con loro che l'algoritmo richiede più passi rispetto alla loro grandezza.

Q: Posso usarlo con tre numeri?

A: Sì, due alla volta: $\text{MCD}(a, b, c) = \text{MCD}(\text{MCD}(a, b), c)$. Per esempio $\text{MCD}(840, 1176) = 168$ e $\text{MCD}(168, 1260) = 84$, quindi il MCD dei tre numeri è $84$.

Esci dalla presentazione

Algoritmo di Euclide

1 / 14

Teoria dei Numeri / Fattori e Multipli

Algoritmo di Euclide

Trova il massimo comune divisore di due numeri con divisioni successive con resto e usalo per semplificare frazioni e calcolare il mcm.

Avanzato25 min

Usa i tasti freccia o la barra spaziatrice per navigare