Algoritmo di Euclide

L'algoritmo di Euclide è un algoritmo per trovare il massimo comune divisore (indicato di seguito con MCD) tra due numeri interi. È uno degli algoritmi più antichi conosciuti, essendo presente negli Elementi di Euclide^[1] intorno al 300 a.C.; tuttavia, probabilmente l'algoritmo non è stato scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. L'algoritmo non richiede la fattorizzazione dei due interi.

Dati due numeri naturali ${\displaystyle a}$ e ${\displaystyle b}$, l'algoritmo prevede che si controlli se ${\displaystyle b}$ è zero. Se lo è, ${\displaystyle a}$ è il MCD. Se non lo è, si deve dividere ${\displaystyle {\frac {a}{b}}}$ e definire ${\displaystyle r}$ come il resto della divisione (operazione indicata con "a modulo b" più sotto). Se ${\displaystyle r=0}$ allora si può affermare che ${\displaystyle b}$ è il MCD cercato, altrimenti occorre assegnare ${\displaystyle a'=b}$ e ${\displaystyle b'=r}$ e ripetere nuovamente la divisione. L'algoritmo può essere espresso in modo naturale utilizzando la ricorsione in coda.

Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo, si possono determinare due interi ${\displaystyle p}$ e ${\displaystyle q}$ tali che ${\displaystyle ap+bq=MCD(a,b)}$. Questo è noto con il nome di algoritmo di Euclide esteso.

Questi algoritmi possono essere usati, oltre che con i numeri interi, in ogni contesto in cui è possibile eseguire la divisione col resto. Ad esempio, l'algoritmo funziona per i polinomi ad una indeterminata su un campo K, o polinomi omogenei a due indeterminate su un campo, o gli interi gaussiani. Un oggetto algebrico in cui è possibile eseguire la divisione col resto è chiamato anello euclideo.

Euclide originariamente formulò il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il più corto dal più lungo. Questo procedimento è equivalente alla implementazione seguente, che è molto meno efficiente del metodo indicato sopra.