Definicja 1

Dzielnik

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.

Uwaga 1

Uwaga

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.

Definicja 2

Największy wspólny dzielnik (NWD)

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.

Definicja 3

Liczby względnie pierwsze

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,
(0)\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*}
gdzie p_i to różne liczby pierwsze.
znaleźć czynniki które występują w obu tych rozkładach:
(0)\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*}
oraz wreszcie wymnożyć przez siebie znalezione czynniki - otrzymana liczba to szukane \text{NWD}(a,b):
(0)\text{NWD}(a,b)=\textcolor{orange}{p_1}\cdot \textcolor{green}{p_3}

Uwaga 2

\text{NWD}

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ć:

(0)\text{NWD}(a,b)=\begin{cases} b,&\text{gdy }b=0\\ \text{NWD}(b, a\ \text{mod }b),& \text{w przeciwnym razie} \end{cases}