Największy wspólny dzielnik

NWD – Największy wspólny dzielnik
Dzielnik liczby – liczba całkowita, przez którą możemy podzielić konkretną liczbę – nazywaną „dzielną” bez uzyskania reszty:
Na przykład: jeżeli mamy liczbę 6 to jej dzielnikami będą kolejno
D(6): 1; 2; 3; 6.
Liczba sześć dzieli się przez wszystkie te liczby, uzyskujemy w wyniku liczbę całkowitą bez reszty.
Dzielników może być oczywiście więcej, w zależności od tego jaką wartość ma dzielna.
Na przykład – liczba 36
Dzielnikami liczby 36 czyli
D(36) są: 1; 2; 3; 4; 6; 9; 12; 18; 36

Jeśli szukamy największego wspólnego dzielnika dla dwóch liczb, to zapisujemy to w następujący sposób:
NWD(a,b):
Na przykład: największym wspólnym dzielnikiem liczb 12 i 8 jest liczba 4.
Obliczenia.
Wypisujemy dzielniki obu liczb:
Dzielniki liczby 12: 1; 2; 3; 4; 6; 12
Dzielniki liczby 8: 1; 2; 4; 8
Wspólnym dzielnikiem jak widać jest liczba 4.

Jeśli chcemy możemy to zapisać tak:
NWD (12, 8) = 4
Czytamy to wtedy tak:
Największy wspólny dzielnik liczb dwanaście i osiem to cztery.
Ćwiczenie 1:
Znajdź NWD(45,60)
Obliczenia
D(45) = {1, 3, 5, 9, 15, 45}
D(60) = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}
Dla powyższych liczb wspólnym dzielnikiem jest jak widać liczba 15, wynik zapisujemy tak:
NWD(45, 60) = 15

Ćwiczenie 2:
Znajdź NWD(125,180)
Obliczenia
D(125)={1, 5, 25, 125}
D(180)={1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180}
Dla powyższych liczb wspólnym dzielnikiem jest liczba 5 i zapisujemy wynik tak:
NWD(125, 180) = 5

NWD można obliczać także za pomocą rozkładu liczby na czynniki pierwsze:
Jeśli mamy liczbę 180 i 40 to wypisywanie ich dzielników może zająć dość dużo czasu. Żeby obliczyć to szybciej można zastosować taką metodę:


W obu przykładach znajdują się liczby: 2, 2 i 5 więc żeby obliczyć największy wspólny dzielnik trzeba je przez siebie pomnożyć


Ćwiczenie 1:
Znajdź NWD(450,600)
Obliczenia


Wspólnymi dzielnikami są liczby: 2, 3, 5, 5 – wynik zapisujemy następująco:
NWD(450,600) = = 150

Ćwiczenie 2:
Znajdź NWD(75,100)
Obliczenia


Wspólnymi dzielnikami są liczby: 5 i 5, czyli zapisujemy wynik następująco:
NWD(75,100) =

Ciekawostka
Dzielnik nie może być większy od połowy dzielnej.