Algoritmul euclidian extins

Algoritmul euclidian extins este un algoritm de calcul al numerelor întregi xxx și yyy astfel încât

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

datorită aaa și bbb.

Existența unor astfel de numere întregi este garantată de lema lui Bézout.

Algoritmul euclidian extins poate fi privit ca reciproca exponențializării modulare.

Inversând pașii din algoritmul euclidian, este posibil să se găsească acești numere întregi xxx și yyy. Întreaga idee este de a începe cu GCD și de a lucra recursiv în sens invers. Acest lucru poate fi realizat prin tratarea numerelor ca variabile până când ajungem la o expresie care este o combinație liniară a numerelor inițiale. Vom face acest lucru cu exemplul pe care l-am folosit mai sus.

Începem cu GCD-ul nostru. Îl rescriem în termenii celor doi termeni anteriori:

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

Înlocuim pentru 12121212 luând linia noastră anterioară (38=1×26+12)(38 = 1 \times 26 + 12)(38=1×26+12) și scriind-o în termeni de 12:

2=26-2×(38-1×26).2 = 26 – 2 \times (38 – 1\times 26). 2=26-2×(38-1×26).

Colectați termenii asemănători, cei 262626, și avem

2=3×26-2×38.2 = 3 \timpuri 26 – 2 \timpuri 38. 2=3×26-2×38.

Repetă procesul:

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

Rezultatul final este răspunsul nostru:

2=3×102-8×38.2 = 3 \times 102 – 8 \times 38.2=3×102-8×38.

Atunci xxx și yyy sunt 333 și -8-8-8-8.

Găsește două numere întregi aaa și bbb astfel încât 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Utilizați mai întâi algoritmul lui Euclid pentru a găsi GCD:

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\begin{aligned}1914 &= 2 \timpuri 899 + 116 \899 &= 7 \puri 116 + 87 \116 &= 1 \puri 87 + 29 \87 &= 3 \puri 29 + 0.\end{aligned}191489911687=2×899+116=7×116+87=1×87+29=3×29+0.

Din aceasta, ultimul rest diferit de zero (GCD) este 292929.Acum folosim algoritmul extins:

29=116+(-1)×8787=899+(-7)×116.\begin{aligned} 29 &= 116 + (-1)\ ori 87\\87 &= 899 + (-7)\ ori 116.\end{aligned}2987=116+(-1)×87=899+(-7)×116.

Substituind 878787 în prima ecuație, avem

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)\ ori (899 + (-7)\ ori 116) \\\&= (-1)\times 899 + 8\times 116 \\\&= (-1)\times 899 + 8\times ( 1914 + (-2)\times 899 )\\&= 8\times 1914 + (-17) \times 899 \&= 8\times 1914 – 17 \times 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.

Din moment ce am scris acum GCD-ul ca o combinație liniară a două numere întregi, terminăm algoritmul și concluzionăm

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