Wspólny dzielnik układu
-
mol_ksiazkowy
- Użytkownik
- Posty: 13537
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3436 razy
- Pomógł: 812 razy
Wspólny dzielnik układu
Udowodnić, że największy wspólny dzielnik liczb \(\displaystyle{ {2n \choose 1}, {2n \choose 3}, ...., {2n \choose 2n-1}}\) to \(\displaystyle{ 2^{k+1}}\) o ile \(\displaystyle{ n= 2^k \cdot r}\) , i \(\displaystyle{ r }\) jest liczbą nieparzystą.
-
azanus111
- Użytkownik
- Posty: 87
- Rejestracja: 25 gru 2025, o 15:16
- Płeć: Mężczyzna
- wiek: 11
- Podziękował: 1 raz
- Pomógł: 7 razy
Re: Wspólny dzielnik układu
Pierwsza rzecz załóżmy, że istnieje pierwszy dzielni jakiś: \(\displaystyle{ p>2}\)
wniosek taki że p dzieli tę sumę tych liczb:
\(\displaystyle{ p | \left( \sum_{k=1 , k=2i+1}^{2n-1} {2n \choose k}\right) =2^{2n-1} }\)
bo tak ta suma wygląda co łatwo sprawdzić, więc prowadzi to do sprzeczności jedynym dzielnikiem zbioru tych liczb jest:
\(\displaystyle{ d=2^r}\)
stawiam tezę, że: największym wspólnym dzielnikiem będzie:
\(\displaystyle{ 2^r | {2n \choose 1} =2n , n=2^sc , c}\) - nieparzyste
pozostaje wykazać, że jest to największy wspólny dzielnik...
weźmy:
\(\displaystyle{ {2n \choose k}= \frac{(2n)!}{(2n-k)! \cdot k!} }\)
niech:
\(\displaystyle{ s_{2}(x)}\) - oznacza w jakiej potędze w tej liczbie mieści się dwójka
np: \(\displaystyle{ s_{2}(4)=2 , s_{2}(10)=1 ,...}\)
chcemy udowodnić, że:
\(\displaystyle{ s_{2}\left( {2n \choose 1} \right)=s+1=s_{2}\left( (2n)!\right)-s_{2}\left( (2n-1)!\right)-s_{2}(1) }\)
ale:
\(\displaystyle{ s_{2}\left( {2n \choose k} \right)=s_{2}\left( (2n)!\right) -s_{2}\left( (2n-k)!\right)-s_{2}\left( (k)!\right)}\)
więc trzeba udowodnić, że:
\(\displaystyle{ s_{2}\left( (2n)!\right) -s_{2}\left( (2n-k)!\right)-s_{2}\left( (k)!\right) \ge s_{2}\left( (2n)!\right) -s_{2}\left( (2n-1)!\right)-s_{2}\left( (1)!\right)}\)
\(\displaystyle{ s_{2}\left( (1)!\right)=0}\)
po uproszczeniu otrzymamy:
(*) \(\displaystyle{ s_{2}\left( (2n-k)!\right)+s_{2}\left( (k)!\right) \le s_{2}\left( (2n-1)!\right)}\)
ale zgodnie ze wzorem:
\(\displaystyle{ s_{2}(x!)= \sum_{k=1}^{ \infty } \left\lfloor \frac{x}{2^k} \right\rfloor}\)
zastosujmy ten wzór do (*) i otrzymamy:
\(\displaystyle{ \sum_{i=1}^{ \infty } \left\lfloor \frac{2n-k}{2^i} \right\rfloor + \sum_{i=1}^{ \infty } \left\lfloor \frac{k}{2^i} \right\rfloor \le \sum_{i=1}^{ \infty } \left\lfloor \frac{2n-1}{2^i} \right\rfloor}\)
lub:
\(\displaystyle{ \sum_{i=1}^{ \infty } \left( \left\lfloor \frac{2n-k}{2^i} \right\rfloor +\left\lfloor \frac{k}{2^i} \right\rfloor\right) \le \sum_{i=1}^{ \infty }\left\lfloor \frac{2n-1}{2^i} \right\rfloor }\)
żeby to udowodnić wystarczy ustalić sobie dowolne \(\displaystyle{ i}\) i udowodnić coś prostszego, czyli:
(**) \(\displaystyle{ \left\lfloor \frac{2n-k}{2^i} \right\rfloor +\left\lfloor \frac{k}{2^i} \right\rfloor \le \left\lfloor \frac{2n-1}{2^i} \right\rfloor}\)
pamietając, że \(\displaystyle{ k}\) jest nieparzyste...
podstawmy sobie:
\(\displaystyle{ 2n=2^ix+2r , 2r<2^i , k=2^iy+R , R<2^i}\)
po podstawieniu i uproszczeniu do (**) otrzymamy:
\(\displaystyle{ \left\lfloor x-y+ \frac{2r-R}{2^i} \right\rfloor +y \le \left\lfloor x+\frac{2r-1}{2^i} \right\rfloor}\)
oczywiście jest:
\(\displaystyle{ x \ge y}\)
jeżeli teraz:
\(\displaystyle{ 2r \ge R \wedge 2r \ge 1}\)
to otrzymamy:
\(\displaystyle{ x-y+y \le x}\)
i jest to prawda...
jeżeli natomiast:
\(\displaystyle{ 2r<R}\)
otrzymamy:
\(\displaystyle{ x-y-1+y \le x \vee x-y-1+y \le x-1}\)
ten drugi przypadek może się zdarzyć gdy: \(\displaystyle{ 2r=0 , r=0}\)
przypadek gdy lewa strona wyjdzie:
\(\displaystyle{ x}\) a prawa \(\displaystyle{ x-1}\) jest niemożliwy
warto jeszcze zauważyć ,że informacja, że \(\displaystyle{ k}\) jest nieparzyste jest bardzo istotna bo gdyby \(\displaystyle{ k}\) było parzyste to \(\displaystyle{ R}\) też byłoby parzyste
załóżmy , że tak jest więc może być np:
\(\displaystyle{ R=0 , r=0}\)
i otrzymamy:
\(\displaystyle{ x \le x-1}\) - co nie zachodzi
a więc te nierówności są spełnione dla \(\displaystyle{ k}\) nieparzystych...
czyli wykazaliśmy, że NWD tego układu jest największym dzielnikiem zawierającym dwa w potędze:
\(\displaystyle{ {2n \choose 1} =2n=2^{s+1}r , r=2i+1}\)
czyli:
\(\displaystyle{ NWD=2^{s+1}}\)
cnd...
wniosek taki że p dzieli tę sumę tych liczb:
\(\displaystyle{ p | \left( \sum_{k=1 , k=2i+1}^{2n-1} {2n \choose k}\right) =2^{2n-1} }\)
bo tak ta suma wygląda co łatwo sprawdzić, więc prowadzi to do sprzeczności jedynym dzielnikiem zbioru tych liczb jest:
\(\displaystyle{ d=2^r}\)
stawiam tezę, że: największym wspólnym dzielnikiem będzie:
\(\displaystyle{ 2^r | {2n \choose 1} =2n , n=2^sc , c}\) - nieparzyste
pozostaje wykazać, że jest to największy wspólny dzielnik...
weźmy:
\(\displaystyle{ {2n \choose k}= \frac{(2n)!}{(2n-k)! \cdot k!} }\)
niech:
\(\displaystyle{ s_{2}(x)}\) - oznacza w jakiej potędze w tej liczbie mieści się dwójka
np: \(\displaystyle{ s_{2}(4)=2 , s_{2}(10)=1 ,...}\)
chcemy udowodnić, że:
\(\displaystyle{ s_{2}\left( {2n \choose 1} \right)=s+1=s_{2}\left( (2n)!\right)-s_{2}\left( (2n-1)!\right)-s_{2}(1) }\)
ale:
\(\displaystyle{ s_{2}\left( {2n \choose k} \right)=s_{2}\left( (2n)!\right) -s_{2}\left( (2n-k)!\right)-s_{2}\left( (k)!\right)}\)
więc trzeba udowodnić, że:
\(\displaystyle{ s_{2}\left( (2n)!\right) -s_{2}\left( (2n-k)!\right)-s_{2}\left( (k)!\right) \ge s_{2}\left( (2n)!\right) -s_{2}\left( (2n-1)!\right)-s_{2}\left( (1)!\right)}\)
\(\displaystyle{ s_{2}\left( (1)!\right)=0}\)
po uproszczeniu otrzymamy:
(*) \(\displaystyle{ s_{2}\left( (2n-k)!\right)+s_{2}\left( (k)!\right) \le s_{2}\left( (2n-1)!\right)}\)
ale zgodnie ze wzorem:
\(\displaystyle{ s_{2}(x!)= \sum_{k=1}^{ \infty } \left\lfloor \frac{x}{2^k} \right\rfloor}\)
zastosujmy ten wzór do (*) i otrzymamy:
\(\displaystyle{ \sum_{i=1}^{ \infty } \left\lfloor \frac{2n-k}{2^i} \right\rfloor + \sum_{i=1}^{ \infty } \left\lfloor \frac{k}{2^i} \right\rfloor \le \sum_{i=1}^{ \infty } \left\lfloor \frac{2n-1}{2^i} \right\rfloor}\)
lub:
\(\displaystyle{ \sum_{i=1}^{ \infty } \left( \left\lfloor \frac{2n-k}{2^i} \right\rfloor +\left\lfloor \frac{k}{2^i} \right\rfloor\right) \le \sum_{i=1}^{ \infty }\left\lfloor \frac{2n-1}{2^i} \right\rfloor }\)
żeby to udowodnić wystarczy ustalić sobie dowolne \(\displaystyle{ i}\) i udowodnić coś prostszego, czyli:
(**) \(\displaystyle{ \left\lfloor \frac{2n-k}{2^i} \right\rfloor +\left\lfloor \frac{k}{2^i} \right\rfloor \le \left\lfloor \frac{2n-1}{2^i} \right\rfloor}\)
pamietając, że \(\displaystyle{ k}\) jest nieparzyste...
podstawmy sobie:
\(\displaystyle{ 2n=2^ix+2r , 2r<2^i , k=2^iy+R , R<2^i}\)
po podstawieniu i uproszczeniu do (**) otrzymamy:
\(\displaystyle{ \left\lfloor x-y+ \frac{2r-R}{2^i} \right\rfloor +y \le \left\lfloor x+\frac{2r-1}{2^i} \right\rfloor}\)
oczywiście jest:
\(\displaystyle{ x \ge y}\)
jeżeli teraz:
\(\displaystyle{ 2r \ge R \wedge 2r \ge 1}\)
to otrzymamy:
\(\displaystyle{ x-y+y \le x}\)
i jest to prawda...
jeżeli natomiast:
\(\displaystyle{ 2r<R}\)
otrzymamy:
\(\displaystyle{ x-y-1+y \le x \vee x-y-1+y \le x-1}\)
ten drugi przypadek może się zdarzyć gdy: \(\displaystyle{ 2r=0 , r=0}\)
przypadek gdy lewa strona wyjdzie:
\(\displaystyle{ x}\) a prawa \(\displaystyle{ x-1}\) jest niemożliwy
warto jeszcze zauważyć ,że informacja, że \(\displaystyle{ k}\) jest nieparzyste jest bardzo istotna bo gdyby \(\displaystyle{ k}\) było parzyste to \(\displaystyle{ R}\) też byłoby parzyste
załóżmy , że tak jest więc może być np:
\(\displaystyle{ R=0 , r=0}\)
i otrzymamy:
\(\displaystyle{ x \le x-1}\) - co nie zachodzi
a więc te nierówności są spełnione dla \(\displaystyle{ k}\) nieparzystych...
czyli wykazaliśmy, że NWD tego układu jest największym dzielnikiem zawierającym dwa w potędze:
\(\displaystyle{ {2n \choose 1} =2n=2^{s+1}r , r=2i+1}\)
czyli:
\(\displaystyle{ NWD=2^{s+1}}\)
cnd...