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

$ M = 2^{\alpha} \cdot 3^{\beta} \cdot 5^{\gamma} \cdot \dots \cdot p^{\mu}, $

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:

$ 2^1 = 2, 2^2 = 4, 2^3 = 8, 264 = 16, 2^5 = 32, 2^6 = 64, 2^7 = 128, \dots $

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

$ 2^{\alpha} \leq n < 2^{\alpha+1} $

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

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

$ 3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243, \dots $

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

$ 3^{\beta} \leq n <3^{\beta + 1} $

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