L'Algoritmo di Euclide

Il Massimo Comun Divisore (MCD) di due numeri è il più grande numero che divide entrambi i numeri. Ad esempio, il MCD di 30 e 45 è 15, poiché 15 è il più grande numero che divide sia 30 che 45.

Abbiamo visto nella lezione precedente che un metodo per calcolare il MCD di due numeri naturali è quello di scomporli in fattori primi e poi moltiplicare i fattori comuni, elevati alla potenza minima con cui compaiono in entrambe le scomposizioni.

Tuttavia, esiste un altro metodo molto più veloce e antico per il calcolo del MCD, che prende il nome di Algoritmo di Euclide. Questo algoritmo è stato scoperto dal matematico greco Euclide nel III secolo a.C che lo descrisse nella sua opera: Elementi, ed è ancora oggi uno dei metodi più utilizzati per calcolare il MCD.

Teorema della divisibilità della differenza

Prima di poter descrivere l'algoritmo e capirne il funzionamento, dobbiamo introdurre un teorema fondamentale che ci permette di calcolare il MCD in modo più semplice. Tale teorema afferma che:

Definizione

Teorema della divisibilità della differenza

Dati due numeri naturali:

a, b \in \mathbb{N}

tali che $a \geq b$ , se esiste un numero naturale $d \in \mathbb{N}$ che divide sia $a$ che $b$ , allora anche la differenza $a - b$ è divisibile per $d$ .

Dimostrazione

Dimostriamo il teorema.

Sappiamo che:

a, b, d \in \mathbb{N}

Inoltre sappiamo che $d$ divide sia $a$ che $b$ .

Pertanto, dato che $d$ divide $a$ , possiamo scrivere:

a : d = q_1 \quad \rightarrow \quad a = d \cdot q_1

Dove $q_1$ è il quoziente della divisione tra $a$ e $d$ . Inoltre, sappiamo che $q_1$ è un numero naturale ed è maggiore o uguale a $1$ .

Allo stesso modo, dato che $d$ divide $b$ , possiamo scrivere:

b : d = q_2 \quad \rightarrow \quad b = d \cdot q_2

Dove $q_2$ è il quoziente della divisione tra $b$ e $d$ . Anche in questo caso, sappiamo che $q_2$ è un numero naturale ed è maggiore o uguale a $1$ .

Ora, consideriamo la differenza $a - b$ :

a - b = d \cdot q_1 - d \cdot q_2

Applicando la proprietà distributiva all'inverso, otteniamo:

a - b = d \cdot (q_1 - q_2)

Se consideriamo che $q_1$ e $q_2$ sono numeri naturali, anche la differenza $q_1 - q_2$ è un numero naturale. Pertanto, possiamo concludere che:

d \cdot (q_1 - q_2) \quad \text{è un numero naturale} è

quindi $d$ divide anche la differenza $a - b$ . Infatti:

(a - b) : d = q_1 - q_2

Vediamo ora un esempio pratico per capire meglio il teorema.

Supponiamo di avere i numeri $a = 45$ e $b = 30$ . Un numero naturale $d$ che divide sia $a$ che $b$ è $5$ . Infatti:

45 : 5 = 9 \quad \text{e} \quad 30 : 5 = 6

Quindi, $5$ divide sia $45$ che $30$ . Ora calcoliamo la differenza tra i due numeri:

a - b = 45 - 30 = 15

Ora verifichiamo se $5$ divide anche la differenza $15$ :

15 : 5 = 3

Quindi, $5$ divide anche la differenza $15$ .

Un'importante conseguenza di questo teorema, che sfrutteremo in questa lezione, è:

Definizione

MCD e la differenza tra due numeri

Dati due numeri naturali $a$ e $b$ , tali che $a > b$ , se essi hanno un divisore in comune $d$ , allora anche la differenza $a - b$ ha lo stesso divisore in comune $d$ .

Pertanto ne consegue che:

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

Un'altra proprietà del MCD che sfrutteremo è:

Definizione

MCD di un numero e se stesso

Dato un numero naturale $a$ , il MCD di $a$ e se stesso è uguale a $a$ :

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

