szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 sty 2011, o 01:20 
Użytkownik

Posty: 348
Lokalizacja: warszawa
Niech n będzie liczbą całkowitą \ge  2. Udowodnić, że n nie dzieli 2^{n} -1.

prosze o wskazówki jak rozwiązać to zadanie
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 8 sty 2011, o 10:38 
Użytkownik

Posty: 3
Lokalizacja: Białystok
A więc na samym początku trzeba zauważyć że pod lupę bierzemy jedynie n nieparzyste.
(Jako że wyrażenie daje zawsze wynik w postaci liczby nieparzystej nie podzielimy jej nigdy przez liczbę parzystą).

Skoro już to wiemy możemy od razu odrzucić wszystkie liczby pierwsze korzystając z małego twierdzenia Fermata, gdyż każda liczba z n pierwszym 2 ^{n} będzie przystawała do 2 (mod n).

Zauważ jeszcze, że 2 ^{n} zawsze będzie przystawało do parzystej liczby (mod n).
Góra
Mężczyzna Offline
PostNapisane: 24 wrz 2011, o 12:49 
Użytkownik
Avatar użytkownika

Posty: 2910
Lokalizacja: Biała Podlaska / Warszawa
Pingwin94 napisał(a):
Zauważ jeszcze, że 2 ^{n} zawsze będzie przystawało do parzystej liczby (mod n).

?

Dla n\ge 2 ma zachodzić n | 2^n-1, oczywiście 2 \nmid n. Niech teraz p będzie najmniejszym dzielnikiem pierwszym n, oraz t = ord_p 2, musi więc zachodzić t | n, oraz z twierdzenia Eulera dostajemy 2^{p-1} \equiv 1 \pmod{p}, skąd t | p-1, czyli t \le p-1 < p ale z założenia p jest najmniejszym dzielnikiem pierwszym n, więc t=1, czyli 2 \equiv 1 \pmod{p}  \Leftrightarrow p=1 ale z założenia p jest pierwsze, czyli n nie ma dzielników pierwszych, co bezpośrednio implikuje n=1, ale z założenia n\ge 2 więc dana podzielność nie zajdzie dla żadnego n, cnd.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 udowodnić, że liczba jest niewymierna - zadanie 2  leszczu450  4
 podzielność, błąd?  tukanik  2
 Podzielność przez 7. - zadanie 2  pchelaa  1
 Dowodzenie twierdzeń. Podzielność przez 36  madziomka  1
 c dzieli a i c dzieli b to c dzieli |A+Bk| Udowodnić???  123456  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl