Największy wspólny dzielnik (NWD)

Największy wspólny dzielnik (NWD) obliczysz, gdy w specjalnie do tego przeznaczone rubryki wpiszesz dwie liczby całkowite.
A poniżej kalkulatora możesz przeczytać także o tym, jakie algorytmy wykorzystywane są do obliczenia największego wspólnego dzielnika.

Czym jest Największy Wspólny Dzielnik (NWD)?

Największy wspólny dzielnik (w skrócie NWD), dla dwóch liczb całkowitych, jest to największa liczba naturalna dzieląca każdą z nich.

Gdy mamy dwie liczby a i b to największy wspólny dzielnik zapisuje się jako NWD(a, b).

Przykład: NWD(18, 12) = 6.

Algorytm Euklidesa

Euklides to grecki matematyk, który w swoim dziele Elementy opisał algorytm do wyznaczania największego wspólnego dzielnika. Został on opisany około 300 lat p.n.e. i jest on jednym z najstarszych, wciąż używanych algorytmów numerycznych.

Istnieją dwie wersje Algorytm Euklidesa: wykorzystującą odejmowanie i wykorzystującą funkcję modulo

1. Algorytm wykorzystujący funkcję modulo

   krok 1. dla liczb a i b oblicz resztę z dzielenia - q

   krok 2. liczbę a zastąp liczbą b, liczbę b liczbą q

   krok 3. jeśli b wynosi 0, to a jesz szukaną wartością, w przeciwnym przypadku przejdź do kroku 1

Zastosowanie Największego Wspólnego Dzielnika

Największy Wspólny Dzielnik potrzebny jest do obliczania Najmniejszej Wspólnej Wielokrotności (NWW).

zobacz również:

• Dzielenie z resztą
• Generator liczb losowych
• Kalkulator binarny
• Kalkulator funkcji kwadratowej
• Kalkulator logarytmów
• Kalkulator macierzy
• Kalkulator modulo
• Kalkulator naukowy online
• Kalkulator pierwiastków
• Kalkulator potęg
• Kalkulator procentowy
• Kalkulator ułamków
• Najmniejsza wspólna wielokrotność (NWW)
• Objętość i pole walca - kalkulator
• Średnia ważona