Dowody - potegi liczby 2
-
- Użytkownik
- Posty: 30
- Rejestracja: 31 mar 2007, o 14:49
- Płeć: Mężczyzna
- Lokalizacja: retyr
- Podziękował: 14 razy
Dowody - potegi liczby 2
1. Udowodnić że \(\displaystyle{ 2^{n}-1}\) \(\displaystyle{ n \in N}\) \(\displaystyle{ n>1}\) nie jest k-tą potęgą \(\displaystyle{ k qslant 2}\) zadnej liczby naturalnej.
2. Udowodnić że jeżeli \(\displaystyle{ a,b N}\) to \(\displaystyle{ NWD(2^{a}-1,2^{b}-1) =2^{NWD(a,b)}-1}\)
3. Wykazać , że 3 różne liczby pierwsze nie mogą być wyrazami tego samego postępu geometrycznego
DZIĘKUJĘ ZA KAŻDĄ POMOC !!!
2. Udowodnić że jeżeli \(\displaystyle{ a,b N}\) to \(\displaystyle{ NWD(2^{a}-1,2^{b}-1) =2^{NWD(a,b)}-1}\)
3. Wykazać , że 3 różne liczby pierwsze nie mogą być wyrazami tego samego postępu geometrycznego
DZIĘKUJĘ ZA KAŻDĄ POMOC !!!
- enigm32
- Użytkownik
- Posty: 596
- Rejestracja: 25 lut 2008, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Jasło
- Podziękował: 12 razy
- Pomógł: 99 razy
Dowody - potegi liczby 2
Wskazówka do zad. 1.: za pomocą kongruencji (lub inaczej, ale najlepsze tu będą kongruencje) zbadaj jaka może być otatnia cyfra liczby \(\displaystyle{ 2^n-1}\). Czyli badasz przystawanie \(\displaystyle{ (mod10)}\). Okaże się, że ostatnia cyfra będzie zawsze, którąś z cyfr \(\displaystyle{ 2, 3, 7, 8}\), a żadna potęga nie kończy się na taką cyfrę. Stąd uzyskujemy dowód naszej tezy. Pzdr.
-
- Użytkownik
- Posty: 116
- Rejestracja: 24 paź 2008, o 22:01
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 10 razy
- Pomógł: 3 razy
Dowody - potegi liczby 2
Chciałem założyć nowy temat z zadaniem 1., ale widzę, że zostało już na tym forum zamieszczone, więc odkopuję temat
Albo czegoś nie widzę, albo rozwiązanie do zadania 1. nie jest poprawne... Po pierwsze liczby postaci \(\displaystyle{ 2^{n}-1}\) mogą dawać reszty \(\displaystyle{ 1, 3, 5, 7}\) z dzielenia przez \(\displaystyle{ 10}\). Po drugie istnieją potęgi o takich ostatnich cyfrach.
Byłbym bardzo wdzięczny za rozwiązanie lub wskazówki do zadania 1.
Albo czegoś nie widzę, albo rozwiązanie do zadania 1. nie jest poprawne... Po pierwsze liczby postaci \(\displaystyle{ 2^{n}-1}\) mogą dawać reszty \(\displaystyle{ 1, 3, 5, 7}\) z dzielenia przez \(\displaystyle{ 10}\). Po drugie istnieją potęgi o takich ostatnich cyfrach.
Byłbym bardzo wdzięczny za rozwiązanie lub wskazówki do zadania 1.
Dowody - potegi liczby 2
3. Zapisz warunek na postęp geometryczny \(\displaystyle{ a_2^2=a_1 a_3}\)
2. Wystarczy skorzystać z algorytmu Eulkidesa
Niestety nie wiem jak zrobić pierwsze
2. Wystarczy skorzystać z algorytmu Eulkidesa
Niestety nie wiem jak zrobić pierwsze
-
- Użytkownik
- Posty: 116
- Rejestracja: 24 paź 2008, o 22:01
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 10 razy
- Pomógł: 3 razy
Dowody - potegi liczby 2
Drugie i trzecie też umiem zrobić ;P Problem mam tylko z zadaniem pierwszym
Dowody - potegi liczby 2
Wiem, że umiesz je zrobić, bo jesteś przecież sporo lepszy ode mnie
Tak napisałem, bo może komuś się kiedyś przyda. Wątpię w to, ale może...
Tak napisałem, bo może komuś się kiedyś przyda. Wątpię w to, ale może...
-
- Użytkownik
- Posty: 116
- Rejestracja: 24 paź 2008, o 22:01
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 10 razy
- Pomógł: 3 razy
Dowody - potegi liczby 2
Poradziłem sobie
Lemat.
Dla \(\displaystyle{ \ a, k, n \in \mathbb{Z_{+}} (n \geqslant 2)}\):
\(\displaystyle{ a^{k} \equiv (-1)(mod \ 2^{n}) \Rightarrow a \equiv (-1)(mod \ 2^{n})}\)
Dowód indukcyjny lematu ze względu na \(\displaystyle{ n}\):
1) Dla \(\displaystyle{ n=2}\) łatwo sprawdzić, że implikacja zachodzi.
2) Załóżmy, że teza jest prawdziwa dla \(\displaystyle{ n}\). Pokażemy, że jest wówczas prawdziwa dla \(\displaystyle{ n+1}\).
Wychodząc od lewej strony implikacji:
\(\displaystyle{ a^{k} \equiv (-1)(mod \ 2^{n+1}) \Rightarrow a^{k} \equiv (-1)(mod \ 2^{n}) \Rightarrow a \equiv (-1)(mod \ 2^{n})}\)
Druga implikacja wynika z założenia indukcyjnego. Stąd otrzymujemy, że:
\(\displaystyle{ a \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a \equiv (-1)(mod \ 2^{n+1})}\)
Jednak w tym pierwszym przypadku otrzymujemy sprzeczność, bo łatwo można sprawdzić, że:
\(\displaystyle{ a^{k} \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a^{k} \equiv 1(mod \ 2^{n+1})}\)
Musi zatem zajść drugi przypadek, a to kończy dowód lematu.
Z lematu otrzymujemy, że:
\(\displaystyle{ a^{k} = 2^{n}-1 \Rightarrow a \equiv (-1)(mod \ 2^{n})}\)
Oczywiście musi zajść:
\(\displaystyle{ a \leqslant 2^{n}-1}\)
A jedyną taka liczbą całkowitą dodatnią, która spełnia zarówno nierówność, jak i kongruencję, jest:
\(\displaystyle{ a = 2^{n}-1}\)
Wówczas jednak \(\displaystyle{ k=1}\).
Tym samym dla \(\displaystyle{ n, k \geqslant 2}\) liczba \(\displaystyle{ 2^{n}-1}\) nie jest \(\displaystyle{ k}\)-tą potęgą żadnej liczby naturalnej.
Lemat.
Dla \(\displaystyle{ \ a, k, n \in \mathbb{Z_{+}} (n \geqslant 2)}\):
\(\displaystyle{ a^{k} \equiv (-1)(mod \ 2^{n}) \Rightarrow a \equiv (-1)(mod \ 2^{n})}\)
Dowód indukcyjny lematu ze względu na \(\displaystyle{ n}\):
1) Dla \(\displaystyle{ n=2}\) łatwo sprawdzić, że implikacja zachodzi.
2) Załóżmy, że teza jest prawdziwa dla \(\displaystyle{ n}\). Pokażemy, że jest wówczas prawdziwa dla \(\displaystyle{ n+1}\).
Wychodząc od lewej strony implikacji:
\(\displaystyle{ a^{k} \equiv (-1)(mod \ 2^{n+1}) \Rightarrow a^{k} \equiv (-1)(mod \ 2^{n}) \Rightarrow a \equiv (-1)(mod \ 2^{n})}\)
Druga implikacja wynika z założenia indukcyjnego. Stąd otrzymujemy, że:
\(\displaystyle{ a \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a \equiv (-1)(mod \ 2^{n+1})}\)
Jednak w tym pierwszym przypadku otrzymujemy sprzeczność, bo łatwo można sprawdzić, że:
\(\displaystyle{ a^{k} \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a^{k} \equiv 1(mod \ 2^{n+1})}\)
Musi zatem zajść drugi przypadek, a to kończy dowód lematu.
Z lematu otrzymujemy, że:
\(\displaystyle{ a^{k} = 2^{n}-1 \Rightarrow a \equiv (-1)(mod \ 2^{n})}\)
Oczywiście musi zajść:
\(\displaystyle{ a \leqslant 2^{n}-1}\)
A jedyną taka liczbą całkowitą dodatnią, która spełnia zarówno nierówność, jak i kongruencję, jest:
\(\displaystyle{ a = 2^{n}-1}\)
Wówczas jednak \(\displaystyle{ k=1}\).
Tym samym dla \(\displaystyle{ n, k \geqslant 2}\) liczba \(\displaystyle{ 2^{n}-1}\) nie jest \(\displaystyle{ k}\)-tą potęgą żadnej liczby naturalnej.
Ostatnio zmieniony 2 wrz 2009, o 17:34 przez lukasz_650, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 306
- Rejestracja: 10 maja 2008, o 11:38
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Pomógł: 36 razy
Dowody - potegi liczby 2
Nie jest powiedziane przecież, że to są kolejne elementy ciągu geometrycznego.frej pisze:3. Zapisz warunek na postęp geometryczny \(\displaystyle{ a_2^2=a_1 a_3}\)
-
- Użytkownik
- Posty: 569
- Rejestracja: 15 gru 2008, o 18:22
- Płeć: Mężczyzna
- Lokalizacja: BK
- Podziękował: 73 razy
- Pomógł: 40 razy
Dowody - potegi liczby 2
Mógłbyś wyjaśnić te dwa kroki? Albo ktokolwiek:dlukasz_650 pisze:
Stąd otrzymujemy, że:
\(\displaystyle{ a \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a \equiv (-1)(mod \ 2^{n+1})}\)
Jednak w tym pierwszym przypadku otrzymujemy sprzeczność, bo łatwo można sprawdzić, że:
\(\displaystyle{ a^{k} \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a^{k} \equiv 1(mod \ 2^{n+1})}\)
Musi zatem zajść drugi przypadek, a to kończy dowód lematu.
-
- Użytkownik
- Posty: 1659
- Rejestracja: 12 lip 2009, o 10:44
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Rawa Maz.
- Podziękował: 8 razy
- Pomógł: 278 razy
Dowody - potegi liczby 2
3) wiadomo, że liczby pierwsze mają 2 podzielniki zatem można je zapisać:
\(\displaystyle{ p_n=1*p_n}\) jeżeli przyjmiemy że naszym ilorazem będzie 1 to zgodnie z treścią będzie to błąd gdyż wyrazy muszą być różne jeżeli zaś przyjmiemy że naszym ilorazem będzie p_n to otrzymamy:
\(\displaystyle{ p_n_+_1=(p_n)^2}\) niestety wtedy nasze \(\displaystyle{ p_n_+_1}\) nie będzie liczbą pierwszą
\(\displaystyle{ p_n=1*p_n}\) jeżeli przyjmiemy że naszym ilorazem będzie 1 to zgodnie z treścią będzie to błąd gdyż wyrazy muszą być różne jeżeli zaś przyjmiemy że naszym ilorazem będzie p_n to otrzymamy:
\(\displaystyle{ p_n_+_1=(p_n)^2}\) niestety wtedy nasze \(\displaystyle{ p_n_+_1}\) nie będzie liczbą pierwszą
-
- Użytkownik
- Posty: 569
- Rejestracja: 15 gru 2008, o 18:22
- Płeć: Mężczyzna
- Lokalizacja: BK
- Podziękował: 73 razy
- Pomógł: 40 razy
Dowody - potegi liczby 2
Pozwólcie, że ponowię pytanie...
Z góry wielkie dzięki!
Czy ktoś mógłby wyjaśnić te dwa kroki w powyższym rozumowaniu?lukasz_650 pisze:
Stąd otrzymujemy, że:
\(\displaystyle{ a \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a \equiv (-1)(mod \ 2^{n+1})}\)
Jednak w tym pierwszym przypadku otrzymujemy sprzeczność, bo łatwo można sprawdzić, że:
\(\displaystyle{ a^{k} \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a^{k} \equiv 1(mod \ 2^{n+1})}\)
Musi zatem zajść drugi przypadek, a to kończy dowód lematu.
Z góry wielkie dzięki!
- Zordon
- Użytkownik
- Posty: 4977
- Rejestracja: 12 lut 2008, o 21:42
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 75 razy
- Pomógł: 910 razy
Dowody - potegi liczby 2
iloraz nie musi być całkowity, może być nawet niewymierny, wiec to rozumowanie nie przechodzi.rodzyn7773 pisze:3) wiadomo, że liczby pierwsze mają 2 podzielniki zatem można je zapisać:
\(\displaystyle{ p_n=1*p_n}\) jeżeli przyjmiemy że naszym ilorazem będzie 1 to zgodnie z treścią będzie to błąd gdyż wyrazy muszą być różne jeżeli zaś przyjmiemy że naszym ilorazem będzie p_n to otrzymamy:
\(\displaystyle{ p_n_+_1=(p_n)^2}\) niestety wtedy nasze \(\displaystyle{ p_n_+_1}\) nie będzie liczbą pierwszą
-
- Użytkownik
- Posty: 1659
- Rejestracja: 12 lip 2009, o 10:44
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice/Rawa Maz.
- Podziękował: 8 razy
- Pomógł: 278 razy
Dowody - potegi liczby 2
tak tak pomyliłem się ale za iloraz możemy wziąć dowolną liczbę a wtedy kolejne wyrazy ciągu będą liczbami złożonymi
-
- Użytkownik
- Posty: 116
- Rejestracja: 24 paź 2008, o 22:01
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 10 razy
- Pomógł: 3 razy
Dowody - potegi liczby 2
Już wyjaśniampawelsuz pisze:Pozwólcie, że ponowię pytanie...
Czy ktoś mógłby wyjaśnić te dwa kroki w powyższym rozumowaniu?
Z góry wielkie dzięki!
1) \(\displaystyle{ a \equiv (-1)(mod \ 2^{n}) \Rightarrow [a \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a \equiv (-1)(mod \ 2^{n+1})]}\)
Ta implikacja jest prawdziwa, bo skoro \(\displaystyle{ a \equiv (-1)(mod \ 2^{n})}\), to dla pewnej liczby całkowitej k mamy:
\(\displaystyle{ a = k 2^{n} - 1}\)
Mamy dwa przypadki (oczywiście l jest liczbą całkowitą):
a) \(\displaystyle{ k = 2l \Rightarrow a=2l*2^{n}-1=l*2^{n+1}-1 \Rightarrow a \equiv (-1)(mod \ 2^{n+1})}\)
b) \(\displaystyle{ k = 2l+1 \Rightarrow a=(2l+1)*2^{n}-1=l*2^{n+1}+2^{n}-1 \Rightarrow a \equiv (2^{n}-1)(mod \ 2^{n+1})}\)
Otrzymaliśmy zatem prawą stronę implikacji, co kończy jej dowód.
2) Załóżmy, że \(\displaystyle{ a \equiv (2^{n}-1)(mod \ 2^{n+1})}\)
Pokaże prawdziwość dwóch implikacji:
a) \(\displaystyle{ a^{k} \equiv (2^{n}-1)(mod \ 2^{n+1}) \Rightarrow a^{k+1} \equiv 1(mod \ 2^{n+1})}\)
Zakładając, że lewa strona implikacji jest prawdziwa, mamy:
\(\displaystyle{ a^{k+1} = a*a^{k} \equiv (2^{n}-1)(2^{n}-1) = 2^{2n}-2^{n+1}+1 = 2^{n+1}(2^{n-1}-1)+1 \equiv 1(mod \ 2^{n+1})}\)
b) \(\displaystyle{ a^{k} \equiv 1(mod \ 2^{n+1}) \Rightarrow a^{k+1} \equiv (2^{n}-1)(mod \ 2^{n+1})}\)
Istotnie, przyjmując założenie z lewej strony implikacji, otrzymujemy:
\(\displaystyle{ a^{k+1} = a*a^{k} \equiv (2^{n}-1)*1 = (2^{n}-1)(mod \ 2^{n+1})}\)
Mając te dwie implikacje, na mocy zasady indukcji matematycznej, otrzymujemy alternatywę:
\(\displaystyle{ a^{k} \equiv (2^{n}-1)(mod \ 2^{n+1}) \vee a^{k} \equiv 1(mod \ 2^{n+1})}\)
To natomiast przeczy założeniu, że \(\displaystyle{ a^{k} \equiv (-1)(mod \ 2^{n+1})}\).
Wracając zatem do implikacji z punktu 1) otrzymujemy: \(\displaystyle{ a \equiv (-1)(mod \ 2^{n+1})}\), co kończy dowód indukcyjny lematu.
Mam nadzieję, ze teraz jest już wszystko wyjaśnione - jeśli nie, to dalej służę pomocą