NWD i NWW

Obliczanie NWD i NWW

Największy Wspólny Dzielnik (NWD) zbioru liczb to największa liczba, która dzieli bez reszty każdą z nich, a Najmniejsza Wspólna Wielokrotność (NWW) to najmniejsza liczba, którą każda z nich dzieli bez reszty. Podaj dwie lub więcej liczb całkowitych, a ten kalkulator natychmiast znajdzie obie wartości.

Metoda

NWD znajduje się za pomocą algorytmu Euklidesa — metody pochodzącej sprzed ponad 2000 lat: dziel wielokrotnie większą liczbę przez mniejszą i zastępuj większą resztą, aż reszta osiągnie zero. Ostatnia niezerowa wartość to NWD.

Gdy znany jest NWD, NWW dwóch liczb wynika bezpośrednio:

$$\text{NWW}(\vA{a}, \vB{b}) = \frac{\vA{a} \times \vB{b}}{\vC{\text{NWD}(\vA{a}, \vB{b})}}$$

Dla więcej niż dwóch liczb, ten kalkulator stosuje obie metody parami na całej liście.

Przykład obliczeniowy

Znajdowanie NWD i NWW liczb 12 i 18:

1. Algorytm Euklidesa: 18 ÷ 12 daje resztę 6; 12 ÷ 6 daje resztę 0. NWD to $\vC{6}$.
2. $\text{NWW}(\vA{12}, \vB{18}) = (12 \times 18) \div \vC{6} = 216 \div \vC{6} = 36$.

Kluczowe czynniki do rozważenia

• Dwie liczby o NWD równym 1 nazywane są “względnie pierwszymi”, to naprawdę przydatna klasyfikacja. Gdy NWD wynosi 1, obie liczby nie mają wspólnych czynników poza 1 — ma to znaczenie w takich dziedzinach jak kryptografia i teoria liczb, a także oznacza, że ich NWW to po prostu ich iloczyn.
• Algorytm Euklidesa jest znacznie szybszy niż wypisywanie każdego czynnika dla dużych liczb. Znajdowanie NWD przez wypisanie wszystkich czynników każdej liczby i ich porównanie staje się niepraktyczne dla dużych liczb — algorytm Euklidesa znajduje odpowiedź w zaledwie kilku krokach niezależnie od tego, jak duże są liczby, dlatego właśnie jest standardową metodą od ponad 2000 lat.
• NWD i NWW uogólniają się gładko na więcej niż dwie liczby, używając tego samego parami budowanego bloku. Zastosowanie wzoru dla dwóch liczb do całej listy — NWD(NWD(a,b), c), i podobnie dla NWW — poprawnie rozszerza oba pojęcia na dowolną liczbę wartości wejściowych, dokładnie tak, jak ten kalkulator obsługuje listę dłuższą niż dwie liczby.
• Te pojęcia pojawiają się stale poza czystą matematyką, w problemach harmonogramowania i podziału zasobów. Poza upraszczaniem ułamków, NWW odpowiada na pytanie “kiedy dwa powtarzające się wydarzenia znów się pokryją” (jak rozkłady autobusów czy migające światła), a NWD odpowiada na pytanie “na jak największe równe grupy mogę to podzielić” (jak podział przedmiotów na identyczne paczki bez reszty).

Częste błędy

• Mylenie, który to NWD, a który NWW. Nazwy brzmią podobnie i łatwo je pomylić — NWD zawsze jest mniejszym z dwóch wyników (wspólny dzielnik, więc nie może przekroczyć najmniejszej liczby wejściowej), podczas gdy NWW zawsze jest większy (wspólna wielokrotność, więc jest co najmniej tak duży jak największa liczba wejściowa).
• Zakładanie, że NWD musi być jedną z porównywanych liczb. Jak opisano powyżej, NWD to największa liczba, która dzieli bez reszty każdą liczbę wejściową — dla 12 i 18 jest to 6, a nie 12 czy 18, mimo że obie te liczby również dzielą bez reszty co najmniej jedną z liczb wejściowych.
• Ręczne wypisywanie każdego czynnika dla dużych liczb zamiast użycia algorytmu Euklidesa. Jak opisano powyżej, staje się to powolne i podatne na błędy w miarę wzrostu liczb — algorytm Euklidesa używany przez ten kalkulator znajduje tę samą odpowiedź w zaledwie kilku krokach niezależnie od rozmiaru.
• Mnożenie dwóch liczb w celu uzyskania NWW bez wcześniejszego dzielenia przez NWD. Jak opisano powyżej, proste mnożenie daje poprawny NWW tylko wtedy, gdy obie liczby są względnie pierwsze (NWD równy 1) — dla liczb mających wspólny czynnik, pominięcie dzielenia przez NWD daje wielokrotność prawdziwego NWW, a nie sam NWW.

Warto wiedzieć

• Uproszczenie ułamka do najprostszej postaci to dokładnie obliczenie NWD — Kalkulator ułamków upraszcza ułamki, używając tego samego NWD, który ten kalkulator oblicza bezpośrednio.
• Znalezienie wspólnego mianownika do dodawania lub odejmowania ułamków to dokładnie obliczenie NWW — ta sama zależność w drugą stronę.
• Kalkulator rozkładu na czynniki pierwsze i Kalkulator proporcji opierają się na tej samej idei wspólnego czynnika, tylko z innej perspektywy — jeden rozkłada liczbę na jej czynniki pierwsze, drugi upraszcza proporcję do najprostszej postaci całkowitej.