I OM - B - Zadanie 18

Podać sposób wyznaczenia najmniejszej wspólnej wielokrotności liczb naturalnych $ 1, 2, 3, \dots , n $.

Rozwiązanie

Niechaj $ p $ oznacza największą liczbę pierwszą zawartą w danym ciągu liczb naturalnych $ 1, 2, 3, \dots, n $. Jeżeli np. $ n=50 $, to $ p $ oznacza liczbę plerwszą 47.

Aby wyznaczyć najmniejszą wspólną wielokrotność liczb naturalnych $ 1, 2, 3, \dots, n $, należałoby rozłożyć wszystkie te liczby na czynniki pierwsze, a następnie, utworzyć iloczyn

\[<br />
M = 2^{\alpha} \cdot 3^{\beta} \cdot 5^{\gamma} \cdot \dots \cdot p^{\mu},<br />
\]

którego czynnikami są najwyższe potęgi kolejnych liczb pierwszych $ 2, 3, 5, \dots  $ aż do $ p $, występujące w rozkładach liczb $ 1, 2, 3, \dots , n $ na czynniki pierwsze.

Możemy jednak wykładniki $ \alpha, beta, \gamma, \dots, \mu $ znaleźć w sposób prostszy, bez rozkładania danych liczb na czynniki pierwsze.

Aby wyznaczyć wykładnik $ \alpha $ przy liczbie pierwszej 2, wypisujemy kolejne potęgi liczby 2:

\[<br />
2^1 = 2, 2^2 = 4, 2^3 = 8, 264 = 16, 2^5 = 32, 2^6 = 64, 2^7 = 128, \dots<br />
\]

i znajdujemy taki wykładnik $ \alpha $, żeby były spełnione nierówności

\[<br />
2^{\alpha} \leq n < 2^{\alpha+1}<br />
\]

Jeżeli np. $ n = 50 $, to należy wziąć $ a = 5 $.

Następnie w ciągu kolejnych potęg liczby pierwszej 3:

\[<br />
3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243, \dots<br />
\]

znajdujemy taki wykładnik $ \beta $, żeby były spełnione nierówności

\[<br />
3^{\beta} \leq n <3^{\beta + 1}<br />
\]

Np. dla $ n = 50 $ znajdziemy $ \beta = 3 $.

Tak postępujemy dalej, przy czym będziemy otrzymywali wykładniki $ \alpha, beta, \gamma, \dots $ coraz mniejsze, aż dojdziemy do takiej liczby pierwszej $ h $, dla której zachodzą nierówności

\[<br />
h \leq n < h^2<br />
\]

Zaczynając od tej liczby pierwszej $ h $ wszystkie czynniki pierwsze będą w iloczynie $ M $ występowały z wykładnikiem 1.

Jeżeli np. weźmiemy $ n = 50 $, to

\[<br />
M = 2^5 \cdot 3^3 \cdot 5^2 \cdot 7^2 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29 \cdot 31 \cdot 37 \cdot 41 \cdot 43 \cdot 47<br />
\]

Komentarze

Dodaj nową odpowiedź