MCD con Sottrazioni Successive

A partire dal teorema della divisibilità della differenza, possiamo escogitare un primo metodo per calcolare il MCD di due numeri naturali che prende il nome di MCD con Sottrazioni Successive. Non si tratta ancora dell'algoritmo di Euclide, ma è un metodo che sfrutta il teorema della divisibilità della differenza per calcolare il MCD in modo più semplice.

Per capire, consideriamo due numeri naturali $a$ e $b$ , tali che $a > b$ . Calcoliamo la differenza tra i due numeri $a - b$ .

Sappiamo che se $a$ e $b$ hanno un divisore in comune $d$ , allora anche la differenza $a - b$ ha lo stesso divisore in comune $d$ . Pertanto, ammesso che abbiano un divisore in comune, si possono verificare due casi:

$a - b = b$ . La conseguenza è che $b$ è il MCD di $a$ e $b$ .
$a - b > b$ . In questo caso, consideriamo allora la differenza tra $a - b$ e $b$ . Essi avranno sicuramente un divisore in comune, quindi possiamo riapplicare il procedimento.

Per cui, il metodo consiste in:

Definizione

MCD con Sottrazioni Successive

Dati due numeri naturali $a$ e $b$ , tali che $a > b$ , per calcolare il MCD tra i due numeri, si procede come segue:

Si calcola la differenza tra i due numeri $d = a - b$ ;
Se $d = b$ , allora il MCD è $b$ e il procedimento termina;
Se $d \neq b$ , si effettuano i seguenti passi:
- $a = max(d, b)$ ; ossia si pone $a$ uguale al numero maggiore tra $d$ e $b$ ;
- $b = min(d, b)$ ; ossia si pone $b$ uguale al numero minore tra $d$ e $b$ ;
- Si torna al passo 1.

Chiariamo con un esempio pratico.

Calcoliamo il MCD tra $a = 120$ e $b = 36$ con il metodo delle sottrazioni successive:

Calcoliamo la differenza tra i due numeri:

$d = 120 - 36 = 84$
$d \neq b$ , quindi procediamo con i passi successivi:
- $a = max(84, 36) = 84$ ;
- $b = min(84, 36) = 36$ ;
- Rieseguiamo il procedimento:
Calcoliamo la differenza tra i due numeri:

$d = 84 - 36 = 48$
$d \neq b$ , quindi procediamo con i passi successivi:
- $a = max(48, 36) = 48$ ;
- $b = min(48, 36) = 36$ ;
- Rieseguiamo il procedimento:
Calcoliamo la differenza tra i due numeri:

$d = 48 - 36 = 12$
$d \neq b$ , quindi procediamo con i passi successivi:
- $a = max(12, 36) = 36$ ;
- $b = min(12, 36) = 12$ ;
- Rieseguiamo il procedimento:
Calcoliamo la differenza tra i due numeri:

$d = 36 - 12 = 24$
$d \neq b$ , quindi procediamo con i passi successivi:
- $a = max(24, 12) = 24$ ;
- $b = min(24, 12) = 12$ ;
- Rieseguiamo il procedimento:
Calcoliamo la differenza tra i due numeri:

$d = 24 - 12 = 12$
$d = b$ , quindi il MCD è $b = 12$ e il procedimento termina.

L'intero procedimento dell'esempio è riassunto nella figura qui sotto:

**Figura 1:** Esempio di MCD per Sottrazioni Successive

Osservando bene il procedimento, quello che abbiamo fatto è stato applicare la seguente catena di uguaglianze:

\text{MCD}(120, 36) = \text{MCD}(84, 36) = \text{MCD}(48, 12) = \text{MCD}(24, 12) = \text{MCD}(12, 12) = 12

Facciamo due importanti osservazioni sull'esempio:

Abbiamo eseguito tre sottrazioni successive con 36 come minuendo:

$(((120 - 36) - 36) - 36) = 12$
Analogamente, abbiamo eseguito due sottrazioni successive con 12 come minuendo:

$((36 - 12) - 12) = 12$

