Algoritmo di Euclide

Scomporre in fattori primi due numeri grandi può essere lento. Euclide (negli Elementi, Libro VII) descrive un metodo per il MCD che non richiede alcuna scomposizione: solo divisioni con resto. È uno degli algoritmi più antichi ancora in uso.

Metodo — algoritmo di Euclide (divisioni successive)

Per calcolare $\text{MCD}(a,b)$ con $a\ge b>0$:

1. dividi $a$ per $b$: $a = q\cdot b + r$, con $0\le r < b$;
2. se $r=0$, il MCD è $b$;
3. altrimenti ripeti con $b$ e $r$ al posto di $a$ e $b$.

Il MCD è l’ultimo resto non nullo (cioè l’ultimo divisore).

L’idea è che $\text{MCD}(a,b) = \text{MCD}(b,r)$: ogni divisore comune di $a$ e $b$ divide anche $r = a - q b$, e viceversa. Sostituendo la coppia con una “più piccola” i divisori comuni non cambiano, ma i numeri calano fino a un resto nullo.

Esempio: MCD(48, 32)

$48 = 1\cdot 32 + 16, \qquad 32 = 2\cdot 16 + 0.$

L’ultimo resto non nullo è $16$: dunque $\text{MCD}(48,32)=16$ — lo stesso valore trovato con le scomposizioni.

Esempio: MCD(1071, 462)

$1071 = 2\cdot 462 + 147, \quad 462 = 3\cdot 147 + 21, \quad 147 = 7\cdot 21 + 0.$

Ultimo resto non nullo: $21$. Quindi $\text{MCD}(1071,462)=21$. Provare a scomporre $1071$ e $462$ in fattori primi sarebbe stato molto più laborioso.

La versione "a sottrazioni" di Euclide

Nella forma originale Euclide non usava la divisione ma sottrazioni ripetute: si sottrae il più piccolo dal più grande finché i due diventano uguali, e quel valore è il MCD. La divisione con resto è semplicemente “tante sottrazioni in un colpo solo”.

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Algoritmo di Euclide · Massimo comun divisore (MCD)
Competenze: Scomporre
Persone: Euclide