Najmniejsza wspólna wielokrotność

Najmniejsza wspólna wielokrotność dwóch lub więcej liczb naturalnych ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ – najmniejsza liczba naturalna ze zbioru wszystkich liczb naturalnych, których dzielnikiem jest każda z liczb ${\displaystyle a_{1},\dots ,a_{n}}$ i na przykład dla liczb 15 i 240 jest to liczba 240, a dla liczb 192 i 348 – liczba 5568. Najmniejszą wspólną wielokrotność oznacza się często symbolem ${\displaystyle NWW(a_{1},\dots ,a_{n})}$^[1].

Ogólniej, najmniejszą wspólną wielokrotność można określić w dowolnym pierścieniu całkowitym.

Właściwości NWW

• zmiana kolejności argumentów NWW nie zmienia jej wartości;
• jeżeli największy wspólny dzielnik każdej pary z ciągu liczb wynosi 1 (są parami względnie pierwsze), to najmniejszą ich wspólną wielokrotnością jest ich iloczyn

${\displaystyle \forall _{i\neq j}NWD(a_{i},a_{j})=1\iff NWW(a_{1},a_{2},\dots ,a_{n})=\prod _{i=1}^{n}a_{i};}$

• NWW należy do domkniętego przedziału od największej z liczb do ich iloczynu

${\displaystyle \max(a_{1},\dots ,a_{n})\leqslant NWW(a_{1},\dots ,a_{n})\leqslant a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n};}$

• sprowadzenia obliczenia NWW zbioru liczb do wyznaczenia NWW pary liczb

${\displaystyle NWW(a_{1},\dots ,a_{n},b_{1},\dots ,b_{m})=NWW\left(NWW(a_{1},\dots ,a_{n}),NWW(b_{1},\dots ,b_{m})\right);}$

• związane z NWD i prawdziwe dla pary liczb – dla więcej niż dwóch liczb analogiczna zależność jest na ogół nieprawdziwa

${\displaystyle NWW(a,b)={\frac {ab}{NWD(a,b)}}.}$

Stosując ostatnią właściwość można sprowadzić obliczenie NWW do obliczenia NWD, który z kolei można znaleźć na przykład korzystając z algorytmu Euklidesa lub dla niewielkich liczb korzystając z ich rozkładu na czynniki pierwsze.

Algorytmy wyznaczania NWW

Ogólny algorytm

Algorytm znajdowania NWW dowolnej ilości liczb całkowitych można opisać następującą zależnością rekurencyjną:

${\displaystyle NWW(a_{1},a_{2})={\frac {a_{1}a_{2}}{NWD(a_{1},a_{2})}}}$

${\displaystyle NWW(a_{1},a_{2},\dots ,a_{n})=NWW(a_{1},NWW(a_{2},a_{3},\dots ,a_{n}))}$

Metoda (szkolna) poprzez rozkład na czynniki pierwsze

Znajdowanie NWW odbywa się w dwóch krokach:

1. Dokonujemy rozkładu liczb, dla których szukamy NWW, na czynniki pierwsze.
2. NWW jest równa iloczynowi wszystkich czynników pierwszych wszystkich liczb, ale tak, że dany czynnik pierwszy w iloczynie występuje tyle razy ile razy występował w rozkładzie, w którym pojawił się najwięcej razy.

Rozkład liczby w tzw. „słupku” rozpoczyna się od czynnika 2 przez sprawdzenie, czy dana liczba dzieli się przez czynnik bez reszty. Jeśli dzieli się, obok wpisujemy czynnik to pod daną liczbą wpisujemy iloraz, jeśli nie, to sprawdzamy kolejne liczby pierwsze jako dzielniki. Czynność powtarzamy aż otrzymamy iloraz równy 1.

Wyznaczenie NWW liczb 42 i 56

${\displaystyle {\begin{matrix}42&|&2&\quad &56&|&\color {red}{2}\\21&|&\color {red}{3}&\quad &28&|&\color {red}{2}\\7&|&7&\quad &14&|&\color {red}{2}\\1&|&&\quad &7&|&\color {red}{7}\\&&&\quad &1&|\end{matrix}}}$

${\displaystyle {\begin{matrix}NWW(42,56)=2^{3}\cdot 3^{1}\cdot 7^{1}=168\end{matrix}}}$

Czynnik 2 wystąpił raz w pierwszym rozkładzie i trzy razy w drugim, więc w iloczynie występuje trzy razy, czynnik 3 wystąpił raz w pierwszym rozkładzie i zero razy w drugim, więc w iloczynie występuje raz, natomiast czynnik 7 wystąpił jeden raz w pierwszym i drugim rozkładzie, więc w iloczynie występuje też raz.

Wyznaczenie NWW liczb 192 i 348

${\displaystyle {\begin{matrix}192&|&\color {red}{2}&\quad &348&|&2\\96&|&\color {red}{2}&\quad &174&|&2\\48&|&\color {red}{2}&\quad &87&|&3\\24&|&\color {red}{2}&\quad &29&|&\color {red}{29}\\12&|&\color {red}{2}&\quad &1&|&\\6&|&\color {red}{2}&\quad &&&\\3&|&\color {red}{3}&\quad &&&\\1&|&&\quad &&&\end{matrix}}}$

${\displaystyle {\begin{matrix}NWW(192,348)=2^{6}\cdot 3^{1}\cdot 29^{1}=5568\end{matrix}}}$

Przypisy

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Least Common Multiple, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-02-02].
• Least common multiple (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-02-02].