szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 8 sty 2011, o 00: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
Góra
Mężczyzna Offline
PostNapisane: 8 sty 2011, o 09: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 11:49 
Użytkownik
Avatar użytkownika

Posty: 2909
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 
 Uzasadnić podzielność sumy liczb przez jedenaście  MuKuL  4
 Podzielność przez 6 - zadanie 5  hugerth  1
 Udowodnij podzielność wyrażenia  Yorktown  3
 Podzielność wyrażenia przez 8  misiasia994  1
 Udowodnić podzielność liczb całkowitych a,b  MathMaster  6
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl