W zagadnieniach związanych z podzielnością liczb wygodnie jest posługiwać się pojęciem największego wspólnego dzielnika (NWD).
Największym wspólnym dzielnikiem dwóch liczb nazywamy największą liczbę naturalną dzielącą obie te liczby.
Pojęcie to można uogólnić dla dowolnej ilości liczb, i tak największym wspólnym dzielnikiem wszystkich tych liczb nazywamy największą liczbę naturalną, która dzieli każdą z tych liczb.
Przykład:
liczba 28 ma następujące dzielniki: 1, 2, 4, 7, 14, 28,
zaś liczba 36 takie: 1, 2, 3, 4, 6, 9, 12, 18, 36.
NWD(28, 36) = 4.
Jeśli największym wspólnym dzielnikiem dwóch liczb jest 1 to mówimy, że liczby te są względnie pierwsze.
Przykład:
NWD(81, 1024) = 1. Liczby 81 i 1024 są względnie pierwsze.
W przykładzie znajdowanie największego wspólnego dzielnika przeprowadzone jest najprostszą metodą, polegającą na wypisaniu wszystkich dzielników obu liczb, a następnie wybraniu największego spośród nich. Istnieje jednak wygodniejsza metoda.
Przykład:
Znaleźć NWD(360, 290).
W celu znalezienia największego wspólnego dzielnika liczb 360 i 290 dokonujemy dla tych liczb tzw. rozkładu na czynniki pierwsze. Sprawdzamy, czy dana liczba dzieli się przez kolejne liczby pierwsze. 360 dzieli się przez 2 dając 180. 180 dzieli się przez 2 dając 90. Postępujemy tak aż dojdziemy do niepodzielnej liczby 1. Po wykonaniu wszystkich działań liczbę 360 możemy zapisać jako iloczyn 2 x 2 x 2 x 3 x 3 x 5. Podobnie w przypadku liczby 290, która - po rozkładzie na czynniki pierwsze - może być zapisana jako 2 x 5 x 29. Teraz wybieramy te czynniki pierwsze, które powtórzyły się w obu przypadkach, przy czym jeśli dana liczba powtarza się kilka razy (jak liczba 2 w rozkładzie liczby 360) bierzemy ją tyle razy, ile wystąpiła w obu rozkładach (w tym przypadku tylko raz). NWD to iloczyn tych czynników, które wystąpiły w obu rozkładach.
Po wykonaniu wszystkich operacji możemy napisać, że NWD(360, 290) = 2 x 5 = 10. Z wszystkich podzielników obu liczb największym jest liczba 10.
W przypadku ogólnienia zagadnienia dla większej ilości liczb procedura jest dokładnie taka sama - wybieramy (podkreślamy, zaznaczamy) te czynniki pierwsze, które wystąpiły we wszystkich rozkładach. Szukanym NWD jest ich iloczyn.
Zadania:
Znaleźć największe wspólne dzielniki dla następujących par i trójek liczb:
a) 26, 49,
b) 345, 1860,
c) 12, 240, 72,
d) 100, 369, 287.
Odpowiedzi:
a) 1,
b) 15,
c) 12,
d) 1.