Kalkulator rozszerzonego algorytmu Euklidesa
Policz NWD(a,b) oraz współczynniki Bézouta x i y takie, że a·x + b·y = NWD. Przydatne do odwrotności modularnej i zadań z arytmetyki modularnej.
g = NWD(a,b)
•
a·x + b·y = g
•
a⁻¹ mod n istnieje gdy NWD(a,n)=1
Do czego służy rozszerzony algorytm Euklidesa?
W kalkulatorze rozszerzonego algorytmu Euklidesa wyznaczysz NWD(a,b) oraz współczynniki Bézouta (x, y), które spełniają równanie a·x + b·y = NWD(a,b). To niezbędne, gdy pojawia się temat odwrotności modularnej, dzielenia modulo lub zadania „znajdź x i y”.
Jeśli pracujesz z modulo, w praktyce obok przydaje się arytmetyka modularna. W kryptografii często pojawiają się też liczby pierwsze i rozkład. Do logiki w dyskretnej zobacz tablicę prawdy, a do kombinatoryki wariacje i kombinacje.
Wzór i logika obliczeń
Kluczowe fakty:
- NWD(a,b) to największa liczba całkowita, która dzieli jednocześnie a i b.
- Rozszerzony Euklides zwraca dodatkowo współczynniki Bézouta: a·x + b·y = g, gdzie g = NWD(a,b).
- Odwrotność modularna a⁻¹ mod n istnieje wtedy i tylko wtedy, gdy NWD(a,n)=1. Wtedy a·x ≡ 1 (mod n), a x (po znormalizowaniu do 0…n−1) jest odwrotnością.
Jak to policzyć w praktyce?
Wpisz a i b. Kalkulator pokaże NWD, współczynniki x i y oraz tabelę kroków (ilorazy q, reszty r). Jeśli podasz też n, zobaczysz czy istnieje odwrotność a⁻¹ mod n.
Przykład obliczeń
Dla a = 240 i b = 46 algorytm zwraca NWD = 2 oraz współczynniki np. x = −9, y = 47, bo 240·(−9) + 46·47 = 2.
To odpowiada pytaniom typu „znajdź x i y takie, że 240x + 46y = NWD(240,46)”.
Zadanie przykładowe i rozwiązanie (1)
Zadanie: Znajdź NWD(119, 544) oraz współczynniki x, y takie, że 119·x + 544·y = NWD.
Rozwiązanie: Wpisz a=119, b=544. Odczytaj NWD i współczynniki Bézouta z wyniku. Tabela kroków pokaże, jak powstają reszty i ilorazy.
To często pojawia się jako „rozszerzony euklides przykład”.
Zadanie przykładowe i rozwiązanie (2)
Zadanie: Oblicz odwrotność modularną 17⁻¹ mod 3120.
Rozwiązanie: Ustaw a=17, b=3120 (żeby policzyć NWD i współczynniki), oraz n=3120. Jeśli NWD=1, kalkulator poda a⁻¹ mod n. To typowy krok w RSA (wyznaczanie wykładnika).
Zapytanie jak z wyszukiwarki: „17 odwrotność modulo 3120”.
Tabela: co oznaczają wyniki?
| Wynik |
Symbol |
Znaczenie |
Po co się przydaje |
| Największy wspólny dzielnik | g | NWD(a,b) | upraszczanie ułamków, warunek odwracalności |
| Współczynnik Bézouta | x | a·x + b·y = g | odwrotność modularna, równania diofantyczne |
| Współczynnik Bézouta | y | a·x + b·y = g | jw. |
| Odwrotność modularna | a⁻¹ mod n | x wzięte modulo n | dzielenie modulo, RSA |
Do praktyki z modulo przejdź do kalkulatora modulo, a do liczb pierwszych do rozkładu na czynniki.
Tabela porównawcza: zwykły NWD vs rozszerzony Euklides
| Cecha |
Algorytm Euklidesa |
Rozszerzony Euklides |
Kiedy potrzebny |
| Wynik NWD | tak | tak | zawsze |
| Współczynniki x, y | nie | tak | odwrotność modulo, równania ax+by=g |
| Odwrotność modularna | pośrednio | bezpośrednio | RSA, kongruencje |
W zadaniach z kryptografii często łączysz to z potęgowaniem modularnym oraz z liczbami pierwszymi.
Ciekawostka
Rozszerzony Euklides działa ekstremalnie szybko nawet dla ogromnych liczb. Liczba kroków jest rzędu log(b), dlatego ten algorytm jest podstawą praktycznych obliczeń w kryptografii.
Najczęstsze błędy i jak zwiększyć dokładność wyniku
- Mylenie znaków – x i y mogą być ujemne; to normalne, liczy się równanie a·x + b·y = g.
- Odwrotność bez warunku – jeśli NWD(a,n) ≠ 1, odwrotność modularna nie istnieje.
- Ujemne a lub b – kalkulator liczy poprawnie, a NWD może być znormalizowany do dodatniego.
- Porównywanie z „%” z programowania – modulo w matematyce zwykle daje wynik w 0…n−1 (tak pokazujemy w odwrotności).
Jeśli wpisujesz „jak znaleźć odwrotność modulo”, najpierw sprawdź NWD(a,n), a potem weź współczynnik x modulo n.
Gdzie to się przydaje na co dzień?
Ułamki i równania diofantyczne
Gdy chcesz uprościć ułamek, zaczynasz od NWD. Gdy masz równanie postaci a·x + b·y = c, rozszerzony Euklides daje punkt startowy.
Modulo i kryptografia
W modulo „dzielenie” to w praktyce mnożenie przez odwrotność. Dlatego rozszerzony Euklides jest niezbędny w RSA i w wielu algorytmach.
Do kompletu warto mieć pod ręką kalkulator modulo, a gdy w zadaniu pojawia się kombinatoryka – wariacje i kombinacje. Do statystyki czasem wchodzi odchylenie przeciętne.
Wskazówka od KalkulatorXXL
Jeśli szukasz odwrotności modularnej, zawsze na końcu sprowadź wynik do 0…n−1 (dodaj n, jeśli wyszło ujemne). Wtedy łatwo zweryfikujesz, że a·inv mod n = 1.
FAQ – Rozszerzony algorytm Euklidesa i współczynniki Bézouta
Wpisz a i b, a kalkulator pokaże tabelę kroków (ilorazy q i reszty r) oraz współczynniki s i t prowadzące do x i y.
To liczby całkowite spełniające a·x + b·y = NWD(a,b). Mogą być ujemne – to normalne.
Używa się rozszerzonego algorytmu Euklidesa. Kalkulator zwraca NWD oraz x i y automatycznie.
Tylko gdy NWD(a,n)=1. Wtedy współczynnik x z równania a·x + n·y = 1, sprowadzony do 0…n−1, jest odwrotnością.
Ustaw a=17 i n=3120. Jeśli NWD=1, kalkulator poda a⁻¹ mod n i pokaże sprawdzenie (a·inv) mod n = 1.
Tak. Współczynniki Bézouta nadal spełniają równanie. Opcja „normalizuj NWD” może wymusić dodatni NWD.
Współczynniki Bézouta nie są unikalne i mogą mieć spore wartości, zwłaszcza dla większych liczb. Równanie a·x + b·y = g nadal będzie prawdziwe.
Wystarczy podstawienie: a·x + b·y powinno dać NWD. Kalkulator pokazuje tę kontrolę wprost.
Służy do wyznaczania odwrotności modularnej (np. wykładnika prywatnego) oraz do operacji w arytmetyce modularnej.