L'algoritmo di Euclide è un metodo iterativo per calcolare il Massimo Comune Divisore (MCD) di due numeri interi che consiste nel dividere sequenzialmente il divisore per il resto della divisione precedente, fino all'ottenimento di un resto nullo.
Vogliamo calcolare il Massimo Comune Divisore di $48$ e $18$
$$ \begin{array}{cccccccc} \color{#0b6e99}{48} & = & \color{#d93526}{18} & \cdot & 2 & + & \color{#2d7d32}{12} \\ & & \swarrow & & & \swarrow & \\ \color{#0b6e99}{18} & = & \color{#d93526}{12} & \cdot & 1 & + & \color{#2d7d32}{6} \\ & & \swarrow & & & \swarrow & \\ \color{#0b6e99}{12} & = & \color{#d93526}{6} & \cdot & 2 & + & 0 \end{array} $$
Quando ottengo $0$ come resto l’algoritmo si ferma.
Il MCD è quindi $6$ ovvero l’ultimo resto non nullo.