Największy wspólny dzielnik (NWD)
Największy wspólny dzielnik (\text{NWD}) dwóch dodatnich liczb naturalnych to największa liczba, która jest dzielnikiem obu tych liczb.
Na przykład:
\text{NWD}(12,18) = 6
Jest tak, ponieważ liczba 6 dzieli zarówno 12, jak i 18, a większego wspólnego dzielnika te liczby już nie mają.
Aby obliczyć \text{NWD} dwóch liczb, najpierw rozkładamy je na czynniki pierwsze. Następnie wybieramy wspólne czynniki pierwsze i obliczamy ich iloczyn.
Przykład. Oblicz \text{NWD}(112,148).
Rozkładamy liczby na czynniki pierwsze:
112 = 2\cdot2\cdot2\cdot2\cdot7
148 = 2\cdot2\cdot37
Wybieramy wspólne czynniki pierwsze:
112 = \boxed{2}\cdot\boxed{2}\cdot2\cdot2\cdot7
148 = \boxed{2}\cdot\boxed{2}\cdot37
Obliczamy ich iloczyn:
\text{NWD}(112,148) = \boxed{2}\cdot\boxed{2} = 4
Przykład. Oblicz \text{NWD}(3850,660).
Rozkładamy liczby na czynniki pierwsze:
3850 = 2\cdot5\cdot5\cdot7\cdot11
660 = 2\cdot2\cdot3\cdot5\cdot11
Wybieramy wspólne czynniki pierwsze:
3850 = \boxed{2}\cdot\boxed{5}\cdot5\cdot7\cdot\boxed{11}
660 = \boxed{2}\cdot2\cdot3\cdot\boxed{5}\cdot\boxed{11}
Obliczamy ich iloczyn:
\text{NWD}(3850, 660) = \boxed{2}\cdot\boxed{5}\cdot\boxed{11} = 110
Przykład. Oblicz \text{NWD}(350,429).
Rozkładamy liczby na czynniki pierwsze:
350 = 2\cdot 5\cdot 5\cdot 7
429 = 3\cdot 11\cdot 13
Liczby te nie mają wspólnych czynników pierwszych, więc:
\text{NWD}(350, 429) = 1
Liczby takie nazywamy względnie pierwszymi.