L'algoritmo di Euclide esteso consiste nel ripercorrere a ritroso i passaggi delle divisioni euclidee per esprimere il MCD come somma algebrica dei due numeri di partenza moltiplicati per coefficienti interi (Identità di Bézout: $ax+by=MCD(a,b)$).
Vogliamo calcolare il Massimo Comune Divisore di $48$ e $18$.
Voglio trovare $x,y\in \Z$ tale per cui $48 \cdot a+18\cdot b = MCD(48,18)$
STEP 1: Trovo il MCD di $48$ e $18$ tramite l’algoritmo Euclideo
$$ \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} $$
STEP 2: Riscrivo l’equazione ottenuta ad ogni passaggio con il resto al primo membro.
$$ \begin{align*} 12 &= 48 - 18 \cdot 2 \\ 6 &= 18 - 12 \cdot 1 \end{align*} $$
STEP 3: Partendo dall’ultima uguaglianza ($6= 18-12\cdot 1$), sostituisco il $12$ con l’espressione superiore ($48-18\cdot 2$)
$$ \begin{align*}6= 18 +(-1)(48-18\cdot2)= \\ = 18 -48+18\cdot 2= \\=18\cdot 3 -48=\end{align*} $$
(Ho eseguito il calcolo e raggruppato il $18$)
(In questo caso ho già finito perché ho solo 2 uguaglianze)
STEP 4: Identità di Bézout
$$ 48\cdot (-1) + 18 \cdot(3)=6 $$