Guida per l'insegnante: 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.

Presenta lezione Condividi in Classroom Visualizza pagina studente

Usa questa lezione in classe

Gratis, senza account per gli studenti.

Condividi con gli studenti

Gli studenti aprono la lezione e si esercitano con correzione immediata.

Scheda da stampare

Tutti gli esercizi su carta, con le soluzioni a parte.

Scheda di esercizi Soluzioni

Quiz di classe

10 domande su Fattori e Multipli. Gli studenti partecipano con un nome, tu vedi tutti i punteggi.

Per gli insegnanti

Obiettivi di apprendimento

Scrivere una divisione con resto nella forma $a = q \times b + r$ con $0 \le r < b$
Calcolare il MCD di due numeri con l'algoritmo di Euclide e con il metodo delle sottrazioni successive
Spiegare perché $\text{MCD}(a, b) = \text{MCD}(b, r)$ e collegare l'algoritmo al taglio di un rettangolo in quadrati
Usare il MCD per semplificare frazioni e calcolare $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$
Stabilire se due numeri sono primi tra loro e confrontare l'algoritmo con la scomposizione in fattori primi

Prerequisiti

• Massimo comune divisore (MCD): trovarlo elencando i divisori e con la scomposizione in fattori primi
• Minimo comune multiplo (mcm) e il suo significato
• Scomposizione in fattori primi, numeri primi e numeri composti
• Divisione con resto tra numeri naturali

Spunti di discussione

1. Perché l'algoritmo termina sempre? Che cosa succede ai numeri a ogni passo?
2. Se $d$ divide $48$ e $18$ , perché deve dividere anche $48 - 2 \times 18 = 12$ ?
3. Quando preferiresti la scomposizione in fattori primi e quando l'algoritmo di Euclide?
4. Perché due numeri di Fibonacci vicini come $144$ e $89$ richiedono così tanti passi?
5. In che modo il taglio di un rettangolo in quadrati mostra gli stessi passi delle divisioni?

Idee sbagliate comuni

Il MCD è l'ultimo numero scritto, spesso il resto $0$ o un quoziente

Rimedio: Evidenzia q e r di ogni riga con colori diversi. Cerchia il divisore della riga con resto $0$ e controlla che divida entrambi i numeri iniziali.

Dopo la prima divisione si continua con il numero grande iniziale

Rimedio: Usa l'immagine del rettangolo: una volta tagliati i quadrati, il lato lungo è sparito e resta solo il rettangolo b per r.

L'algoritmo è un trucco che funziona per caso

Rimedio: Mostra con $48$ , $18$ e $12$ che ogni divisore comune di $48$ e $18$ divide $12$ , e ogni divisore comune di $18$ e $12$ divide $48$ . Elenca i due insiemi di divisori comuni: sono uguali.

Idee di differenziazione

Per studenti in difficoltà:

• Cominciare con il metodo delle sottrazioni su coppie piccole come (35, 14) prima di dividere
• Usare rettangoli di carta quadrettata e ritagliare davvero i quadrati
• Fornire una tabella con le colonne a, b, q, r da completare riga per riga

Per studenti a livello:

• Applicare l'algoritmo a coppie di tre e quattro cifre come (1071, 462)
• Semplificare frazioni come $\frac{391}{667}$ con il MCD
• Calcolare mcm con $\frac{a \times b}{\text{MCD}(a, b)}$ e verificarli

Per studenti avanzati:

• Dimostrare in generale che $\text{MCD}(a, b) = \text{MCD}(b, r)$
• Indagare perché numeri di Fibonacci vicini richiedono il maggior numero di passi
• Esplorare l'algoritmo di Euclide esteso: scrivere $\text{MCD}(a, b)$ come $x \times a + y \times b$

Allineamento agli standard

6.NS.B.4 (CCSS.MATH.CONTENT.6.NS.B.4)
Trovare il massimo comune divisore e il minimo comune multiplo di due numeri naturali
6.NS.B.2 (CCSS.MATH.CONTENT.6.NS.B.2)
Dividere con sicurezza numeri a più cifre con l'algoritmo in colonna
MP.7 (CCSS.MATH.PRACTICE.MP7)
Cercare e usare le strutture

Risorse della lezione

visualDal rettangolo ai quadrati
Vista interattiva che taglia un rettangolo a per b nei quadrati più grandi scrivendo ogni riga a = q × b + r
activityQuadrati su carta quadrettata
Gli studenti disegnano un rettangolo 48 per 18 su carta quadrettata e ritagliano con le forbici i quadrati più grandi finché restano solo quadrati uguali
gameGara del MCD
Una squadra usa la scomposizione in fattori primi, l'altra l'algoritmo di Euclide, su coppie come (1071, 462) e (391, 667)
worksheetEsercizi sulle righe di Euclide
Completare quozienti e resti, poi semplificare frazioni e calcolare mcm a partire dal MCD

Contenuto della lezione

Tutto ciò che vedono gli studenti: definizione, esempi, errori comuni, applicazioni. Tocca per aprire.

Definizione

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)

