Algoritmo di Euclide e identità di Bézout

Testo

Usa l’algoritmo di Euclide per calcolare $\gcd(1071, 462)$, poi esprimilo come combinazione lineare di $1071$ e $462$.

Soluzione

Applichiamo divisioni successive: $1071 = 2 \cdot 462 + 147,$ $462 = 3 \cdot 147 + 21,$ $147 = 7 \cdot 21 + 0.$ L’ultimo resto non nullo è $\boxed{21}$, quindi $\gcd(1071,462) = 21$.

Risalendo (identità di Bézout): $21 = 462 - 3 \cdot 147 = 462 - 3\,(1071 - 2\cdot 462) = 7 \cdot 462 - 3 \cdot 1071.$ Verifica: $7 \cdot 462 - 3 \cdot 1071 = 3234 - 3213 = 21$. Dunque $21 = (-3)\cdot 1071 + 7 \cdot 462$.

Collegamenti

Argomenti: Numeri e operazioni
Concetti: Combinazione lineare · Massimo comun divisore (MCD)
Competenze: Calcolare
Tipo di esercizio: Calcolo espressioni