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.

Największy wspólny dzielnik (NWD) - definicja

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