Pamiętaj: Wyniki kalkulatorów mają charakter informacyjny i zależą od podanych danych oraz przyjętych założeń. W sprawach finansowych, podatkowych, prawnych lub zdrowotnych zweryfikuj wynik w aktualnym źródle lub u odpowiedniego specjalisty.Pamiętaj: Wyniki kalkulatorów mają charakter informacyjny i zależą od podanych danych oraz przyjętych założeń. W sprawach finansowych, podatkowych, prawnych lub zdrowotnych zweryfikuj wynik w aktualnym źródle lub u odpowiedniego specjalisty.
Rozszerzony algorytm Euklidesa – NWD i współczynniki Bézouta
Oblicz NWD(a,b), znajdź współczynniki x i y w równaniu a·x+b·y=NWD(a,b), prześledź kolejne kroki i sprawdź odwrotność modularną.
Liczby do obliczeń
Wpisz dwie liczby całkowite. Pole modułu jest potrzebne tylko wtedy, gdy chcesz znaleźć odwrotność modularną.
NWD • Bézout • modulo
Np. 240, -84 albo 0xF0.
Druga liczba całkowita do NWD.
Wpisz n > 1, aby sprawdzić a⁻¹ mod n. Możesz też zostawić pole puste.
NWD jest zawsze pokazywany jako liczba nieujemna. Dla liczb ujemnych współczynniki x i y są dobierane tak, aby nadal zachodziło a·x+b·y=NWD(a,b).
Wynik
NWD(a,b)
—
—
Współczynnik x
—
Współczynnik y
—
Sprawdzenie:
—
Odwrotność a⁻¹ mod n
—
—
Kolejne kroki rozszerzonego algorytmu Euklidesa
Każdy wiersz pokazuje resztę r oraz liczby s i t, dla których r=a·s+b·t.
Masz już NWD – co możesz policzyć dalej?
Jeśli potrzebujesz tylko NWD i NWW, wybierz prostszy kalkulator. Jeśli pracujesz z resztą z dzielenia albo równaniem modulo, możesz od razu przejść do kolejnego obliczenia.
W zwykłym algorytmie Euklidesa szukasz tylko największego wspólnego dzielnika. W wersji rozszerzonej dostajesz dodatkowo liczby całkowite x i y, które spełniają równanie:
a·x + b·y = NWD(a,b)
Liczby x i y nazywa się współczynnikami Bézouta. Mogą być dodatnie, ujemne albo równe zero.
Przykład: dla a=240 i b=46 mamy NWD=2. Jedna poprawna para to x=-9 i y=47, ponieważ 240·(-9)+46·47=2.
Stąd x=-9 i y=47. Kalkulator pokazuje te same zależności automatycznie.
Czy współczynniki x i y są jedyne?
Nie. Jeśli x₀ i y₀ są jednym rozwiązaniem równania a·x+b·y=g, gdzie g=NWD(a,b), to wszystkie rozwiązania mają postać:
x = x₀ + k·(b/g), y = y₀ - k·(a/g), k ∈ ℤ
Dlatego inne poprawne rozwiązanie może podać inną parę x,y. Najprostsza kontrola to podstawienie jej do a·x+b·y.
Jak znaleźć odwrotność modulo?
Szukasz liczby x, dla której a·x ≡ 1 (mod n). Taka liczba istnieje wtedy i tylko wtedy, gdy NWD(a,n)=1.
Rozszerzony algorytm daje wtedy a·x+n·y=1. Po sprowadzeniu x do zakresu od 0 do n-1 otrzymujesz odwrotność a modulo n.
Przykład: 7⁻¹ mod 26 = 15, bo 7·15=105, a reszta z dzielenia 105 przez 26 wynosi 1.
Kiedy równanie a·x+b·y=c ma rozwiązanie całkowite?
Równanie ma rozwiązanie całkowite wtedy i tylko wtedy, gdy NWD(a,b) dzieli c.
Jeśli kalkulator poda a·x₀+b·y₀=g, a c jest wielokrotnością g, jedną parę dla prawej strony c otrzymasz przez pomnożenie x₀ i y₀ przez c/g.
Jak zapisać rozwiązanie w zeszycie?
1. Zapisz kolejne dzielenia z resztą. Najpierw znajdź NWD zwykłym algorytmem Euklidesa.
2. Wskaż ostatnią niezerową resztę. To jest NWD.
3. Cofaj równania od końca. Każdą resztę zastępuj wyrażeniem z poprzedniego dzielenia.
4. Zbierz liczby stojące przy a i b. To są współczynniki x i y.
5. Sprawdź wynik. Po podstawieniu do a·x+b·y musisz otrzymać NWD.
Najczęstsze błędy
Mylenie zwykłego i rozszerzonego algorytmu. Zwykły daje NWD, rozszerzony dodatkowo x i y.
Odrzucanie ujemnego x lub y. Ujemny współczynnik może być całkowicie poprawny.
Zakładanie, że odwrotność modulo zawsze istnieje. Musi zachodzić NWD(a,n)=1.
Porównywanie tylko jednej pary x,y. Współczynniki Bézouta nie są jedyne.
Pomijanie sprawdzenia. Podstawienie do a·x+b·y szybko wykrywa pomyłkę.
Wpisanie a=0 i b=0. NWD(0,0) nie jest określony.
Ciekawostka
Rozszerzony algorytm Euklidesa zachowuje informację o tym, jak każda kolejna reszta powstaje z liczb wejściowych. Dzięki temu ten sam rachunek prowadzi od NWD do współczynników Bézouta i odwrotności modulo.
Przy ręcznym rozwiązaniu pokaż kolejne dzielenia, wskaż NWD i wykonaj podstawienia wstecz. Sam zapis końcowej pary x,y może nie wystarczyć, jeśli trzeba pokazać sposób obliczenia.
FAQ - rozszerzony algorytm Euklidesa krok po kroku
To wersja algorytmu Euklidesa, która oprócz NWD(a,b) wyznacza całkowite współczynniki x i y spełniające a·x + b·y = NWD(a,b).
Zwykły algorytm wyznacza NWD przez kolejne dzielenia z resztą. Rozszerzony śledzi dodatkowo, jak każdą resztę zapisać jako kombinację liczb a i b, dzięki czemu otrzymujemy współczynniki Bézouta.
Dziel większą liczbę przez mniejszą, zapisz resztę, a następnie dziel poprzedni dzielnik przez poprzednią resztę. Powtarzaj aż reszta będzie równa zero. Ostatnia niezerowa reszta to NWD.
To liczby całkowite x i y, które pozwalają zapisać NWD(a,b) w postaci a·x + b·y. Współczynniki mogą być dodatnie, ujemne albo równe zero.
Użyj rozszerzonego algorytmu Euklidesa. Po znalezieniu NWD cofaj kolejne równania z dzielenia z resztą lub odczytaj współczynniki z tabeli s i t.
Nie. Jeśli x0,y0 jest jednym rozwiązaniem, to wszystkie rozwiązania mają postać x=x0+k·b/g oraz y=y0-k·a/g, gdzie g=NWD(a,b) i k jest liczbą całkowitą.
Podstaw je do a·x + b·y. Wynik musi być równy NWD(a,b). To najprostsza kontrola poprawności.
Odwrotność modularna istnieje wtedy i tylko wtedy, gdy NWD(a,n)=1 oraz w typowym zastosowaniu moduł n jest większy od 1.
Znajdź x i y takie, że a·x+n·y=1. Wtedy x po sprowadzeniu do zakresu od 0 do n-1 jest odwrotnością a modulo n.
Współczynnik Bézouta może być ujemny. Aby otrzymać standardową reprezentację odwrotności, sprowadza się go modulo n do zakresu 0…n-1.
Dokładnie wtedy, gdy NWD(a,b) dzieli c. Gdy warunek jest spełniony, współczynniki Bézouta można odpowiednio przeskalować.
Tak. Obsługiwane są liczby całkowite dodatnie i ujemne. NWD jest zawsze prezentowany jako liczba nieujemna, a współczynniki x i y nadal spełniają a·x + b·y = NWD(a,b).
Tak. Możesz użyć formatu 0x..., także z minusem, np. -0x2A. Wynik może być pokazany dziesiętnie, szesnastkowo albo w obu formatach.
NWD(0,0) nie jest określony, dlatego kalkulator wymaga, aby co najmniej jedna z liczb a lub b była różna od zera.
Najczęściej do współczynników Bézouta, równań diofantycznych, odwrotności modularnej, kongruencji liniowych, teorii liczb i zadań z matematyki dyskretnej.
Tak. Współczynniki Bézouta nie są unikalne. Jeśli inna para daje po podstawieniu dokładnie NWD(a,b), również jest poprawna.