W tym artykule platforma edukacyjna Mathema wyjaśni, czym jest największy wspólny dzielnik (NWD) i jak łatwo go znaleźć za pomocą algorytmu Euklidesa. Znajdziesz tu również zadania dotyczące znajdowania największego wspólnego dzielnika.
Co to jest największy wspólny dzielnik (NWD)?
Największy wspólny dzielnik (NWD) dwóch lub więcej liczb to największa liczba, która dzieli każdą z tych liczb bez reszty. Innymi słowy, jest to największa liczba, na którą mogą dzielić się wszystkie te liczby jednocześnie.
Przykład: Rozważmy liczby 55 i 132. Największym wspólnym dzielnikiem tych liczb jest 11, ponieważ:
- 55 dzieli się przez 11 (55 ÷ 11 = 5)
- 132 dzieli się przez 11 (132 ÷ 11 = 12)
Zatem NWD dla liczb 55 i 132 wynosi 11.
Jak znaleźć największy wspólny dzielnik (NWD)?
Oto kilka sposobów na znalezienie NWD. Przeanalizujmy na przykładzie liczb 35 i 133.
Wypisz liczby, przez które dzieli się pierwsza liczba:
- Dla 35: 1, 5, 7, 35
- Dla 133: 1, 7, 19, 133
- NWD = 7
W tym przypadku widzimy, że obie liczby dzielą się przez 7 i 1. 7 jest największym wspólnym dzielnikiem.
Rozłóż liczby na czynniki pierwsze:
- 35 = 5 · 7
- 133 = 7 · 19
- NWD = 7
Wybierzmy bardziej skomplikowany przykład i spróbujmy go rozwiązać rozkładając na czynniki pierwsze. Weźmy liczby 154 i 396.
- 154 = 14 · 11 = 2 · 7 · 11
- 396 = 4 · 9 · 11 = 2 · 2 · 3 · 3 · 11
- NWD (154 i 396) = 2 · 11 = 22
Jeśli największym wspólnym dzielnikiem dla obu liczb jest 1, to takie liczby nazywamy względnie pierwszymi.
Co to jest algorytm Euklidesa?
Algorytm Euklidesa to prosty sposób na znalezienie największego wspólnego dzielnika (NWD) dwóch liczb. Oto jak to się robi:
- Weźmy dwie liczby, na przykład 48 i 18. Zacznijmy od większej liczby.
- Podziel większą liczbę przez mniejszą i znajdź resztę. Dla 48 i 18 reszta wynosi 12 (48 = 18 · 2 + 12).
- Powtórz proces: podziel 18 przez 12. Reszta wynosi 6 (18 = 12 · 1 + 6).
- Kontynuuj dzielenie, aż reszta będzie równa 0.
- Ostatnia liczba, przez którą dzieliliśmy bez reszty, jest NWD.
- W naszym przypadku 12 dzieli się przez 6 bez reszty, a reszta wynosi 0.
- Zatem NWD wynosi 6.
Algorytm Euklidesa polega na dzieleniu liczb jedna przez drugą, aż uzyskamy resztę równą 0.
Algorytm Euklidesa został wymyślony ponad 2000 lat temu przez greckiego matematyka Euklidesa i opisany w jego książce „Elementy” około 300 roku p.n.e. Jest to jedna z najstarszych metod matematycznych, która nadal jest stosowana. Euklides opracował ten algorytm do badania właściwości liczb. Nawet dziś metoda ta pozostaje ważna w matematyce i informatyce.
Zadania na znajdowanie NWD
Oto pięć zadań dotyczących znajdowania największego wspólnego dzielnika. Spróbuj rozwiązać je różnymi metodami oraz znaleźć wśród tych liczb liczby względnie pierwsze.
- Znajdź NWD liczb 56 i 98.
- Znajdź NWD liczb 105 i 252.
- Znajdź NWD liczb 144 i 60.
- Znajdź NWD liczb 81 i 153.
- Znajdź NWD liczb 72 i 120.
