Witajcie! Staram się udowodnić prawdziwość równości
\(\displaystyle{ v_p (n!) = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + {...} + \lfloor \frac{n}{p^k} \rfloor}\),
gdzie \(\displaystyle{ p \in \mathbb{P}, n \in \mathbb{N}}\), a \(\displaystyle{ k}\) jest taką liczbą naturalną, że \(\displaystyle{ p^k \le n \le p^{k+1}}\)
Niestety do tej pory nie znalazłem rozwiązania. Jakieś wskazówki?
Dowód wykładnika p-adycznego silni liczby naturalnej
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
Tak. Policzmy, ile jest liczb wśród \(\displaystyle{ 1,2\ldots n}\) podzielnych przez \(\displaystyle{ p}\). To proste: \(\displaystyle{ \left\lfloor \frac{n}{p}\right\rfloor}\). A teraz ile jest liczb wśród \(\displaystyle{ 1,2\ldots n}\) podzielnych przez \(\displaystyle{ p^{2}}\): nic prostszego, wychodzi \(\displaystyle{ \left\lfloor \frac{n}{p^{2}}\right\rfloor}\). I tak dalej. Pozostaje spostrzec, że dla liczby pierwszej \(\displaystyle{ p}\) mamy
\(\displaystyle{ v_{p}(n!)=\mbox{#} \left\{i\in \left\{1,2, \ldots n\right\}: p|i \right\}+\mbox{#} \left\{i\in \left\{1,2, \ldots n\right\}: p^{2}|i \right\}+\ldots+\mbox{#} \left\{i\in \left\{1,2, \ldots n\right\}: p^{k}|i \right\}}\), gdzie \(\displaystyle{ p^{k}\le n<p^{k+1}}\).
Jak poradzisz sobie z dowodem tego fakciku, to sprawa załatwiona (popatrzmy na rozkład \(\displaystyle{ n!}\) na czynniki pierwsze), jak nie, to go napiszę.
\(\displaystyle{ v_{p}(n!)=\mbox{#} \left\{i\in \left\{1,2, \ldots n\right\}: p|i \right\}+\mbox{#} \left\{i\in \left\{1,2, \ldots n\right\}: p^{2}|i \right\}+\ldots+\mbox{#} \left\{i\in \left\{1,2, \ldots n\right\}: p^{k}|i \right\}}\), gdzie \(\displaystyle{ p^{k}\le n<p^{k+1}}\).
Jak poradzisz sobie z dowodem tego fakciku, to sprawa załatwiona (popatrzmy na rozkład \(\displaystyle{ n!}\) na czynniki pierwsze), jak nie, to go napiszę.
-
- Użytkownik
- Posty: 133
- Rejestracja: 27 lip 2019, o 22:19
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 52 razy
- Pomógł: 15 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
Teraz rzeczywiście rozwiązanie wydaje się oczywiste, chociaż trudno ubrać to w jakiś rozsądnie brzmiący dowód.
Niech \(\displaystyle{ p}\) oznacza dowolną liczbę pierwszą, a \(\displaystyle{ n}\) dowolną liczbę naturalną dodatnią (dla uproszczenia pomińmy zero).
\(\displaystyle{ v_p (n!) = v_p (1 \cdot 2 \cdot 3 \cdot {...} \cdot n) = v_p (1) + v_p (2) + {...} + v_p (n)}\)
Wśród liczb \(\displaystyle{ 1, 2, 3, {...}, n}\) znajduje się dokładnie \(\displaystyle{ \left\lfloor \frac{n}{p}\right\rfloor}\) liczb podzielnych przez \(\displaystyle{ p}\). Niech \(\displaystyle{ k \in \mathbb{N_{+}}}\). Zauważmy, że wśród liczb \(\displaystyle{ 1, 2, 3, {...}, n}\) znajduje się \(\displaystyle{ \left\lfloor \frac{n}{p^k}\right\rfloor}\) liczb podzielnych przez liczbę \(\displaystyle{ p^k}\). Jeśli \(\displaystyle{ p^k}\) dzieli pewną liczbę naturalną \(\displaystyle{ m}\), to także \(\displaystyle{ p^{k-1}}\) dzieli liczbę \(\displaystyle{ m}\) dla dowolnego \(\displaystyle{ k}\) należącego do zbioru liczb naturalnych dodatnich. Stąd wynika zawieranie się zbiorów
\(\displaystyle{ \lbrace x: p^k|x, \ x \in A \rbrace \subseteq \lbrace x: p^{k-1}|x, \ x \in A \rbrace \subseteq {...} \subseteq \lbrace x: p|x, \ x \in A \rbrace}\), gdzie \(\displaystyle{ A = \lbrace 1, 2, {...}, n \rbrace}\)
I tutaj pojawia się kłopot ze sformułowaniem dowodu. Myślę jednak, że dzięki Twojej radzie, Premislavie, rozumiem, jak to działa; wyznaczamy wartość wykładnika liczby \(\displaystyle{ p}\) w rozkładzie liczby \(\displaystyle{ n}\) na czynniki pierwsze, po kolei dodając moc zbiorów zawierających te z liczb \(\displaystyle{ 1, 2, {...}, n}\), które są podzielne przez kolejne potęgi liczby \(\displaystyle{ p}\). Zaczynamy od pierwszej potęgi i później „schodkowo” bierzemy pod uwagę te, które dzielą się również przez następne potęgi liczby \(\displaystyle{ p}\). W ten sposób, jeśli w tym zbiorze jest pewna liczba \(\displaystyle{ m}\), dla której \(\displaystyle{ v_p (m) = i}\), to uwzględnimy ją \(\displaystyle{ i}\) razy, co da nam jej wykładnik. Prosiłbym jednak o Twoje rozwiązanie, z chęcią je zobaczę.
Niech \(\displaystyle{ p}\) oznacza dowolną liczbę pierwszą, a \(\displaystyle{ n}\) dowolną liczbę naturalną dodatnią (dla uproszczenia pomińmy zero).
\(\displaystyle{ v_p (n!) = v_p (1 \cdot 2 \cdot 3 \cdot {...} \cdot n) = v_p (1) + v_p (2) + {...} + v_p (n)}\)
Wśród liczb \(\displaystyle{ 1, 2, 3, {...}, n}\) znajduje się dokładnie \(\displaystyle{ \left\lfloor \frac{n}{p}\right\rfloor}\) liczb podzielnych przez \(\displaystyle{ p}\). Niech \(\displaystyle{ k \in \mathbb{N_{+}}}\). Zauważmy, że wśród liczb \(\displaystyle{ 1, 2, 3, {...}, n}\) znajduje się \(\displaystyle{ \left\lfloor \frac{n}{p^k}\right\rfloor}\) liczb podzielnych przez liczbę \(\displaystyle{ p^k}\). Jeśli \(\displaystyle{ p^k}\) dzieli pewną liczbę naturalną \(\displaystyle{ m}\), to także \(\displaystyle{ p^{k-1}}\) dzieli liczbę \(\displaystyle{ m}\) dla dowolnego \(\displaystyle{ k}\) należącego do zbioru liczb naturalnych dodatnich. Stąd wynika zawieranie się zbiorów
\(\displaystyle{ \lbrace x: p^k|x, \ x \in A \rbrace \subseteq \lbrace x: p^{k-1}|x, \ x \in A \rbrace \subseteq {...} \subseteq \lbrace x: p|x, \ x \in A \rbrace}\), gdzie \(\displaystyle{ A = \lbrace 1, 2, {...}, n \rbrace}\)
I tutaj pojawia się kłopot ze sformułowaniem dowodu. Myślę jednak, że dzięki Twojej radzie, Premislavie, rozumiem, jak to działa; wyznaczamy wartość wykładnika liczby \(\displaystyle{ p}\) w rozkładzie liczby \(\displaystyle{ n}\) na czynniki pierwsze, po kolei dodając moc zbiorów zawierających te z liczb \(\displaystyle{ 1, 2, {...}, n}\), które są podzielne przez kolejne potęgi liczby \(\displaystyle{ p}\). Zaczynamy od pierwszej potęgi i później „schodkowo” bierzemy pod uwagę te, które dzielą się również przez następne potęgi liczby \(\displaystyle{ p}\). W ten sposób, jeśli w tym zbiorze jest pewna liczba \(\displaystyle{ m}\), dla której \(\displaystyle{ v_p (m) = i}\), to uwzględnimy ją \(\displaystyle{ i}\) razy, co da nam jej wykładnik. Prosiłbym jednak o Twoje rozwiązanie, z chęcią je zobaczę.
- Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
A czemu w ogóle liczby \(\displaystyle{ p}\)-adyczne w tytule?
Równość, o której mowa, to wzór Legendre'a. Szukając pod tym hasłem znajdziesz z pewnością wiele dowodów, chociażby
Równość, o której mowa, to wzór Legendre'a. Szukając pod tym hasłem znajdziesz z pewnością wiele dowodów, chociażby
-
- Użytkownik
- Posty: 609
- Rejestracja: 10 lis 2009, o 22:39
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Pomógł: 135 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
Gdzie widzisz liczby p-adyczne w tytule? Może tytuł ma jakąś część niewidoczną dla zwykłych śmiertelników?
- Gosda
- Użytkownik
- Posty: 340
- Rejestracja: 29 cze 2019, o 19:46
- Płeć: Mężczyzna
- Lokalizacja: Oulu
- Podziękował: 42 razy
- Pomógł: 60 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
Widzę wykładnik \(\displaystyle{ p}\)-adyczny, czyli termin blisko związany z liczbami. Zapytałem z ciekawości Pamiętam, że sam w liceum na którymś sprawdzianie miałem to zadanie w wersji "iloma zerami kończy się silnia (jakaś duża liczba)?", więc to nie jest tak, że się go nie da inaczej sformułować.
-
- Użytkownik
- Posty: 133
- Rejestracja: 27 lip 2019, o 22:19
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 52 razy
- Pomógł: 15 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
Określiłem to, jak widać, nieprecyzyjnie, chodzi w końcu o wykładnik \(\displaystyle{ p}\)-adyczny silni z liczby naturalnej.
Za link bardzo dziękuję. Szukałem wcześniej, ale nie udało mi się znaleźć, chyba używałem niepasujących fraz.
- Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Dowód wykładnika p-adycznego silni liczby naturalnej
Po tym, co tu napisałeś, ja nie mam nic do dodania. Dość podobnie zresztą dowodzą w linku…Thingoln pisze: ↑4 paź 2019, o 00:01
I tutaj pojawia się kłopot ze sformułowaniem dowodu. Myślę jednak, że dzięki Twojej radzie, Premislavie, rozumiem, jak to działa; wyznaczamy wartość wykładnika liczby \(\displaystyle{ p}\) w rozkładzie liczby \(\displaystyle{ n}\) na czynniki pierwsze, po kolei dodając moc zbiorów zawierających te z liczb \(\displaystyle{ 1, 2, {...}, n}\), które są podzielne przez kolejne potęgi liczby \(\displaystyle{ p}\). Zaczynamy od pierwszej potęgi i później „schodkowo” bierzemy pod uwagę te, które dzielą się również przez następne potęgi liczby \(\displaystyle{ p}\). W ten sposób, jeśli w tym zbiorze jest pewna liczba \(\displaystyle{ m}\), dla której \(\displaystyle{ v_p (m) = i}\), to uwzględnimy ją \(\displaystyle{ i}\) razy, co da nam jej wykładnik. Prosiłbym jednak o Twoje rozwiązanie, z chęcią je zobaczę.