liczby względnie pierwsze
liczby względnie pierwsze
Pokazać, że w ciągu \(\displaystyle{ {2 ^{n}-3}}\) istnieje nieskończenie wiele liczb, z których każde dwie są względnie pierwsze.
-
arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
liczby względnie pierwsze
Mi się wydaje, że w tym ciągu jest nieskończenie wiele l. pierwszych ponieważ:
\(\displaystyle{ 2^{n}-3=4*(2^{n-2}-1)+1}\)
a w ciągach 4k+1 jest nieskończenie wiele l. pierwszych
\(\displaystyle{ 2^{n}-3=4*(2^{n-2}-1)+1}\)
a w ciągach 4k+1 jest nieskończenie wiele l. pierwszych
-
SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
liczby względnie pierwsze
arku1357, to co napisałeś jeszcze nie jest rozwiązaniem. Przytoczony fakt jest oczywiście prawdziwy, ale skąd wiesz, że ciąg \(\displaystyle{ 4(2^{n-2}-1)+1}\) nie "omija" tych liczb pierwszych? Jeszcze dzisiaj spróbuję się zabrać za te zadanie 
EDIT:
Dobra, zadanie zrobione. Przez \(\displaystyle{ \mathbb{Z}^*_n}\) oznaczmy zbiór wszystkich liczb naturalnych mniejszych od \(\displaystyle{ n}\) oraz względnie pierwszych z \(\displaystyle{ n}\). Jeżeli \(\displaystyle{ n\equiv 1\pmod{2}}\), to oczywiście \(\displaystyle{ 2\in\mathbb{Z}^*_n}\). Teraz pokażemy, że dla dowolnego takiego \(\displaystyle{ n}\) nieparzystego istnieje \(\displaystyle{ n'}\), że \(\displaystyle{ (2^{n'}-3, n)=1}\). To zakończy dowód, ponieważ nieskończony ciąg liczb względnie pierwszych będziemy konstruować indukcyjnie- mając dany zbiór parami względnie pierwszych wyrazów tego ciągu, znajdziemy wyraz ciągu względnie pierwszy z ich iloczynem, a zatem i z każdym z poprzednich wyrazów. Z twierdzenia Lagrange'a/Eulera (jak kto woli) mamy, że \(\displaystyle{ n|2^{\phi(n)}-1}\), czyli \(\displaystyle{ 2^{\phi(n)}-1=nk}\) dla pewnego \(\displaystyle{ k\in\mathbb{N}}\). Weźmy zatem \(\displaystyle{ n'=\phi(n)}\). Wiemy, że \(\displaystyle{ (2^{n'}-1, 2^{n'}-3)=1\Leftrightarrow (nk, 2^{n'}-3)=1\Rightarrow (n,2^{n'}-3)=1}\) (kolejno- dwie kolejne liczby nieparzyste są względnie pierwsze oraz jeżeli liczba jest względnie pierwsza z iloczynem liczb, to jest również względnie pierwsza z każdą z nich), a to już kończy dowód.
EDIT2: Jak już ogarnąłem, że zamiast Lagrange'a mogę użyć równoważnego w tym przypadku Eulera, to odechciało mi się tłumaczyć ideę \(\displaystyle{ \mathbb{Z}_n^*}\)
EDIT:
Dobra, zadanie zrobione. Przez \(\displaystyle{ \mathbb{Z}^*_n}\) oznaczmy zbiór wszystkich liczb naturalnych mniejszych od \(\displaystyle{ n}\) oraz względnie pierwszych z \(\displaystyle{ n}\). Jeżeli \(\displaystyle{ n\equiv 1\pmod{2}}\), to oczywiście \(\displaystyle{ 2\in\mathbb{Z}^*_n}\). Teraz pokażemy, że dla dowolnego takiego \(\displaystyle{ n}\) nieparzystego istnieje \(\displaystyle{ n'}\), że \(\displaystyle{ (2^{n'}-3, n)=1}\). To zakończy dowód, ponieważ nieskończony ciąg liczb względnie pierwszych będziemy konstruować indukcyjnie- mając dany zbiór parami względnie pierwszych wyrazów tego ciągu, znajdziemy wyraz ciągu względnie pierwszy z ich iloczynem, a zatem i z każdym z poprzednich wyrazów. Z twierdzenia Lagrange'a/Eulera (jak kto woli) mamy, że \(\displaystyle{ n|2^{\phi(n)}-1}\), czyli \(\displaystyle{ 2^{\phi(n)}-1=nk}\) dla pewnego \(\displaystyle{ k\in\mathbb{N}}\). Weźmy zatem \(\displaystyle{ n'=\phi(n)}\). Wiemy, że \(\displaystyle{ (2^{n'}-1, 2^{n'}-3)=1\Leftrightarrow (nk, 2^{n'}-3)=1\Rightarrow (n,2^{n'}-3)=1}\) (kolejno- dwie kolejne liczby nieparzyste są względnie pierwsze oraz jeżeli liczba jest względnie pierwsza z iloczynem liczb, to jest również względnie pierwsza z każdą z nich), a to już kończy dowód.
EDIT2: Jak już ogarnąłem, że zamiast Lagrange'a mogę użyć równoważnego w tym przypadku Eulera, to odechciało mi się tłumaczyć ideę \(\displaystyle{ \mathbb{Z}_n^*}\)
Ostatnio zmieniony 24 gru 2010, o 14:22 przez SaxoN, łącznie zmieniany 2 razy.