Pokazać, że \(\displaystyle{ 2^{n}-1}\) nie jest k-tą potęgą liczby naturalnej.
Założenia \(\displaystyle{ n, k \ge 2}\)
Zadanie wydaje się super proste, ale właściwie nie do końca wiem jak się za nie zabrać, mógłby ktoś dać jakąś wskazówkę?
Z góry dziękuję.
Pokazać, że liczb nie jest k-tą potęgą liczby naturalnej.
-
MadJack
- Użytkownik
- Posty: 270
- Rejestracja: 21 lis 2010, o 22:23
- Płeć: Mężczyzna
- Podziękował: 5 razy
- Pomógł: 35 razy
Pokazać, że liczb nie jest k-tą potęgą liczby naturalnej.
Nie wprost załóżmy, że jest
\(\displaystyle{ 2^n - 1 = t^k}\)
\(\displaystyle{ 2^n = (t+1) \cdot h}\) dla pewnego \(\displaystyle{ h}\) całkowitego (wzór skróconego mnożenia).
Wiemy, że \(\displaystyle{ t+1 > 1}\), stąd i powyższej równości wynika, że jedynym dzielnikiem pierwszym \(\displaystyle{ t+1}\) jest \(\displaystyle{ 2}\).
Teraz już raczej łatwo uzyskać sprzeczność.
\(\displaystyle{ 2^n - 1 = t^k}\)
\(\displaystyle{ 2^n = (t+1) \cdot h}\) dla pewnego \(\displaystyle{ h}\) całkowitego (wzór skróconego mnożenia).
Wiemy, że \(\displaystyle{ t+1 > 1}\), stąd i powyższej równości wynika, że jedynym dzielnikiem pierwszym \(\displaystyle{ t+1}\) jest \(\displaystyle{ 2}\).
Teraz już raczej łatwo uzyskać sprzeczność.
-
Fiszer
- Użytkownik
- Posty: 104
- Rejestracja: 19 kwie 2012, o 21:40
- Płeć: Mężczyzna
- Podziękował: 15 razy
- Pomógł: 3 razy
Pokazać, że liczb nie jest k-tą potęgą liczby naturalnej.
Zakładając to co mówisz, mamy
\(\displaystyle{ 2^{n} = t^{k} + 1}\)
Wzór o którym mówisz rozkłada się w ten sposób, jedynie dla nieparzystych k. (a co z parzystymi?)
Ponadto, nawet gdyby k było nieparzyste to mamy
\(\displaystyle{ 2^{n} = (t+1)(t^{k-1}-t^{k-2}+ ... -t + 1)}\)
I okej wnioskujemy, że skoro da się tak rozłożyć to
\(\displaystyle{ t+1 = 2^{p}}\) dla jakiegoś p. Możemy stąd zapisać \(\displaystyle{ t = 2^{p}-1}\)
I teraz trzeba, by powiedzieć coś o sumie \(\displaystyle{ (t^{k-1}-t^{k-2}+ ... -t + 1)}\)
Wiemy, że k było nieparzyste wobec tego w naszej sumie wyrazy przy, których stoją plusy będą parzystymi potęgami liczby \(\displaystyle{ 2^{p}-1}\), zatem z każdego takie podniesienia do parzystej potęgi dostaniemy liczbę podzielną przez 2 i gratisową 1 na końca. Natomiast przy wyrazach z nieparzystą potęgą stoi minus, więc z potęgowania do nieparzystej potęgi będziemy otrzymywać liczbę podzielną przez dwa i dodatkowo -1, ale minus przed całą liczbą znowu daje nam gratisową 1.
Pytanie ile takich jedynek będzie? Ano skoro mamy k wyrazów więc będzie \(\displaystyle{ k \cdot 1}\) jedynek czyli ogólnie nasza suma będzie liczbą nieparzystą. Sprzeczność. No dobra to jeszcze przypadek dla k parzystego.
Tutaj znalazłem rozwiązanie, a myślałem że bez kongruencji da się.
https://www.matematyka.pl/62630.htm
\(\displaystyle{ 2^{n} = t^{k} + 1}\)
Wzór o którym mówisz rozkłada się w ten sposób, jedynie dla nieparzystych k. (a co z parzystymi?)
Ponadto, nawet gdyby k było nieparzyste to mamy
\(\displaystyle{ 2^{n} = (t+1)(t^{k-1}-t^{k-2}+ ... -t + 1)}\)
I okej wnioskujemy, że skoro da się tak rozłożyć to
\(\displaystyle{ t+1 = 2^{p}}\) dla jakiegoś p. Możemy stąd zapisać \(\displaystyle{ t = 2^{p}-1}\)
I teraz trzeba, by powiedzieć coś o sumie \(\displaystyle{ (t^{k-1}-t^{k-2}+ ... -t + 1)}\)
Wiemy, że k było nieparzyste wobec tego w naszej sumie wyrazy przy, których stoją plusy będą parzystymi potęgami liczby \(\displaystyle{ 2^{p}-1}\), zatem z każdego takie podniesienia do parzystej potęgi dostaniemy liczbę podzielną przez 2 i gratisową 1 na końca. Natomiast przy wyrazach z nieparzystą potęgą stoi minus, więc z potęgowania do nieparzystej potęgi będziemy otrzymywać liczbę podzielną przez dwa i dodatkowo -1, ale minus przed całą liczbą znowu daje nam gratisową 1.
Pytanie ile takich jedynek będzie? Ano skoro mamy k wyrazów więc będzie \(\displaystyle{ k \cdot 1}\) jedynek czyli ogólnie nasza suma będzie liczbą nieparzystą. Sprzeczność. No dobra to jeszcze przypadek dla k parzystego.
Tutaj znalazłem rozwiązanie, a myślałem że bez kongruencji da się.
https://www.matematyka.pl/62630.htm
-
MadJack
- Użytkownik
- Posty: 270
- Rejestracja: 21 lis 2010, o 22:23
- Płeć: Mężczyzna
- Podziękował: 5 razy
- Pomógł: 35 razy
Pokazać, że liczb nie jest k-tą potęgą liczby naturalnej.
Można inaczej. Załóżmy, że
\(\displaystyle{ 2^n-1 = (2^p-1)^k}\)
W szczególności oznacza to, że
\(\displaystyle{ 2^p-1 \mid 2^n-1}\), czyli \(\displaystyle{ 2^n-1 = s(2^p-1)}\)
\(\displaystyle{ 2^n = 2^p s - (s-1)}\)
Mamy także \(\displaystyle{ 2^p \mid 2^n}\), więc \(\displaystyle{ 2^p \mid s-1}\), czyli możemy napisać
\(\displaystyle{ 2^n = 2^p (2^p b+1) - 2^p b}\)
Dzieląc przez \(\displaystyle{ 2^p}\)
\(\displaystyle{ 2^{n-p} = 2^p b - (b-1)}\)
Powtarzamy rozumowanie jak wyżej i dostajemy
\(\displaystyle{ 2^{n-2p} = 2^p b_1 - (b_1-1)}\) i tak dalej.
Tak postępując dojdziemy w końcu do pewnego \(\displaystyle{ b_i = 1}\). Zatem
\(\displaystyle{ s = 2^p(2^p(...(2^p+1)...+1) + 1}\). Ale wymnażając dostaniemy ciąg geometryczny równy dla pewnego \(\displaystyle{ g}\) \(\displaystyle{ 2^g+1}\), stąd już łatwo dostać sprzeczność.
Był edit, bo wkradł się w środku rozumowania głupi błąd. Teraz już chyba dobrze.
\(\displaystyle{ 2^n-1 = (2^p-1)^k}\)
W szczególności oznacza to, że
\(\displaystyle{ 2^p-1 \mid 2^n-1}\), czyli \(\displaystyle{ 2^n-1 = s(2^p-1)}\)
\(\displaystyle{ 2^n = 2^p s - (s-1)}\)
Mamy także \(\displaystyle{ 2^p \mid 2^n}\), więc \(\displaystyle{ 2^p \mid s-1}\), czyli możemy napisać
\(\displaystyle{ 2^n = 2^p (2^p b+1) - 2^p b}\)
Dzieląc przez \(\displaystyle{ 2^p}\)
\(\displaystyle{ 2^{n-p} = 2^p b - (b-1)}\)
Powtarzamy rozumowanie jak wyżej i dostajemy
\(\displaystyle{ 2^{n-2p} = 2^p b_1 - (b_1-1)}\) i tak dalej.
Tak postępując dojdziemy w końcu do pewnego \(\displaystyle{ b_i = 1}\). Zatem
\(\displaystyle{ s = 2^p(2^p(...(2^p+1)...+1) + 1}\). Ale wymnażając dostaniemy ciąg geometryczny równy dla pewnego \(\displaystyle{ g}\) \(\displaystyle{ 2^g+1}\), stąd już łatwo dostać sprzeczność.
Był edit, bo wkradł się w środku rozumowania głupi błąd. Teraz już chyba dobrze.
