NWD i NWW liczb naturalnych

Aby dobrze rozumieć NWD i NWW, trzeba odróżniać pojęcia dzielnika oraz wielokrotności. Dodatnia liczba naturalna $d$ jest dzielnikiem liczby $a$, gdy dzielenie $a$ przez $d$ daje resztę równą $0$. Zapisujemy wtedy $d\mid a$.

Wielokrotność liczby $a$ ma postać $a\cdot k$, gdzie $k$ jest liczbą naturalną. Każda liczba ma skończenie wiele dodatnich dzielników, ale nieskończenie wiele wielokrotności.

• Dzielnikami $18$ są $1$, $2$, $3$, $6$, $9$ i $18$.
• Wielokrotnościami $18$ są $18$, $36$, $54$, $72$ i kolejne.

Największy wspólny dzielnik liczb naturalnych dodatnich to największa liczba, która dzieli każdą z nich bez reszty. Stosuje się oznaczenie $NWD(a,b)$. Dla liczb $18$ i $30$ wspólnymi dzielnikami są $1$, $2$, $3$ i $6$, zatem $NWD(18,30)=6$.

Najmniejsza wspólna wielokrotność to najmniejsza dodatnia liczba będąca wielokrotnością wszystkich danych liczb. Oznaczamy ją przez $NWW(a,b)$. Na przykład wspólnymi wielokrotnościami $6$ i $8$ są $24$, $48$, $72$ i dalsze, więc $NWW(6,8)=24$.

Nie należy mylić tych pojęć: NWD jest związany z dzieleniem na równe części, a NWW z pierwszym wspólnym powtórzeniem zdarzeń.

Najbardziej uniwersalną szkolną metodą jest rozkład liczb na czynniki pierwsze. Liczba pierwsza ma dokładnie dwa dodatnie dzielniki: $1$ i samą siebie. Przykładowo $72=2^3\cdot 3^2$, a $90=2\cdot 3^2\cdot 5$.

Przy wyznaczaniu NWD wybieramy wyłącznie czynniki pierwsze obecne w każdym rozkładzie. Jeżeli dany czynnik występuje z różnymi wykładnikami, bierzemy mniejszy wykładnik.

Przy wyznaczaniu NWW zapisujemy wszystkie czynniki pierwsze występujące w co najmniej jednym rozkładzie. Dla każdego z nich wybieramy największy wykładnik.

Gdy liczby są duże, wygodny jest algorytm Euklidesa. Dzielimy większą liczbę przez mniejszą i zapisujemy resztę. Następnie dzielimy poprzedni dzielnik przez otrzymaną resztę. Postępujemy tak, aż pojawi się reszta $0$. Ostatnia niezerowa reszta jest NWD.

Dla $252$ i $105$: $252=2\cdot 105+42$, następnie $105=2\cdot 42+21$, a $42=2\cdot 21+0$. Stąd $NWD(252,105)=21$.

Dla dodatnich liczb $a$ i $b$ zachodzi bardzo ważna zależność:

$$NWD(a,b)\cdot NWW(a,b)=a\cdot b$$

Można więc obliczyć NWW, jeśli znamy NWD: $NWW(a,b)=\frac{a\cdot b}{NWD(a,b)}$.

Liczby względnie pierwsze mają NWD równy $1$. Nie oznacza to, że każda z nich musi być liczbą pierwszą. Na przykład $8$ i $15$ są złożone, lecz nie mają wspólnego dzielnika większego od $1$.

Jeśli $NWD(a,b)=1$, wtedy z podanego wzoru wynika, że $NWW(a,b)=a\cdot b$. To znacznie przyspiesza obliczenia.

NWD pojawia się w zadaniach o dzieleniu przedmiotów na największe równe grupy oraz w skracaniu ułamków. NWW stosuje się przy sprowadzaniu ułamków do wspólnego mianownika i w zadaniach o cykliczności, na przykład gdy dwa autobusy odjeżdżają w różnych odstępach czasu.