Dowody - potegi liczby 2

[legos]

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 !!!

[enigm32]

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.

[lukasz_650]

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.

[frej]

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

[lukasz_650]

Drugie i trzecie też umiem zrobić ;P Problem mam tylko z zadaniem pierwszym

[frej]

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...

[lukasz_650]

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.

[kammeleon18]

3. Zapisz warunek na postęp geometryczny \(\displaystyle{ a_2^2=a_1 a_3}\)

Nie jest powiedziane przecież, że to są kolejne elementy ciągu geometrycznego.

[pawelsuz]

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.

Mógłbyś wyjaśnić te dwa kroki? Albo ktokolwiek:d

[rodzyn7773]

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ą

[pawelsuz]

Pozwólcie, że ponowię pytanie...

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.

Czy ktoś mógłby wyjaśnić te dwa kroki w powyższym rozumowaniu?
Z góry wielkie dzięki!

[Zordon]

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ą

iloraz nie musi być całkowity, może być nawet niewymierny, wiec to rozumowanie nie przechodzi.

[rodzyn7773]

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

[lukasz_650]

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!

Już wyjaśniam
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ą

[pawelsuz]

Tak, wszystko jasne. Wielkie dzięki!