Rozszerzony algorytm euklidesowy

Rozszerzony algorytm euklidesowy to algorytm obliczania liczb całkowitych xxx i yyy takich, że

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

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

dane aaa i bbb.

Istnienie takich liczb całkowitych gwarantuje lemat Bézouta.

Rozszerzony algorytm euklidesowy można traktować jako odwrotność wykładania modułowego.

Odwracając kroki w algorytmie euklidesowym, można znaleźć takie liczby całkowite xxx i yyy. Cała idea polega na tym, aby zacząć od GCD i rekurencyjnie pracować naszą drogę wstecz. Można to zrobić, traktując liczby jako zmienne, aż w końcu otrzymamy wyrażenie, które jest kombinacją liniową naszych początkowych liczb. Zrobimy to na przykładzie, którego użyliśmy powyżej.

Zaczynamy od naszego GCD. Zapisujemy ją w kategoriach poprzednich dwóch wyrażeń:

2=26-2×12.2 = 26 – 2 razy 12 .2=26-2×12.

Zastępujemy dla 121212 biorąc nasz poprzedni wiersz (38=1×26+12)(38 = 1 \times 26 + 12)(38=1×26+12) i pisząc go w kategoriach 12:

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

Zbierz podobne wyrażenia, te 262626, i mamy

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

Powtórz ten proces:

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

Wynikiem końcowym jest nasza odpowiedź:

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

Więc xxx i yyy są równe 333 i -8-8-8.

Znajdź dwie liczby całkowite aaa i bbb takie, że 1914a+899b=gcd(1914,899).1914a + 899b = ∗gcd(1914,899). 1914a+899b=gcd(1914,899).

Najpierw użyj algorytmu Euklidesa, aby znaleźć GCD:

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

Z tego wynika, że ostatnia niezerowa reszta (GCD) to 292929.Teraz korzystamy z rozszerzonego algorytmu:

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

Podstawiając 878787 w pierwszym równaniu, mamy

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 29&= 116 + (-1)razy (899 + (-7)razy 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.

Ponieważ teraz zapisaliśmy GCD jako kombinację liniową dwóch liczb całkowitych, kończymy algorytm i stwierdzamy

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

a=8,b=-17. □