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

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

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$ e $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$ e $\text{MCD}(168, 1260) = 84$, quindi il MCD dei tre numeri è $84$.

Risorse per insegnanti

Algoritmo di Euclide

Q: 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.

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

Avanzato25 minLezione

Condividi in Classroom

Scheda da stampare

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.

Prova subito

Nell'algoritmo di Euclide scrivi

a = q \times b + r

con

0 \le r < b

. Quale coppia dividi dopo?

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

Visuale interattivo

I quadrati più grandi in un rettangolo: scegli una coppia

Primo numeroSecondo numero

Rettangolo 1071 × 462

Premi Passo successivo per tagliare i quadrati più grandi che ci stanno.

Tocca a te: scrivi il quoziente e il resto di ogni riga

Primo numeroSecondo numero

Rettangolo 168 × 120

Quante volte sta 120 in 168, e quanto avanza?

168 =× 120 +

Sandbox interattivo

Calcolatrice di espressioni

Prova questi:

Cronologia

Ancora nessun calcolo

Esercizi pratici

18 esercizi

Problema 1 di 18

Facile

Nell'algoritmo di Euclide scrivi

a = q \times b + r

con

0 \le r < b

. Quale coppia dividi dopo?

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

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.

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$

Sfida di oggiUn problema, tre tentativi

Altro su questo argomento

Definizione

Esempi svolti

Errori comuni

Visuale interattivo

Sandbox interattivo

Calcolatrice di espressioni

Cronologia

Esercizi pratici

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)