Największy wspólny dzielnik (NWD)
Największy wspólny dzielnik (\text{NWD}) dwóch liczb naturalnych dodatnich to dokładnie to, na co wskazuje nazwa :-) Na przykład dla liczb 12 i 18 \text{NWD} to 6, co zapisujemy jako: \text{NWD}(12,18) = 6. Jest tak gdyż 6 jest dzielnikiem 12 i 6 jest dzielnikiem 18 (stąd jest on wspólny) i nie ma innego większego dzielnika wspólnego dla tych dwóch liczb.
Aby wyznaczyć \text{NWD} dla dwóch liczb naturalnych dodatnich należy je najpierw rozłożyć na czynniki pierwsze.
Przykład. Oblicz \text{NWD}(112,148).
Rozkładamy 112 i 148 na czynniki pierwsze:
112 = \bold{2}\cdot\bold{2}\cdot2\cdot2\cdot7
148 = \bold{2}\cdot\bold{2}\cdot37
Iloczyn ich wspólnych czynników pierwszych to \text{NWD}. Czyli:
\text{NWD}(112,148) = \bold{2}\cdot\bold{2} = 4
Przykład. Oblicz \text{NWD}(3850,660).
Rozkład na czynniki pierwsze:
3850 = \bold{2}\cdot\bold{5}\cdot5\cdot7\cdot\bold{11}
660 = \bold{2}\cdot2\cdot3\cdot\bold{5}\cdot\bold{11}
Wybieramy wspólne czynniki pierwsze i obliczamy ich iloczyn:
\text{NWD}(3850, 660) = \bold{2}\cdot\bold{5}\cdot\bold{11} = 110
Przykład. Oblicz \text{NWD}(350,429).
Rozkład na czynniki pierwsze:
350 = 2\cdot 5\cdot 5\cdot 7
429 = 3\cdot 11\cdot 13
Jak widać, liczby te nie mają wspólnych czynników pierwszych. Wtedy:
\text{NWD}(350, 429) = 1
Liczby takie nazywamy względnie pierwszymi.