szukanie zaawansowane
 [ Posty: 12 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 18:44 
Moderator

Posty: 1902
Lokalizacja: Trzebiatów
Witam, natknąłem się na dość prosty problem ale nie mam żadnego pomysłu jak go ruszyć, mianowicie :
Czy istnieje wspólny dzielnik liczb a,  2^{a} - 1 gdzie a \in N.
Z góry dziękuje :)
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 18:49 
Moderator
Avatar użytkownika

Posty: 2226
Lokalizacja: Warszawa
Szukasz liczby d, takiej, że d \mid a i d \mid 2^{a}-1?
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 18:53 
Moderator

Posty: 1902
Lokalizacja: Trzebiatów
Tak
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 19:47 
Użytkownik

Posty: 738
Lokalizacja: Podhale/ Warszawa
d=1
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 20:17 
Moderator

Posty: 1902
Lokalizacja: Trzebiatów
Geniualne ^.^ Znalazłem już, dziękuje.
Góra
Kobieta Offline
PostNapisane: 5 mar 2014, o 20:33 
Użytkownik

Posty: 79
Lokalizacja: Bielsko-Biała
Zahion, czy mógłbyś napisać, w jaki sposób do tego doszedłeś?
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 20:56 
Moderator

Posty: 1902
Lokalizacja: Trzebiatów
Mianowicie do czego ?
Góra
Kobieta Offline
PostNapisane: 5 mar 2014, o 21:05 
Użytkownik

Posty: 79
Lokalizacja: Bielsko-Biała
W jaki sposób znalazłeś d.
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 21:30 
Moderator

Posty: 1902
Lokalizacja: Trzebiatów
Znalazłem w sensie, że stwierdziłem iż nie ma takiej liczby.
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 21:48 
Użytkownik
Avatar użytkownika

Posty: 2909
Lokalizacja: Biała Podlaska / Warszawa
Załóżmy, że dla pewnego a jest (a,2^a-1) > 1 i niech p będzie najmniejszym dzielnikiem pierwszym (a,2^a-1), dodatkowo niech t będzie najmniejszą dodatnią liczbą taką, że 2^t \equiv 1\pmod{p}. Niech a = kt+r gdzie r \in [0;t-1], wówczas 1 \equiv 2^a \equiv (2^t)^k \cdot 2^r \equiv 2^r \pmod{p}, ale z definicji t dostajemy r=0, czyli t \mid a, ale z małego twierdzenia Fermata mamy też 2^{p-1} \equiv 1\pmod{p}, analogicznie wnioskujemy, że t \mid p-1, czyli t jest dzielnikiem a i jednocześnie dzielnikiem p-1, ale p było najmniejszym dzielnikiem pierwszym a, skąd t=1 czyli 2 \equiv 1\pmod{p} sprzeczność.
Góra
Kobieta Offline
PostNapisane: 5 mar 2014, o 23:00 
Użytkownik

Posty: 79
Lokalizacja: Bielsko-Biała
Ale p było najmniejszym dzielnikiem pierwszym (a,2^a-1), nie a. Istnieją d większe od 1, np. a=23 \cdot 11 , wtedy d=23.
Góra
Mężczyzna Offline
PostNapisane: 5 mar 2014, o 23:21 
Moderator
Avatar użytkownika

Posty: 2226
Lokalizacja: Warszawa
Przecież wspólnym dzielnikiem może być dowolna liczba pierwsza p. Weźmy bowiem a=bpt, gdzie b jest dowolną liczbą całkowitą dodatnią, zaś t jest rzędem dwójki modulo p. Wtedy oczywiście p \mid a, zaś 2^{bpt}-1 \equiv \left(2^{t}\right)^{bp}-1 \equiv 0 \pmod{p}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 12 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 (4 zadania) Sprawdz podzielność liczb przez 10  Anonymous  4
 Czy podana liczba jest różnicą kwadratów 2 liczb calko  pennywise  1
 Różnica cyfr pewnej liczby wynosi 5 ... Znajdź tę liczb  Tomasz B  4
 Zadanie z dowodem na sumę liczb naturalnych  scn  5
 podzielnosc liczb?  Anonymous  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl