Podzielność liczby 2^2006!

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
BlueSky
Użytkownik
Użytkownik
Posty: 224
Rejestracja: 11 cze 2011, o 20:27
Płeć: Kobieta
Podziękował: 31 razy

Podzielność liczby 2^2006!

Post autor: BlueSky » 7 sie 2013, o 23:11

Wyznaczyć największą liczbę naturalną \(\displaystyle{ k}\) taką, że \(\displaystyle{ 2^k}\) dzieli liczbę \(\displaystyle{ 2^{2006}!}\).
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

Podzielność liczby 2^2006!

Post autor: Vax » 7 sie 2013, o 23:15

Skorzystaj z tego, że \(\displaystyle{ v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i}\right\rfloor}\)

BlueSky
Użytkownik
Użytkownik
Posty: 224
Rejestracja: 11 cze 2011, o 20:27
Płeć: Kobieta
Podziękował: 31 razy

Podzielność liczby 2^2006!

Post autor: BlueSky » 8 sie 2013, o 16:31

Niestety mało mi ta wskazówka mówi...

Awatar użytkownika
Vax
Użytkownik
Użytkownik
Posty: 2913
Rejestracja: 27 kwie 2010, o 22:07
Płeć: Mężczyzna
Lokalizacja: Biała Podlaska / Warszawa
Podziękował: 4 razy
Pomógł: 611 razy

Podzielność liczby 2^2006!

Post autor: Vax » 8 sie 2013, o 16:41

Nasze \(\displaystyle{ k}\) to po prostu \(\displaystyle{ \sum_{i=1}^{\infty}\left\lfloor\frac{2^{2006}}{2^i}\right\rfloor = 2^{2005}+2^{2004}+...+2+1 = 2^{2006}-1}\)

Marcinek665
Korepetytor
Korepetytor
Posty: 1824
Rejestracja: 11 sty 2007, o 20:12
Płeć: Mężczyzna
Lokalizacja: Katowice, Warszawa
Podziękował: 73 razy
Pomógł: 228 razy

Podzielność liczby 2^2006!

Post autor: Marcinek665 » 8 sie 2013, o 19:06

Jako że obydwa posty Vaxa są zupełnie niezrozumiałe w przypadku braku znajomości odpowiedniej aparatury, pozwolę sobie zabrać głos.

Chcemy w ogólności sprawdzić, z jakim wykładnikiem wchodzi liczba \(\displaystyle{ 2}\) w rozkład liczby \(\displaystyle{ n!}\) (potem wstawimy \(\displaystyle{ n=2^{2006}}\) i rozwiążemy zadanie). Liczbę taką oznaczamy jako \(\displaystyle{ v_2(n!)}\).

No ale w tym celu wystarczy sprawdzić ile jest liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), które dzielą się przez \(\displaystyle{ 2}\), potem przez \(\displaystyle{ 2^2}\), potem przez \(\displaystyle{ 2^3}\) itp, a następnie wszystko to po prostu zsumować. Liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ n}\), które dzielą się przez \(\displaystyle{ 2^k}\) jest oczywiście \(\displaystyle{ \left\lfloor\frac{n}{2^k}\right\rfloor}\), zatem wystarczy wysumować to od \(\displaystyle{ k=1}\) do nieskończoności. W rzeczywistości ta suma będzie oczywiście skończona, bo gdy licznik będzie mniejszy od mianownika, to w sumie występować będą same zera.

Liczymy więc: \(\displaystyle{ \sum_{i=1}^{\infty}\left\lfloor\frac{2^{2006}}{2^i}\right\rfloor = 2^{2005}+2^{2004}+...+2+1 = 2^{2006}-1}\)

i jest ok.

Awatar użytkownika
Ponewor
Moderator
Moderator
Posty: 2218
Rejestracja: 30 sty 2012, o 21:05
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 70 razy
Pomógł: 296 razy

Podzielność liczby 2^2006!

Post autor: Ponewor » 8 sie 2013, o 19:58

Gwoli uzupełnienia dodam, że nie ma powodu by traktować dwójkę w szczególny sposób - można ją z powodzeniem zastąpić dowolną liczbą pierwszą. Tutaj, też ktoś coś podobnego zliczał, ale ujął to nieco innymi słowami niż Marcinek665.

BlueSky
Użytkownik
Użytkownik
Posty: 224
Rejestracja: 11 cze 2011, o 20:27
Płeć: Kobieta
Podziękował: 31 razy

Podzielność liczby 2^2006!

Post autor: BlueSky » 8 sie 2013, o 23:15

ok, dziękuję wszystkim za pomoc

ODPOWIEDZ