Największy wspólny dzielnik — NWD

Największy wspólny dzielnik (NWD) dwóch liczb jest to największa spośród takich liczb, które są jednocześnie dzielnikami obu liczb.

Największy wspólny dzielnik liczb \(a\) i \(b\) oznaczamy następująco: \(NWD(a,b)\).

Przykłady

Podzielnikami liczb 12 i 18 są liczby: 1, 2, 3 oraz 6. Największą z tych liczb jest 6, a więc jest to największy wspólny dzielnik. Zapisujemy to w następujący sposób: \(NWD(12,18)=6\).

Jak obliczyć NWD?

NWD dwóch liczb naturalnych znajdujemy, wykorzystując rozkład na czynniki pierwsze.

NWD jest równe iloczynowi wszystkich czynników pierwszych wspólnych dla obu liczb.

Obliczanie NWD nie jest trudne. Poniższy przykład ułatwi zrozumienie algorytmu znajdowania największego wspólnego dzielnika.

Animacja

Powyższa animacja jest bardzo obrazowa, podajemy jednak algorytm znajdowania NWD w sposób opisowy:

Zapisujemy dwie liczby obok siebie.
Rysujemy pionową kreskę z prawej strony liczby.
Dzielimy daną liczbę przez najmniejszą liczbę pierwszą, będącą jej dzielnikiem i dzielnik zapisujemy po prawej, a wynik po lewej stronie pod liczbą.
Tak długo dzielimy uzyskany wynik przez najmniejsze liczby pierwsze, aż uzyskamy w wyniku liczbę 1.
Takie same kroki wykonujemy dla drugiej liczby.
Zakreślamy w obu kolumnach dzielników kółkiem pary takich samych dzielników i mnożymy je przez siebie.
Wynik powyższego mnożenia to największy wspólny dzielnik.

Poniższy program online znajduje NWD dwóch liczb. Wspomaga samodzielne obliczanie NWD poprzez możliwość porównania wyniku.

Kalkulator NWD

Kalkulator
Podaj dowolne dwie liczby naturalne. Nasz robot znajdzie rozwiązanie.

Wpisz dane:

Liczba 1:
Liczba 2:

Rozwiązanie:

Przykład

A oto inny przykład: Znaleźć największy wspólny dzielnik liczb 999 i 3108:

\(NWD(999,3108)=3\cdot 37=111\)

Zatem największy dzielnik liczb 999 i 3108 to 111. Można sprawdzić, że 999 : 111 = 9 i 3108 : 111 = 28.

Uwaga! NWD to największy wspólny dzielnik, a nie najmniejszy wspólny dzielnik, jak często można usłyszeć ze szkolnych ławek.

Ciekawostka

Aby znaleźć największy wspólny dzielnik trzech liczb, trzeba je rozłożyć na czynniki pierwsze i zaznaczyć we wszystkich diagramach takie same podzielniki.