MathWizards

Definicja 1

Dzielnik

Dzielnikiem liczby naturalnej $a$ a nazywamy każdą liczbę naturalną $b$ b która dzieli $a$ a bez reszty.

Wspólnym dzielnikiem liczb $a$ a i $b$ b nazywamy liczbę $c$ c która jest dzielnikiem oby tych liczb.

Uwaga 1

Każda liczba naturalna ma co najmniej dwa dzielniki: $1$ 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}$ a,b\in\mathbb{Z}. Wówczas liczbę $d\in\mathbb{N_+}$ d\in\mathbb{N_+} nazywamy największym wspólnym dzielnikiem liczb $a$ a i $b$ b, jeśli $d$ d jest największą liczbą naturalną która dzieli obie z nich (jest ich dzielnikiem), tj. $d|a$ d|a i $d|b$ d|b. Symbolicznie zapisujemy $\text{NWD}(a,b)=d$ \text{NWD}(a,b)=d lub $\text{nwd}(a,b)=d$ \text{nwd}(a,b)=d.

Definicja 3

Liczby względnie pierwsze

Liczby $a,b\in\mathbb{Z}$ a,b\in\mathbb{Z} są względnie pierwsze, jeśli $\text{NWD}(a,b)=1$ \text{NWD}(a,b)=1.

Algorytm wyznaczania NWD dwóch liczb

Aby dla dwóch liczb $a$ a i $b$ b znaleźć ich $\text{NWD}(a,b)$ \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*}$
\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$ 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*}$
\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):
$\text{NWD}(a,b)=\textcolor{orange}{p_1}\cdot \textcolor{green}{p_3}$
\text{NWD}(a,b)=\textcolor{orange}{p_1}\cdot \textcolor{green}{p_3}(0)

Uwaga 2

$\text{NWD}$ \text{NWD}

Zwróć uwagę na następujące obserwacje przy wyznaczaniu $\text{NWD}(a,b)$ \text{NWD}(a,b):

Jeżeli $b|a$ b|a, to $\text{NWD}(a,b)=b$ \text{NWD}(a,b)=b.
Jeżeli $b=a$ b=a, to $\text{NWD}(a,b)=a=b$ \text{NWD}(a,b)=a=b.
Jeżeli $a$ a i $b$ b to liczby względnie pierwsze, to $\text{NWD}(a,b)=1$ \text{NWD}(a,b)=1.
$\text{NWD}$ \text{NWD} dla więcej niż dwóch liczb, np. $\text{NWD}(a,b,c)$ \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$ a i $b$ b, gdzie $a>b$ a>b:

Obliczamy resztę $r$ r z dzielenia $a$ a przez $b$ b, tj. $r=a\ (\text{mod } b)$ r=a\ (\text{mod } b)
- Jeżeli $r=0$ r=0, to $\text{NWD}(a,b)=b$ \text{NWD}(a,b)=b.
- W przeciwnym razie, podstawiamy $a=b$ a=b, $b=r$ b=r i powtarzamy punkt $1$ 1.

Rekurencyjnie, możemy zapisać:

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

(0)

Największy wspólny dzielnik (NWD)

Dzielnik

Uwaga

Największy wspólny dzielnik (NWD)

Liczby względnie pierwsze

Algorytm wyznaczania NWD dwóch liczb

NWD\text{NWD}NWD\text{NWD}

$\text{NWD}$ \text{NWD}