Niech \(\displaystyle{ \mu_p (n)}\) będzie największym wykładnikiem \(\displaystyle{ k}\), takim, że \(\displaystyle{ p^k}\) dzieli \(\displaystyle{ n}\) (\(\displaystyle{ p}\)-liczba pierwsza). Pokaż, że \(\displaystyle{ \mu_p (n!)}\) jest równe sumie części całkowitych liczb \(\displaystyle{ \frac{n}{p}, \frac{n}{p^2}, \frac{n}{p^3},... }\) i tak dalej (liczba składników niezerowych jest oczywiście skończona).
Jak to zrobić? Sprawdziłem to dla paru liczb i widzę, że się zgadza, ale jak to udowodnić? Może mi ktoś pomóc?
Największy wykładnik
-
Janusz Tracz
- Użytkownik
- Posty: 4071
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1393 razy
Re: Największy wykładnik
Lemat: W zbiorze \(\displaystyle{ \left\{ 1,2,...,n\right\} }\) znajduje się \(\displaystyle{ \left\lfloor n/k \right\rfloor}\) liczb podzielnych przez \(\displaystyle{ k}\).
Jako, że \(\displaystyle{ n!=1 \cdot 2 \cdot ... \cdot n}\) to w celu wyznaczenia \(\displaystyle{ \mu_p(n!)}\) wystarczy policzyć ile razy \(\displaystyle{ n!}\) dzieli się przez \(\displaystyle{ p}\). W zbiorze \(\displaystyle{ \left\{ 1,2,...,n\right\} }\) znajduje się \(\displaystyle{ \left\lfloor n/p \right\rfloor}\) licz podzielnych przez \(\displaystyle{ p}\). Jednak niektóre z tych liczb dzieją się przez \(\displaystyle{ p^2}\), takich liczb jest \(\displaystyle{ \left\lfloor n/p^2\right\rfloor}\). Ale jeszcze niektóre dzielą się przez \(\displaystyle{ p^3}\) i takich jest \(\displaystyle{ \left\lfloor n/p^3\right\rfloor}\) itd.
Uwaga: wydawać by się mogło, że niektóre liczby zliczamy wielokrotnie. Ale tak nie jest. Jeśli jakaś liczba \(\displaystyle{ k<n}\) dzieli się przez \(\displaystyle{ p^3}\) (ale przez \(\displaystyle{ p^4}\) już nie) to zostanie ona zliczona podczas podczas brania \(\displaystyle{ \left\lfloor n/p^1\right\rfloor}\),\(\displaystyle{ \left\lfloor n/p^2\right\rfloor}\) oraz \(\displaystyle{ \left\lfloor n/p^3\right\rfloor}\). Ale to właśnie dobrze. Bo ją trzeba policzyć tak jakby \(\displaystyle{ 3}\) razy bo ona właśnie wnosi \(\displaystyle{ 3}\) bo ogólnej liczb \(\displaystyle{ \mu_p(n!)}\). Analogiczny argument działa dla innych wykładników niż \(\displaystyle{ 3}\).
Jako, że \(\displaystyle{ n!=1 \cdot 2 \cdot ... \cdot n}\) to w celu wyznaczenia \(\displaystyle{ \mu_p(n!)}\) wystarczy policzyć ile razy \(\displaystyle{ n!}\) dzieli się przez \(\displaystyle{ p}\). W zbiorze \(\displaystyle{ \left\{ 1,2,...,n\right\} }\) znajduje się \(\displaystyle{ \left\lfloor n/p \right\rfloor}\) licz podzielnych przez \(\displaystyle{ p}\). Jednak niektóre z tych liczb dzieją się przez \(\displaystyle{ p^2}\), takich liczb jest \(\displaystyle{ \left\lfloor n/p^2\right\rfloor}\). Ale jeszcze niektóre dzielą się przez \(\displaystyle{ p^3}\) i takich jest \(\displaystyle{ \left\lfloor n/p^3\right\rfloor}\) itd.
Uwaga: wydawać by się mogło, że niektóre liczby zliczamy wielokrotnie. Ale tak nie jest. Jeśli jakaś liczba \(\displaystyle{ k<n}\) dzieli się przez \(\displaystyle{ p^3}\) (ale przez \(\displaystyle{ p^4}\) już nie) to zostanie ona zliczona podczas podczas brania \(\displaystyle{ \left\lfloor n/p^1\right\rfloor}\),\(\displaystyle{ \left\lfloor n/p^2\right\rfloor}\) oraz \(\displaystyle{ \left\lfloor n/p^3\right\rfloor}\). Ale to właśnie dobrze. Bo ją trzeba policzyć tak jakby \(\displaystyle{ 3}\) razy bo ona właśnie wnosi \(\displaystyle{ 3}\) bo ogólnej liczb \(\displaystyle{ \mu_p(n!)}\). Analogiczny argument działa dla innych wykładników niż \(\displaystyle{ 3}\).