Nel primo caso si trattava sostanzialmente di dividere 120 per 36 e prenderne il resto che è 12. Nel secondo caso, si trattava di dividere 36 per 12 e prenderne il resto che è 0.

Sfruttando questa osservazione possiamo semplificare il procedimento e arrivare a un metodo più veloce per calcolare il MCD.

Infatti, possiamo enunciare il seguente teorema:

Definizione

MCD e Resto della Divisione

Dati due numeri naturali $a$ e $b$ , tali che $a > b$ , se essi hanno un divisore in comune $d$ , allora anche il resto della divisione tra $a$ e $b$ ha lo stesso divisore in comune $d$ .

Possiamo verificare facilmente che il teorema è vero con un esempio:

Prendiamo di nuovo i numeri $a = 120$ e $b = 36$ . Un numero naturale $d$ che divide sia $a$ che $b$ è $4$ .

Dividiamo $a$ per $b$ :

120 : 36 = 3 \quad \text{e} \quad 120 - (3 \cdot 36) = 12

Quindi, il resto della divisione tra $120$ e $36$ è $12$ . Ora verifichiamo se $4$ divide anche il resto $12$ :

12 : 4 = 3

Quindi, $4$ divide anche il resto $12$ .

Sfruttando questo teorema, e le osservazioni fatte in precedenza, arriviamo all'algoritmo di Euclide che sfrutta il resto della divisione tra i due numeri per calcolare il MCD in modo più veloce.

Algoritmo di Euclide

L'Algoritmo di Euclide sfrutta le divisioni successive per calcolare il MCD di due numeri naturali:

Definizione

Algoritmo di Euclide

Dati due numeri naturali $a$ e $b$ , tali che $a > b$ , per calcolare il MCD tra i due numeri, si procede come segue:

Si calcola il resto della divisione tra $a$ e $b$ :

$r = \text{resto}(a : b)$
Se $r = 0$ , allora il MCD è $b$ e il procedimento termina;
Se $r \neq 0$ , si effettuano i seguenti passi:
- $a = b$ ;
- $b = r$ ;
- Si torna al passo 1.

Nel caso in cui $a < b$ , si invertono i due numeri e si procede come sopra.

Applichiamo ora l'algoritmo di Euclide all'esempio precedente per calcolare il MCD tra $120$ e $36$ :

Calcoliamo il resto della divisione tra $120$ e $36$ :

$120 : 36 = 3 \quad \text{con resto} \quad 12$
$r \neq 0$ , quindi procediamo con i passi successivi:
- $a = 36$ ;
- $b = 12$ ;
- Rieseguiamo il procedimento:
Calcoliamo il resto della divisione tra $36$ e $12$ :

$36 : 12 = 3 \quad \text{con resto} \quad 0$
$r = 0$ , quindi il MCD è $b = 12$ e il procedimento termina.

Come si può notare, l'algoritmo di Euclide è molto più veloce rispetto al metodo delle sottrazioni successive. Infatti, in questo caso abbiamo eseguito solo due divisioni invece di cinque sottrazioni.

Anche in questo caso, l'intero procedimento sfrutta la seguente catena di uguaglianze:

\text{MCD}(120, 36) = \text{MCD}(36, 12) = \text{MCD}(12, 12) = 12

Algoritmo di Euclide in Pseudocodice

Proviamo ad implementare l'algoritmo di Euclide in pseudocodice. L'algoritmo è molto semplice e può essere implementato in qualsiasi linguaggio di programmazione. Ecco un esempio di implementazione in pseudocodice:

L'algoritmo è suddiviso in due parti:

La prima parte controlla se effettivamente il primo dei due numeri, $a$ , è maggiore del secondo, $b$ . Se non lo è, i due numeri vengono scambiati;
La seconda parte è l'algoritmo di Euclide vero e proprio. Attraverso un ciclo while, si calcola il resto della divisione tra $a$ e $b$ e si verifica se il resto è uguale a zero. Se lo è, il MCD è $b$ e il ciclo termina. Se non lo è, i valori di $a$ e $b$ vengono aggiornati e il ciclo continua fino a quando non si trova il MCD.

Lezione Precedente Indice del capitolo