Podzielność silni
-
- 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
Podzielność silni
Witajcie. Mam kolejne zadanie z teorii liczb do rozwiązania. Na początek podam treść zadania i napiszę, co udało mi się do tej pory zrobić.
Dowieść, że \(\displaystyle{ 2^n \nmid n!}\) dla \(\displaystyle{ n \in \mathbb{N_{+}}}\).
\(\displaystyle{ 2^n \nmid n! \Leftrightarrow n \nmid v_p (n)}\)
Ze wzoru Legendre'a wynika również, że jest to równoważne
\(\displaystyle{ n \nmid \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor \ \ (1)}\),
gdzie \(\displaystyle{ 2^k \le n < 2^{k+1}}\) i \(\displaystyle{ k \in \mathbb{N_{+}}}\).
I tutaj pojawia się moje pytanie. Czy można uzasadnić \(\displaystyle{ (1)}\) w ten sposób?
Weźmy pod uwagę ciąg geometryczny \(\displaystyle{ (a_m)}\) określony wzorem \(\displaystyle{ a_m = \frac{n}{2} \cdot \left(\frac{1}{2}\right)^{m-1}}\). Oznaczmy jego iloraz jako \(\displaystyle{ q}\). Oczywiście jest on równy \(\displaystyle{ \frac{1}{2}}\), a więc \(\displaystyle{ |q| < 1}\). Wynika z tego, że istnieje skończona wartość szeregu \(\displaystyle{ \sum_{m=1}^{ \infty} a_m}\) równa \(\displaystyle{ a_1 \cdot \frac{1}{1-q} = \frac{n}{2} \cdot \frac{1}{1-\left(\frac{1}{2}\right)} = \frac{n}{2} \cdot \frac{1}{\frac{1}{2}} = n}\).
Dla dowolnej liczby naturalnej dodatniej \(\displaystyle{ t}\) wyraz \(\displaystyle{ a_t}\) jest liczbą dodatnią. Stąd suma \(\displaystyle{ t}\) pierwszych wyrazów tego ciągu jest funkcją ściśle rosnącą. Zauważmy również, że dla dowolnej liczby rzeczywistej \(\displaystyle{ x}\) zachodzi \(\displaystyle{ x-1 < \left\lfloor x \right\rfloor \le x}\), więc także
\(\displaystyle{ \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor \le \frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^k}}\)
Dla dowolnej liczby naturalnej dodatniej \(\displaystyle{ t}\) zachodzi więc
\(\displaystyle{ 0 \le \sum_{m=1}^{t} \left\lfloor a_m \right\rfloor \le \sum_{m=1}^{t} a_m < \sum_{m=1}^{\infty} a_m = n}\),
więc \(\displaystyle{ (1)}\) jest spełnione, bo większa liczba naturalna nie może dzielić mniejszej różnej od zera.
Dowieść, że \(\displaystyle{ 2^n \nmid n!}\) dla \(\displaystyle{ n \in \mathbb{N_{+}}}\).
\(\displaystyle{ 2^n \nmid n! \Leftrightarrow n \nmid v_p (n)}\)
Ze wzoru Legendre'a wynika również, że jest to równoważne
\(\displaystyle{ n \nmid \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor \ \ (1)}\),
gdzie \(\displaystyle{ 2^k \le n < 2^{k+1}}\) i \(\displaystyle{ k \in \mathbb{N_{+}}}\).
I tutaj pojawia się moje pytanie. Czy można uzasadnić \(\displaystyle{ (1)}\) w ten sposób?
Weźmy pod uwagę ciąg geometryczny \(\displaystyle{ (a_m)}\) określony wzorem \(\displaystyle{ a_m = \frac{n}{2} \cdot \left(\frac{1}{2}\right)^{m-1}}\). Oznaczmy jego iloraz jako \(\displaystyle{ q}\). Oczywiście jest on równy \(\displaystyle{ \frac{1}{2}}\), a więc \(\displaystyle{ |q| < 1}\). Wynika z tego, że istnieje skończona wartość szeregu \(\displaystyle{ \sum_{m=1}^{ \infty} a_m}\) równa \(\displaystyle{ a_1 \cdot \frac{1}{1-q} = \frac{n}{2} \cdot \frac{1}{1-\left(\frac{1}{2}\right)} = \frac{n}{2} \cdot \frac{1}{\frac{1}{2}} = n}\).
Dla dowolnej liczby naturalnej dodatniej \(\displaystyle{ t}\) wyraz \(\displaystyle{ a_t}\) jest liczbą dodatnią. Stąd suma \(\displaystyle{ t}\) pierwszych wyrazów tego ciągu jest funkcją ściśle rosnącą. Zauważmy również, że dla dowolnej liczby rzeczywistej \(\displaystyle{ x}\) zachodzi \(\displaystyle{ x-1 < \left\lfloor x \right\rfloor \le x}\), więc także
\(\displaystyle{ \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor \le \frac{n}{2} + \frac{n}{2^2} + \cdots + \frac{n}{2^k}}\)
Dla dowolnej liczby naturalnej dodatniej \(\displaystyle{ t}\) zachodzi więc
\(\displaystyle{ 0 \le \sum_{m=1}^{t} \left\lfloor a_m \right\rfloor \le \sum_{m=1}^{t} a_m < \sum_{m=1}^{\infty} a_m = n}\),
więc \(\displaystyle{ (1)}\) jest spełnione, bo większa liczba naturalna nie może dzielić mniejszej różnej od zera.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podzielność silni
Hmm? No nie bardzo. Trochę pomieszałeś. Raczej dla dowolnej liczby pierwszej \(\displaystyle{ p}\) będzie \(\displaystyle{ p^{n}\nmid n!\Leftrightarrow v_{p}(n!)<n}\) i dalej wszak wyliczasz i szacujesz z góry \(\displaystyle{ v_{2}(n!)}\).Thingoln pisze:\(\displaystyle{ 2^n \nmid n! \Leftrightarrow n \nmid v_p (n)}\)
I znów, dalej:
No nie, jest to równoważne nierówności \(\displaystyle{ n> \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor}\), gdzie \(\displaystyle{ 2^{k}\le n<2^{k+1}}\).Thingoln pisze:Ze wzoru Legendre'a wynika również, że jest to równoważne
\(\displaystyle{ n \nmid \left\lfloor \frac{n}{2}\right\rfloor + \left\lfloor \frac{n}{2^2}\right\rfloor + \cdots + \left\lfloor \frac{n}{2^k}\right\rfloor }\)
gdzie \(\displaystyle{ 2^k \le n < 2^{k+1}}\) i \(\displaystyle{ k\in \NN_{+}}\)
Samo szacowanie z góry \(\displaystyle{ v_{2}(n!)}\) jest natomiast całkowicie poprawne.
-
- 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: Podzielność silni
Aj, rzeczywiście tutaj się zagapiłem. Oczywiście zgadzam się. W takim razie jest to poprawne rozwiązanie po naniesieniu Twoich poprawek?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podzielność silni
Nie żebym był specjalistą od teorii liczb, ale moim zdaniem ten sposób jest dla niej bardzo typowy. Trudno mi sobie wyobrazić inne rozwiązanie (może mam małą wyobraźnię ), ale też bym chętnie takie zobaczył, bo inaczej nie umiem.
-
- Użytkownik
- Posty: 171
- Rejestracja: 26 lut 2016, o 17:32
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 14 razy
Re: Podzielność silni
Można zastosować indukcję matematyczną. Rozłóżmy silnię na iloczyn.
\(\displaystyle{ n! = n!! \cdot (n-1)!!}\)
Jeżeli \(\displaystyle{ n}\) jest nieparzyste to \(\displaystyle{ n!!}\) nie dzieli się przez \(\displaystyle{ 2}\) i interesuje nas tylko \(\displaystyle{ (n-1)!!}\).
Jeżeli \(\displaystyle{ n}\) jest parzyste to zapisujemy \(\displaystyle{ n!! = 2^{n/2} \cdot (n/2)! }\)
Wstawiając do wcześniejszej zależności dostajemy tezę dla mniejszego \(\displaystyle{ n}\) :
\(\displaystyle{ 2^{n/2} \nmid (n/2)!}\).
Kontynuując dalej dostajemy sprzeczność:
\(\displaystyle{ 2^1 \nmid 1!}\).
\(\displaystyle{ n! = n!! \cdot (n-1)!!}\)
Jeżeli \(\displaystyle{ n}\) jest nieparzyste to \(\displaystyle{ n!!}\) nie dzieli się przez \(\displaystyle{ 2}\) i interesuje nas tylko \(\displaystyle{ (n-1)!!}\).
Jeżeli \(\displaystyle{ n}\) jest parzyste to zapisujemy \(\displaystyle{ n!! = 2^{n/2} \cdot (n/2)! }\)
Wstawiając do wcześniejszej zależności dostajemy tezę dla mniejszego \(\displaystyle{ n}\) :
\(\displaystyle{ 2^{n/2} \nmid (n/2)!}\).
Kontynuując dalej dostajemy sprzeczność:
\(\displaystyle{ 2^1 \nmid 1!}\).
Ostatnio zmieniony 5 paź 2019, o 19:04 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Podzielność silni
Dla liczby pierwszej \(\displaystyle{ p}\) i \(\displaystyle{ n\in \ZZ\setminus \left\{0\right\}}\) mówimy, że \(\displaystyle{ v_{p}(n)=x}\), gdy
\(\displaystyle{ p^{x}|n, \ p^{x+1} \nmid n}\).
\(\displaystyle{ p^{x}|n, \ p^{x+1} \nmid n}\).
-
- 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: Podzielność silni
pasmanie, dzięki za Twoje rozwiązanie! Wygląda ciekawie, chociaż na końcu chyba zamiast sprzeczności jest spełnienie tezy. W każdym razie świetnie poznać jeszcze inne podejście do tego zadania.
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: Podzielność silni
To ja zaproponuję coś swojego.
Zauważmy, że aby \(\displaystyle{ 2^n}\) dzieliło \(\displaystyle{ n!}\), to \(\displaystyle{ n!}\) musi mieć w swoim rozkładzie conajmniej \(\displaystyle{ n}\) dwójek.
Weźmy \(\displaystyle{ n}\) kolejnych liczb i oszacujmy ile łącznie dwójek w nich występuje.
Oczywistym oszacowaniem z góry jest: \(\displaystyle{ \frac{n}{2} + \frac{n}{2^2}+ \frac{n}{2^3}+ \frac{n}{2^4} + \dots + \frac{n}{2^n}}\)
Wystarczy więc wykazać, że:
\(\displaystyle{ \frac{n}{2} + \frac{n}{2^2}+ \frac{n}{2^3}+ \frac{n}{2^4} + \dots + \frac{n}{2^n} \ge n}\)
Po podzieleniu obustronnie przez \(\displaystyle{ n}\) mamy \(\displaystyle{ \frac{1}{2} + \frac{1}{2^2}+ \frac{1}{2^3}+ \frac{1}{2^4} + \dots + \frac{1}{2^n} \ge 1}\)
A to jest sprzeczne, bo \(\displaystyle{ \sum_{n=1}^\infty \frac{1}{2^n} = 1.}\)
Zauważmy, że aby \(\displaystyle{ 2^n}\) dzieliło \(\displaystyle{ n!}\), to \(\displaystyle{ n!}\) musi mieć w swoim rozkładzie conajmniej \(\displaystyle{ n}\) dwójek.
Weźmy \(\displaystyle{ n}\) kolejnych liczb i oszacujmy ile łącznie dwójek w nich występuje.
Oczywistym oszacowaniem z góry jest: \(\displaystyle{ \frac{n}{2} + \frac{n}{2^2}+ \frac{n}{2^3}+ \frac{n}{2^4} + \dots + \frac{n}{2^n}}\)
Wystarczy więc wykazać, że:
\(\displaystyle{ \frac{n}{2} + \frac{n}{2^2}+ \frac{n}{2^3}+ \frac{n}{2^4} + \dots + \frac{n}{2^n} \ge n}\)
Po podzieleniu obustronnie przez \(\displaystyle{ n}\) mamy \(\displaystyle{ \frac{1}{2} + \frac{1}{2^2}+ \frac{1}{2^3}+ \frac{1}{2^4} + \dots + \frac{1}{2^n} \ge 1}\)
A to jest sprzeczne, bo \(\displaystyle{ \sum_{n=1}^\infty \frac{1}{2^n} = 1.}\)