Dzielnikiem liczby naturalnej a nazywamy każdą liczbę naturalną b która dzieli a bez reszty.
Wspólnym dzielnikiem liczb a i b nazywamy liczbę c która jest dzielnikiem oby tych liczb.
Każda liczba naturalna ma co najmniej dwa dzielniki: 1 oraz samą siebie. Liczba dzielników dowolnej liczby jest skończona i dzielnik nie może być większy od tej liczby, a największy dzielnik jest mniejszy bądź równy połowie tej liczby.
Największy wspólny dzielnik (NWD) dwóch liczb to największa liczba, która dzieli obie te liczby.
Niech a,b\in\mathbb{Z}. Wówczas liczbę d\in\mathbb{N_+} nazywamy największym wspólnym dzielnikiem liczb a i b, jeśli d jest największą liczbą naturalną która dzieli obie z nich (jest ich dzielnikiem), tj. d|a i d|b. Symbolicznie zapisujemy \text{NWD}(a,b)=d lub \text{nwd}(a,b)=d.
Liczby a,b\in\mathbb{Z} są względnie pierwsze, jeśli \text{NWD}(a,b)=1.
Algorytm wyznaczania NWD dwóch liczb
Aby dla dwóch liczb a i b znaleźć ich \text{NWD}(a,b) należy albo wypisać wszystkie dzielniki obu liczb i wskazać największy, albo:
rozłożyć obie liczby na czynniki pierwsze,
\begin{align*} a&=p_1\cdot p_2\cdot p_3\cdot p_4 \\ b&=p_1\cdot p_1\cdot p_1\cdot p_3\cdot p_5, \\ \end{align*}(0)gdzie p_i to różne liczby pierwsze.
znaleźć czynniki które występują w obu tych rozkładach:
\begin{align*} a&=\textcolor{orange}{p_1}\cdot p_2\cdot \textcolor{green}{p_3}\cdot p_4 \\ b&=\textcolor{orange}{p_1}\cdot p_1\cdot p_1\cdot \textcolor{green}{p_3}\cdot p_5 \\ \end{align*}(0)oraz wreszcie wymnożyć przez siebie znalezione czynniki - otrzymana liczba to szukane \text{NWD}(a,b):
\text{NWD}(a,b)=\textcolor{orange}{p_1}\cdot \textcolor{green}{p_3}(0)
Zwróć uwagę na następujące obserwacje przy wyznaczaniu \text{NWD}(a,b):
Jeżeli b|a, to \text{NWD}(a,b)=b.
Jeżeli b=a, to \text{NWD}(a,b)=a=b.
Jeżeli a i b to liczby względnie pierwsze, to \text{NWD}(a,b)=1.
\text{NWD} dla więcej niż dwóch liczb, np. \text{NWD}(a,b,c) wyznaczamy analogicznie jak w przypadku dwóch liczb - mnożymy przez siebie czynniki pierwsze występujące w każdym z trzech rozkładów.
Alternatywnie, możemy skorzystać z tzw. algorytmu Euklidesa, który opiera się na zasadzie, że NWD dwóch liczb nie zmienia się, jeśli większą liczbę zastąpimy resztą z dzielenia przez mniejszą. Innymi słowy, dla dwóch liczb a i b, gdzie a>b:
Obliczamy resztę r z dzielenia a przez b, tj. r=a\ (\text{mod } b)
Jeżeli r=0, to \text{NWD}(a,b)=b.
W przeciwnym razie, podstawiamy a=b, b=r i powtarzamy punkt 1.
Rekurencyjnie, możemy zapisać: