# Algoritmo esteso di Euclide

In aritmetica e nella programmazione l'algoritmo esteso di Euclide è un'estensione dell'algoritmo di Euclide che calcola non solo il massimo comun divisore (indicato con MCD nel seguito) tra due interi a e b, ma anche i coefficienti x e y dell'identità di Bézout.
L'algoritmo esteso di Euclide è particolarmente utile quando a e b sono interi coprimi: in questo caso x è l'inverso moltiplicativo di a modulo b e y è l'inverso moltiplicativo di b modulo a.
Spesso si indica con l'espressione algoritmo esteso di Euclide anche un altro algoritmo, molto simile al precedente, per il calcolo del massimo comun divisore tra polinomi e i loro coefficienti dell'identità di Bézout.

## Storia

Le prime documentazioni sull'algoritmo risalgono al V-VI secolo a.C., ad opera del matematico indiano Aryabhata. Fu poi riscoperto più volte indipendentemente, ad esempio dal francese Bachet nel 1621 e poi da Eulero intorno al 1731.

## Descrizione

Dati due numeri interi a e b, l'algoritmo di Euclide permette di calcolare le sequenze $q_{1},\ldots ,q_{k}$ dei quozienti e $r_{0},\ldots ,r_{k+1}$ dei resti come segue:
    ${\begin{aligned}q_{1}&=a:b\\&\,\,\,\vdots \\q_{i}&=r_{i-1}:r_{i}\\&\,\,\,\vdots \end{aligned}}$ ${\begin{aligned}r_{0}&=a\\r_{1}&=b\\&\,\,\,\vdots \\r_{i+1}&=r_{i-1}-q_{i}r_{i}\\&\,\,\,\vdots \end{aligned}}$
La sequenza si arresta quando $r_{k+1}=0$ e il MCD corrisponde a $r_{k}$.
L'algoritmo esteso di Euclide procede in modo simile: si considerano due ulteriori sequenze $x_{0},\ldots ,x_{k}$ e $y_{0},\ldots ,y_{k}$ tali che:
${\begin{aligned}x_{0}&=1\\x_{1}&=0\\&\,\,\,\vdots \\x_{i+1}&=x_{i-1}-q_{i}x_{i}\\&\,\,\,\vdots \end{aligned}}$${\begin{aligned}y_{0}&=0\\y_{1}&=1\\&\,\,\,\vdots \\y_{i+1}&=y_{i-1}-q_{i}y_{i}\\&\,\,\,\vdots \end{aligned}}$
Al termine dell'algoritmo, i coefficienti dell'identità di Bézout sono $x_{k}$ e $y_{k}$.

### Esempio

La seguente tabella mostra con un esempio come procede l'algoritmo esteso di Euclide nel caso dei numeri 20 e 7.
Il calcolo procede con una serie di iterazioni i da 0 a k. Si arresta quando è nullo il risultato nella colonna "resto" (alla riga 4 nell'esempio), per cui il massimo comun divisore è 1 e quindi 20 e 7 sono coprimi.
I coefficienti di Bézout sono i risultati nelle ultime due colonne della penultima riga. Infatti, è facile verificare che $ax+by=\operatorname {MCD} (a,b)$ poiché $20\times (-1)+7\times 3=1.$
I risultati delle ultime due colonne nell'ultima riga, 7 e −20, sono rispettivamente, segno a parte, i quozienti di 7 e 20 rispetto al massimo comun divisore 1.
| indice i | quoziente q$_i$$_{-1}$ | resto r$_i$ | x$_i$ | y$_i$ |
| 0 | | 20 | 1 | 0 |
| 1 | | 7 | 0 | 1 |
| 2 | 20 ÷ 7 = 2 | 20 − 2 × 7 = 6 | 1 − 2 × 0 = 1 | 0 − 2 × 1 = −2 |
| 3 | 7 ÷ 6 = 1 | 7 − 1 × 6 = 1 | 0 − 1 × 1 = −1 | 1 − 1 × (−2) = 3 |
| 4 | 6 ÷ 1 = 6 | 6 − 6 × 1 = 0 | 1 − 6 × (−1) = 7 | −2 − 6 × 3 = −20 |
Essendo i due numeri coprimi si ha anche:
* -1 è l'inverso moltiplicativo di 20 modulo 7, cioè $20\times (-1)\equiv 1\mod 7$
* 3 è l'inverso moltiplicativo di 7 modulo 20, cioè $7\times 3\equiv 1\mod 20$ .

## Applicazioni

L'algoritmo di Euclide trova applicazione nella crittografia, in particolare il calcolo dell'inverso moltiplicativo modulare è un passo fondamentale per criptare i messaggi con l'algoritmo a chiave pubblica RSA.