Najmniejsza wspólna wielokrotność

Najmniejsza wspólna wielokrotność (NWW)

Najmniejsza wspólna wielokrotność (NWW) to najmniejsza liczba naturalna, która jest dzielnikiem każdej z podanych liczb naturalnych. Oznaczana jest symbolem $NWW(a\_1,\; \backslash dots,a\_n)$. Przykładowo, dla liczb 15 i 240 NWW wynosi 240, a dla 192 i 348 – 5568.

Właściwości NWW

• Zmiana kolejności argumentów nie wpływa na wartość NWW.
• Jeśli największy wspólny dzielnik (NWD) każdej pary liczb wynosi 1, NWW jest równa ich iloczynowi: $\backslash forall\_\{i\; \backslash neq\; j\}\; NWD(a\_i,\; a\_j)=1\; \backslash iff\; NWW(a\_1,\; a\_2,\; \backslash dots,\; a\_n)=\backslash prod\_\{i=1\}^n\; a\_i;$
• NWW mieści się w przedziale od największej liczby do iloczynu liczb: $\backslash max(a\_1,\backslash dots,a\_n)\backslash leqslant\; NWW(a\_1,\backslash dots,a\_n)\backslash leqslant\; a\_1\; \backslash cdot\; a\_2\; \backslash cdot\; \backslash ldots\; \backslash cdot\; a\_n;$
• Można sprowadzić obliczenie NWW zbioru liczb do wyznaczenia NWW pary: $NWW(a\_1,\backslash dots,a\_n,\; b\_1,\backslash dots,b\_m)=NWW\backslash left(NWW(a\_1,\backslash dots,a\_n),NWW(b\_1,\backslash dots,b\_m)\backslash right);$
• Związek z NWD: $NWW(a,b)=\backslash frac\{ab\}\{NWD(a,b)\}.$

Algorytmy wyznaczania NWW

Ogólny algorytm

Algorytm znajdowania NWW można opisać jako:
$NWW(a\_1,\; a\_2)=\backslash frac\{a\_1\; a\_2\}\{NWD(a\_1,a\_2)\}$
$NWW(a\_1,\; a\_2,\; \backslash dots,\; a\_n)=NWW(a\_1,\; NWW(a\_2,\; a\_3,\; \backslash dots,\; a\_n)$

Metoda rozkładu na czynniki pierwsze

Znajdowanie NWW polega na dwóch krokach:

1. Rozkład liczb na czynniki pierwsze.
2. NWW to iloczyn wszystkich czynników, gdzie każdy czynnik występuje tyle razy, ile w rozkładzie, w którym pojawił się najwięcej razy.

Przykład dla NWW liczb 42 i 56:

$NWW(42,56)\; =\; 2^3\; \backslash cdot\; 3^1\; \backslash cdot\; 7^1\; =\; 168$

Przykład dla NWW liczb 192 i 348:

$NWW(192,348)\; =\; 2^6\; \backslash cdot\; 3^1\; \backslash cdot\; 29^1\; =\; 5568$

Podsumowanie

Najmniejsza wspólna wielokrotność jest kluczowym pojęciem w teorii liczb, umożliwiającym analizę i obliczenia związane z wielokrotnościami liczb naturalnych. Istnieje wiele metod jej obliczania, w tym algorytmy rekurencyjne oraz metoda rozkładu na czynniki pierwsze.