Algoritmo esteso di Euclide
L'algoritmo esteso di Euclide è una variante dell'algoritmo di Euclide che non si limita a calcolare il massimo comune divisore (MCD) tra due numeri, ma trova anche i coefficienti \( x \) e \( y \) dell'identità di Bézout. \[ a \cdot x + n \cdot y = \text{MCD}(a, n) \]
L’identità di Bézout afferma che, dati due numeri interi \( a \) e \( n \), esistono sempre due interi \( x \) e \( y \) tali che:
\[ a \cdot x + n \cdot y = \text{MCD}(a, n) \]
Se il massimo comune divisore è 1, ovvero se i numeri sono coprimi, l’equazione diventa:
\[ a \cdot x + n \cdot y = 1 \]
Dove \( x \) è proprio l’inverso moltiplicativo di \( a \) modulo \( n \), cioè il numero che soddisfa:
\[ a \cdot x \equiv 1 \pmod{n} \]
Quindi, l'algoritmo esteso di Euclide è particolarmente utile per trovare \( x \), ossia nel calcolo dell’inverso moltiplicativo modulo n, quando due numeri sono coprimi.
A cosa serve? E' usato risolvere equazioni modulari che sono fondamentali in crittografia, teoria dei numeri e informatica. L'algoritmo esteso di Euclide può essere usato anche per risolvere un'equazione diofantea solo in certi casi, in particolare quando l'equazione è lineare e ha una soluzione intera. L’equazione \( ax + by = c \) ha soluzioni intere se e solo se il MCD(a, b) divide c, ovvero: \[ \text{MCD}(a, b) \mid c \] Se questa condizione non è soddisfatta, non esistono soluzioni intere.
Come funziona l’algoritmo esteso di Euclide
Questi sono i principali passaggi dell'algoritmo
- L’algoritmo classico di Euclide
Utilizzo l’algoritmo di Euclide classico per trovare il massimo comune divisore (MCD) tra \( a \) e \( n \) attraverso divisioni successive: \[ n = a \cdot q + r \] Dove \( n \) è il dividendo, \( a \) è il divisore, \( q \) è il quoziente, \( r \) è il resto. Poi continuo il processo sostituendo \( a \) con \( r \) e ripetendo fino a ottenere un resto di 1 che indica che \( a \) e \( n \) sono coprimi. - Espandere l’algoritmo all’indietro
A partire dall’ultima divisione, riscrivo ogni resto in termini di combinazioni lineari di \( a \) e \( n \), lavorando all’indietro fino a esprimere 1 come combinazione di \( a \) e \( n \). Il coefficiente \( x \) che moltiplica \( a \) in questa espressione è l’inverso moltiplicativo modulo \( n \).
Nota. Alla fine mi devo assicurare che il valore \( x \) sia sempre positivo. Se il valore trovato per \( x \) è negativo, lo trasformo in un valore positivo aggiungendo \( n \): \[ x_{\text{pos}} = x + n \]
Un esempio pratico
Esempio 1 (inverso moltiplicativo modulare)
Devo calcolare l’inverso di 23 modulo 40
In altre parole devo trovare un valore intero \( x \) tale che:
\[ 23 \cdot x \equiv 1 \pmod{40} \]
Applico l'algoritmo di Euclide.
Trovo il massimo comune divisore (MCD) tra 23 e 40 eseguendo divisioni successive:
\[ 40 = 23 \cdot 1 + 17 \]
Calcolo il MCD tra il divisore (23) e il resto (17) della precedente divisione.
\[ 23 = 17 \cdot 1 + 6 \]
\[ 17 = 6 \cdot 2 + 5 \]
\[ 6 = 5 \cdot 1 + 1 \]
\[ 5 = 1 \cdot 5 + 0 \]
Poiché il MCD è 1, significa che 23 e 40 sono coprimi e quindi l’inverso moltiplicativo esiste.
Ora riscrivo l’ultimo resto (1) come combinazione di 23 e 40, lavorando a ritroso:
\[ 1 = 6 - 5 \cdot 1 \]
Sostituisco \( 5 = 17 - 6 \cdot 2 \):
\[ 1 = 6 - (17 - 6 \cdot 2) \]
\[ 1 = 6 \cdot 3 - 17 \]
Sostituisco \( 6 = 23 - 17 \cdot 1 \):
\[ 1 = (23 - 17) \cdot 3 - 17 \]
\[ 1 = 23 \cdot 3 - 17 \cdot 4 \]
Sostituisco \( 17 = 40 - 23 \):
\[ 1 = 23 \cdot 3 - (40 - 23) \cdot 4 \]
\[ 1 = 23 \cdot (3 + 4) - 40 \cdot 4 \]
\[ 1 = 23 \cdot 7 + 40 \cdot (-4) \]
Il coefficiente di 23 è 7, quindi l'inverso moltiplicativo di 23 è 7.
\[ 23^{-1} \equiv 7 \pmod{40} \]
Nota. Verifico che \( 23 \cdot 7 \equiv 1 \pmod{40} \): $$ 23 \cdot 7 = 161 \equiv 1 \mod 40 $$ Il risultato è corretto.
Esempio 2 (equazione diofantea)
Considero l'equazione diofantea
\[ 23x + 40y = 7 \]
Il massimo comune divisore (MCD) di 23 e 40 è 1
\[ \text{MCD}(23, 40) = 1 \]
Poiché \( 1 \mid 7 \), ossia 1 è un divisore di 7, so che ci sono soluzioni intere.
Applico l’algoritmo esteso di Euclide e ottengo la soluzione:
\[ 40 = 23 \cdot 1 + 17 \]
\[ 23 = 17 \cdot 1 + 6 \]
\[ 17 = 6 \cdot 2 + 5 \]
\[ 6 = 5 \cdot 1 + 1 \]
\[ 5 = 1 \cdot 5 + 0 \]
Ripercorro all'indietro i passaggi prendendo il resto uguale a 1.
\[ 6 = 5 \cdot 1 + 1 \]
Utilizzo questo passaggio per scrivere 1 come combinazione lineare
\[ 1 = 6 - 5 \]
A questo punto devo cercare di ricondurla a una combinazione lineare di 23 e 40.
Dai passaggi precedente so già che \( 5 = 17 - 6 \cdot 2 \)
\[ 1 = 6 - (17 - 6 \cdot 2) \]
\[ 1 = 6 - 17 + 6 \cdot 2 \]
\[ 1 = 6 \cdot 3 - 17 \]
Sapendo che \( 6 = 23 - 17 \)
\[ 1 = (23 - 17) \cdot 3 - 17 \]
\[ 1 = 23 \cdot 3 - 17 \cdot 3 - 17 \]
\[ 1 = 23 \cdot 3 - 17 \cdot 4 \]
So anche che \( 17 = 40 - 23 \cdot 1 \)
\[ 1 = 23 \cdot 3 - (40 - 23) \cdot 4 \]
\[ 1 = 23 \cdot 3 - 40 \cdot 4 + 23 \cdot 4 \]
\[ 1 = - 40 \cdot 4 + 23 \cdot 7 \]
Quindi, l'equazione diofantea \( 23x + 40y = 1 \) ha come soluzione particolare $ x= 7 $ e $ y=-4 $.
Poiché voglio risolvere l'equazione iniziale \( 23x + 40y = 7 \), moltiplico entrambe le soluzioni per 7.
$$ x_0= x \cdot 7 = 7 \cdot 7 = 49 $$
$$ y_0= y \cdot 7 = -4 \cdot 7 = -28 $$
Questa è la soluzione particolare dell'equazione iniziale: $ x_0=49 $ e $ y_0=-28 $.
\[ 23x_0 + 40y_0 = 7 \]
\[ 23 \cdot 49 + 40 \cdot (-28) = 7 \]
\[ 1127 - 1120 = 7 \]
\[ 7 = 7 \]
La soluzione generale di un'equazione diofantea lineare ha la forma:
\[ x = x_0 + k \cdot \frac{b}{\text{MCD}(a,b)} \]
\[ y = y_0 - k \cdot \frac{a}{\text{MCD}(a,b)} \]
Dove \( k \) è un numero intero qualsiasi.
Sostituendo i valori $ x_0 =49 $ e $ y_0 =-28 $ ottengo la soluzione generale dell'equazione \( 23x + 40y = 7 \)
\[ x = 49 + k \cdot 40 \]
\[ y = -28 - k \cdot 23 \]
Dove \( k \) è un qualsiasi numero intero.
Questo mi permette di ottenere infinite soluzioni dell'equazione variando il valore di \( k \) (ad esempio, \( k = 0, 1, -1, 2, -2, ... \)).
Nota. Ovviamente l'algoritmo esteso di Euclide si può usare solo se il MCD(a,b) divide il termine noto c dell'equazione diofantea. Ad esempio, Considero l'equazione diofantea \[ 6x + 9y = 5 \] Qui, \( \text{MCD}(6, 9) = 3 \), ma 3 non divide 5. Quindi, l'equazione non ha soluzioni intere.
E così via.
