przez 2 do której potęgi dzieli się x!

[Citizen]

Spotykam sie ze stwierdzeniami że np liczba \(\displaystyle{ 24!}\) dzieli sie przez \(\displaystyle{ 2^{22}}\)

Czy mógłby mi ktoś tak łopatologicznie wytłumaczyć jak obliczyć przez jakie \(\displaystyle{ 2^{n}}\) i jakie \(\displaystyle{ 5^{n}}\) dzielą się dowolne \(\displaystyle{ x!}\) ? Jak to obliczać?

Z góry dziękuje.-- 28 maja 2009, o 19:03 --

[jarzabek89]

dla przykładu niech będzie wyżej wymienione 24!
Jak wiadomo jest to 1*2*3....24
Wśród tych liczb wybierzmy same liczby parzystę \(\displaystyle{ 2\cdot4\cdot6\cdot8...24}\)
4 można zapisać jako \(\displaystyle{ 2\cdot2}\)
6 jak \(\displaystyle{ 2\cdot3}\)... itd.
\(\displaystyle{ 8=2\cdot2\cdot2}\) itd
Trzeba policzyć ilość takich dwójeczek.
Analogicznie do \(\displaystyle{ 5^{n}}\)
Zauważmy że\(\displaystyle{ 2\cdot5=10}\)
lub \(\displaystyle{ 5\cdot20=100}\)

[Citizen]

Mhm czyli przy 24! będzie \(\displaystyle{ 5^{4}}\), a np. przy 25! byłoby \(\displaystyle{ 5^{6}}\) tak?

[BettyBoo]

To wynika z następującego faktu:

Dla każdej liczby pierwszej p określamy funkcję \(\displaystyle{ \alpha_p:\mathbb{N}\to \mathbb{N}\cup\{0\}}\):
\(\displaystyle{ \forall\, n\in\mathbb{N}\qquad \alpha_p(n)=k \quad \mathrm{gdy} \quad p^k|n\ \wedge\ p^{k+1}\nmid n}\)

(czyli \(\displaystyle{ \alpha_p(n)}\) określa potęgę, z jaką liczba p występuje w rozkładzie liczby n na czynniki pierwsze)

Wówczas

\(\displaystyle{ \forall\,n\in\mathbb{N}\ \forall\,p\in\mathbb{P}\qquad \alpha_p(n!)=\sum_{i=1}^\infty \left[\frac{n}{p^i}\right],}\)

gdzie [x] oznacza największą liczbę całkowitą nieprzekraczającą x.

Pozdrawiam.

[Citizen]

Chyba wszystko jest ok, rozumiem dzięki, ale teraz pojawia się problem, że np przy 1000! ciężko liczyć to "na palcach" są do tego jakieś wzory? Jeżeli tylko z użyciem "\(\displaystyle{ \sum_{}^{}}\)" to czy mógłby ktoś mi je wytłumaczyć bo nie mam pojęcia jak z nich korzystać.

[kubek1]

W tym wzorze z sumą po prostu chodzi o to, że liczymy liczbę liczb od 1 do n podzielnych przez p, potem podzielnych przez p^2, przez p^3 itd. aż dojdziemy do zer. Sumując te liczby, otrzymamy to, co chcemy, a na tym polega suma przedstawiona przez BettyBoo

[BettyBoo]

Ale nawet dla 1000! da się łatwo sprawdzić na palcach, wystarczy doliczyć do \(\displaystyle{ 2^9}\) (bo \(\displaystyle{ 2^{10}=1024}\)).

Obliczamy największą potęgę liczby 2, która dzieli 1000! - to będzie \(\displaystyle{ \alpha_2(1000!)}\), czyli zgodnie ze wzorem


\(\displaystyle{ \alpha_2(1000!)=\sum_{i=1}^\infty \left[\frac{1000}{2^i}\right]=\left[\frac{1000}{2}\right]+\left[\frac{1000}{4}\right]+\left[\frac{1000}{8}\right]+\left[\frac{1000}{16}\right]+\left[\frac{1000}{32}\right]+\left[\frac{1000}{64}\right]+\left[\frac{1000}{128}\right]+\left[\frac{1000}{256}\right]+\left[\frac{1000}{512}\right]}\)

bo wszystkie pozostałe potęgi dwójki są już większe niż 1000, więc częscią całkowitą ilorazu będzie 0.


Pozdrawiam.

[Citizen]

Super, wszystko jasne. Wielkie dzięki! ;D