Jak obliczyć NWD? Metody i przykłady obliczeń
NWD, czyli największy wspólny dzielnik, to największa liczba naturalna, przez którą można podzielić dwie lub więcej liczb bez reszty. Możesz go wyznaczyć przez rozkład na czynniki pierwsze albo za pomocą algorytmu Euklidesa. Pierwsza metoda jest intuicyjna, a druga zwykle szybsza przy dużych liczbach.
Co to jest NWD i do czego służy?
Dzielnik danej liczby to liczba, przez którą można ją podzielić bez reszty. Dla liczb 12 i 18 wspólne dzielniki to 1, 2, 3 oraz 6. Największy z nich to 6, dlatego zapisujemy:
NWD(12, 18) = 6
NWD wykorzystuje się między innymi do skracania ułamków. Ułamek 12/18 można skrócić przez 6, otrzymując 2/3. Nie należy mylić NWD z NWW, czyli najmniejszą wspólną wielokrotnością. W przypadku NWD szukamy największego wspólnego dzielnika, a nie najmniejszego.
Jak obliczyć NWD przez rozkład na czynniki pierwsze?
Ta metoda polega na rozłożeniu każdej liczby na czynniki pierwsze, a następnie wybraniu czynników występujących w obu rozkładach. Rozpatrzmy przykład NWD(12, 18).
Postępuj według następujących kroków:
- Rozłóż pierwszą liczbę na czynniki pierwsze – 12 = 2 · 2 · 3.
- Rozłóż drugą liczbę na czynniki pierwsze – 18 = 2 · 3 · 3.
- Wybierz wspólne czynniki – w obu rozkładach występują 2 i 3.
- Pomnóż wspólne czynniki – 2 · 3 = 6.
Ostatecznie:
NWD(12, 18) = 2 · 3 = 6
Każdy wspólny czynnik uwzględnia się tyle razy, ile występuje w obu rozkładach. Na przykład dla liczb 24 i 36 mamy 24 = 2 · 2 · 2 · 3 oraz 36 = 2 · 2 · 3 · 3. Wspólne czynniki to 2, 2 i 3, więc NWD(24, 36) = 2 · 2 · 3 = 12.
Na czym polega algorytm Euklidesa?
Algorytm Euklidesa wykorzystuje kolejne dzielenie z resztą. Najpierw dzielisz większą liczbę przez mniejszą. Następnie mniejszą liczbę zastępujesz resztą z dzielenia i powtarzasz działanie. Gdy reszta wyniesie 0, ostatnia niezerowa reszta jest NWD.
Obliczmy tą metodą NWD(1230, 528):
- 1230 : 528 = 2 reszty 174, czyli 1230 mod 528 = 174.
- 528 : 174 = 3 reszty 6, czyli 528 mod 174 = 6.
- 174 : 6 = 29 reszty 0.
Ostatnia niezerowa reszta to 6, dlatego:
NWD(1230, 528) = 6
Algorytm jest szybki, ponieważ w każdym kroku liczby wyraźnie się zmniejszają. Nie trzeba wypisywać wszystkich dzielników ani rozkładać dużych liczb na czynniki pierwsze. Przy większych liczbach dzielenie z resztą zwykle prowadzi do wyniku w niewielu krokach.
Obie metody można porównać w ten sposób:
| Metoda | Najlepsza dla | Zalety |
|---|---|---|
| Rozkład na czynniki pierwsze | Małych liczb i nauki podstaw | Jasno pokazuje, skąd bierze się wspólny dzielnik |
| Algorytm Euklidesa | Dużych liczb i szybkich obliczeń | Wymaga tylko dzielenia z resztą i zwykle działa w kilku krokach |
W przypadku więcej niż dwóch liczb możesz obliczać NWD kolejno. Na przykład:
NWD(12, 18, 24) = NWD(NWD(12, 18), 24) = NWD(6, 24) = 6.
Gdzie wykorzystuje się NWD?
Największy wspólny dzielnik pojawia się w wielu zadaniach związanych z podzielnością. Najczęstsze zastosowania to:
- skracanie ułamków zwykłych do postaci nieskracalnej,
- dzielenie przedmiotów na największą możliwą liczbę równych grup,
- sprawdzanie, czy dwie liczby są względnie pierwsze,
- rozwiązywanie zadań dotyczących wspólnych dzielników i podzielności.
Gdy NWD dwóch liczb wynosi 1, liczby te są względnie pierwsze. Do ręcznych obliczeń małych liczb dobrze nadaje się rozkład na czynniki pierwsze. Przy dużych liczbach wygodniej zastosować algorytm Euklidesa, ponieważ pozwala szybko otrzymać wynik bez wypisywania wszystkich dzielników.
