Zacznijmy od znalezienia największego wspólnego dzielnika liczb 527 i 341 przy użyciu standardowego algorytmu euklidesowego jako rozgrzewki:
Standardowy algorytm jest zwięzły i prosty i posłuży jako miły mały przewodnik przy implementacji algorytmu rozszerzonego.
Dla Rozszerzonego Algorytmu Euklidesa weźmiemy trzecie równanie (na niebiesko), odejmiemy 155(1) z obu stron i zrobimy małą zmianę układu, aby otrzymać równoważne równanie, w którym 31 jest izolowane.
Następnie zastąpimy 155 przez 341-186(1), które można znaleźć rozwiązując drugie równanie dla 155, co daje nam następujące wyniki:
Teraz to wyczyśćmy. Upewnij się, że rozdzieliłeś znak ujemny przez nawias i zastąpiłeś 186 + 186 przez 186-2.
Jak możesz zauważyć, po prostu pracujemy naszą drogę wstecz przez standardowy algorytm. Będziemy musieli przejść przez ten proces jeszcze raz, aby otrzymać równanie zawierające 527 i 341, co jest naszym celem.
Aby to zrobić, zastąp 186 przez 527 – 341(1), które pochodzi z pierwszego równania, gdy rozwiązujemy dla 186.
Ponownie upraszczamy równanie, rozdzielając 2 i łącząc w grupy 527 i 341.
Wyraziliśmy teraz 31 jako kombinację liniową 527 i 341. Całkiem fajnie, prawda?
Ponadto liczba po przeciwnej stronie kombinacji liniowej jest największym wspólnym dzielnikiem. Tak więc w tym przypadku 31 jest największym wspólnym dzielnikiem 527 i 341.
Rozszerzony algorytm euklidesowy jest przydatny, ponieważ daje tożsamość Bezouta, jak również podkreśla gcd.
Dzięki za przeczytanie!
.