(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.

Esempi svolti

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

18

\frac{48}{6} \times \frac{18}{6} = 8 \times 3

→

24

quadrati di lato

6

lo ricoprono

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

Errori comuni

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

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

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

Dare $0$ o l'ultimo quoziente come MCD

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

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

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

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

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

Prendere $a \times b$ come mcm

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

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

Perché è importante

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.

Applicazioni nel mondo reale

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.

Esempio:

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.

1Provaci tu stesso

Il pavimento di un corridoio misura $168$ cm per $120$ cm. Va coperto con piastrelle quadrate uguali, senza tagli e senza spazi vuoti.

Qual è il lato, in cm, della piastrella quadrata più grande che va bene?

Passo 1: Scrivi l'espressione matematica

Calcola $\text{MCD}(168, 120)$ con l'algoritmo di Euclide:

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.

Esempio:

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.

2Provaci tu stesso

La corona di una bicicletta ha $84$ denti e un pignone piccolo ha $36$ denti. Ora due denti segnati si toccano.

Dopo quanti denti i due denti segnati si toccano di nuovo?

Passo 1: Scrivi l'espressione matematica

Calcola $\text{mcm}(84, 36) = \frac{84 \times 36}{\text{MCD}(84, 36)}$ :

Il formato degli schermi

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

Esempio:

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

3Provaci tu stesso

Un monitor ha $1920$ per $1080$ pixel. Per scrivere il suo formato dividi entrambi i numeri per il loro MCD.

Quanto vale $\text{MCD}(1920, 1080)$ ?

Passo 1: Scrivi l'espressione matematica

Applica l'algoritmo di Euclide a $1920$ e $1080$ :

Punti chiave

1Algoritmo 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$
2Il MCD è l'ultimo resto diverso da zero, cioè il divisore dell'ultima riga
3Funziona perché $\text{MCD}(a, b) = \text{MCD}(b, r)$ : le due coppie hanno gli stessi divisori comuni
4Geometricamente, l'algoritmo taglia un rettangolo $a \times b$ nei quadrati più grandi possibili; il lato dell'ultimo quadrato è il MCD
5Il metodo delle sottrazioni successive toglie più volte il numero più piccolo; la divisione ne è la scorciatoia
6Serve 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$ )

Domande frequenti

Conta da quale numero comincio?

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.

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

Con numeri piccoli come

12

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

462 = 2 \times 3 \times 7 \times 11

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

Allora i due numeri sono primi tra loro (coprimi): non hanno divisori comuni tranne

1

. Due numeri di Fibonacci vicini, come

144

89

, sono sempre primi tra loro, ed è con loro che l'algoritmo richiede più passi rispetto alla loro grandezza.

Posso usarlo con tre numeri?

Sì, due alla volta:

\text{MCD}(a, b, c) = \text{MCD}(\text{MCD}(a, b), c)

. Per esempio

\text{MCD}(840, 1176) = 168

\text{MCD}(168, 1260) = 84

, quindi il MCD dei tre numeri è

84

Glossario

Algoritmo di Euclide: Metodo per il MCD di due numeri: dividere con resto, sostituire la coppia con (divisore, resto) e ripetere finché il resto è $0$
Divisione con resto: La scrittura $a = q \times b + r$ con $0 \le r < b$ , per esempio $1071 = 2 \times 462 + 147$
Quoziente: Il numero $q$ di volte intere in cui $b$ sta in $a$
Resto: Il numero $r$ che avanza dopo la divisione, sempre più piccolo del divisore
Primi tra loro (coprimi): Due numeri il cui MCD è $1$ , come $144$ e $89$
Minimo comune multiplo (mcm): Il più piccolo numero positivo multiplo di entrambi i numeri; $\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$

Scheda formule

Divisione con resto

a = q \times b + r, \quad 0 \le r < b

Una riga dell'algoritmo: $q$ è il quoziente, $r$ il resto

Passo chiave

\text{MCD}(a, b) = \text{MCD}(b, r)

Sostituisci la coppia con (divisore, resto) e ripeti finché $r = 0$

mcm dal MCD

\text{mcm}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}

Moltiplica i numeri e dividi per il loro MCD

Numeri primi tra loro

\text{MCD}(a, b) = 1

I numeri non hanno divisori comuni tranne $1$

Altro su questo argomento

Guida per l'insegnante: Algoritmo di Euclide

Usa questa lezione in classe

Per gli insegnanti

Per studenti in difficoltà:

Per studenti a livello:

Per studenti avanzati:

Contenuto della lezione

Definizione

Esempi svolti

Errori comuni

Perché è importante

Applicazioni nel mondo reale

Piastrellare un pavimento con le piastrelle quadrate più grandi

Ingranaggi e cicli che si ripetono

Il formato degli schermi

Punti chiave

Domande frequenti

Glossario

Scheda formule

Divisione con resto

Passo chiave

mcm dal MCD

Numeri primi tra loro

Altro su questo argomento

Divisori e multipli

Scomposizione in fattori primi

Numeri primi e composti

Massimo Comune Divisore (MCD)