Algoritmo euclideo esteso

L’algoritmo euclideo esteso è un algoritmo per calcolare gli interi xxx e yyy tali che

ax+by=gcd(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b)

date aaa e bbb.

L’esistenza di tali interi è garantita dal lemma di Bézout.

L’algoritmo euclideo esteso può essere visto come il reciproco dell’esponenziazione modulare.

Invertendo i passi dell’algoritmo euclideo, è possibile trovare questi interi xxx e yyy. L’intera idea è di iniziare con il GCD e lavorare ricorsivamente all’indietro. Questo può essere fatto trattando i numeri come variabili fino a quando ci ritroviamo con un’espressione che è una combinazione lineare dei nostri numeri iniziali. Lo faremo con l’esempio che abbiamo usato sopra.

Iniziamo con il nostro GCD. Lo riscriviamo in termini dei due termini precedenti:

2=26-2×12.2 = 26 – 2 \tempi 12 .2=26-2×12.

Sostituiamo per 121212 prendendo la nostra linea precedente (38=1×26+12)(38 = 1 volta 26 + 12)(38=1×26+12) e scrivendola in termini di 12:

2=26-2×(38-1×26).2 = 26 – 2 volte (38 – 1 volta 26). 2=26-2×(38-1×26).

Raccogliendo i termini simili, i 262626, abbiamo

2=3×26-2×38.2 = 3 volte 26 – 2 volte 38. 2=3×26-2×38.

Ripetere il processo:

2=3×(102-2×38)-2×38.2 = 3 volte (102 – 2 volte 38) – 2 volte 38.2=3×(102-2×38)-2×38.

Il risultato finale è la nostra risposta:

2=3×102-8×38.2 = 3 volte 102 – 8 volte 38.2=3×102-8×38.

Quindi xxx e yyy sono 333 e -8-8-8.

Trova due numeri interi aaa e bbb tali che 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Prima usa l’algoritmo di Euclide per trovare il GCD:

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\1914 &= 2 volte 899 + 116 \899 &= 7 volte 116 + 87 \116 &= 1 volta 87 + 29 \87 &= 3 volte 29 + 0.\Fine{aligned}191489911687=2×899+116=7×116+87=1×87+29=3×29+0.

Da questo, l’ultimo resto non nullo (GCD) è 292929.Ora usiamo l’algoritmo esteso:

29=116+(-1)×87=899+(-7)×116.\inizio{aligned} 29 &= 116 + (-1)\tempi 87\87 &= 899 + (-7)\tempi 116.\fine{aligned}2987=116+(-1)×87=899+(-7)×116.

Sostituendo 878787 nella prima equazione, abbiamo

29=116+(-1)×(899+(-7)×116)=(-1)×899+8×116=(-1)×899+8×(1914+(-2)×899)=8×1914+(-17)×899=8×1914-17×899.\begin{aligned}29&= 116 + (-1)\tempo (899 + (-7)\tempo 116) \&= (-1)\tempi 899 + 8\tempi 116 \&= (-1)\tempi 899 + 8\tempi ( 1914 + (-2)\tempi 899 )\&= 8\tempi 1914 + (-17) \tempi 899 \&= 8\tempi 1914 – 17 \tempi 899.\end{aligned}29=116+(−1)×(899+(−7)×116)=(−1)×899+8×116=(−1)×899+8×(1914+(−2)×899)=8×1914+(−17)×899=8×1914−17×899.

Siccome ora abbiamo scritto il GCD come combinazione lineare di due interi, terminiamo l’algoritmo e concludiamo

a=8,b=-17. □ a = 8, b =-17. \ □ a=8,b=-17. □