Znajdz takie pary liczb pierwszych , ze:

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11266
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3143 razy
Pomógł: 747 razy

Znajdz takie pary liczb pierwszych , ze:

Post autor: mol_ksiazkowy »

\(\displaystyle{ 2^p+2^q \equiv 0 \ mod (pq)}\)
Marcin88
Użytkownik
Użytkownik
Posty: 66
Rejestracja: 15 sie 2006, o 12:41
Płeć: Mężczyzna
Lokalizacja: Krosno Odrzańskie
Pomógł: 25 razy

Znajdz takie pary liczb pierwszych , ze:

Post autor: Marcin88 »

Powinno być dobrze: jeżeli jedna z tych liczb, powiedzmy p jest równa 2, to wówczas mamy podzielność: \(\displaystyle{ q|2+2^{q-1}}\)
Jeżeli q=2 to podzielność zachodzi, jeśli q nie jest dwójką, to z Małego Twierdzenia Fermata mamy: \(\displaystyle{ q|2+2^{q-1}\equiv2+1=3(mod q)}\)
skąd już bezpośrednio: q=3. Zatem w przypadku, gdy co najmniej jedna z tych liczb jest równa dwa, znajdujemy trzy rozwiązania: \(\displaystyle{ (2,2), (2,3), (3,2)}\)
Załóżmy zatem że żadna z tych liczb nie jest dwójką. Wtedy jest p różne od q i mamy: \(\displaystyle{ pq|2^{p-1}+2^{q-1}}\) skąd ponownie stosując Małe Tw. Fermata otrzymujemy układ kongruencji:
\(\displaystyle{ 2^{p-1}\equiv-1(mod q), 2^{q-1}\equiv1(mod q), 2^{q-1}\equiv-1(mod p), 2^{p-1}\equiv1(mod p)}\) Oznaczmy zatem przez \(\displaystyle{ 2r_p, 2r_q}\) rząd dwójki modulo odpowiednio p i q.
Wówczas wiadomo, że: \(\displaystyle{ 2^{r_p}\equiv-1(mod p), 2^{r_q}\equiv-1(mod q)}\) Z tych dwóch kongruencji oraz z czterech wcześniejszych wnioskujemy, że:\(\displaystyle{ (2k+1)*r_p=l*2r_q=q-1, (2m+1)*r_q=n*2r_p=p-1}\)
dla pewnych liczb naturalnych \(\displaystyle{ k,l,m,n}\) A to już daje sprzeczność, gdyż jak łatwo się przekonać, pierwsza równość implikuje: \(\displaystyle{ 2|r_p}\), druga równość, że: \(\displaystyle{ 4|r_q}\), i wtedy pierwsza równość że \(\displaystyle{ 8|r_p}\) i druga równość że \(\displaystyle{ 16|r_q}\) itd. bez końca.
ODPOWIEDZ