Dowód wykładnika p-adycznego silni liczby naturalnej

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Thingoln
Użytkownik
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

Dowód wykładnika p-adycznego silni liczby naturalnej

Post autor: Thingoln »

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? :)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Dowód wykładnika p-adycznego silni liczby naturalnej

Post autor: Premislav »

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ę.
Thingoln
Użytkownik
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

Post autor: Thingoln »

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ę. :)
Awatar użytkownika
Gosda
Użytkownik
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

Post autor: Gosda »

A czemu w ogóle liczby \(\displaystyle{ p}\)-adyczne w tytule? :D

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
krl
Użytkownik
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

Post autor: krl »

Gosda pisze: 4 paź 2019, o 06:36 A czemu w ogóle liczby \(\displaystyle{ p}\)-adyczne w tytule?
Gdzie widzisz liczby p-adyczne w tytule? Może tytuł ma jakąś część niewidoczną dla zwykłych śmiertelników?
Awatar użytkownika
Gosda
Użytkownik
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

Post autor: Gosda »

Widzę wykładnik \(\displaystyle{ p}\)-adyczny, czyli termin blisko związany z liczbami. Zapytałem z ciekawości :D 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ć.
Thingoln
Użytkownik
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

Post autor: Thingoln »

Gosda pisze: 4 paź 2019, o 06:36 A czemu w ogóle liczby \(\displaystyle{ p}\)-adyczne w tytule? :D
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. :) :mrgreen:
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Dowód wykładnika p-adycznego silni liczby naturalnej

Post autor: Premislav »

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ę. :)
Po tym, co tu napisałeś, ja nie mam nic do dodania. Dość podobnie zresztą dowodzą w linku…
ODPOWIEDZ