Znajdz takie pary liczb pierwszych , ze:
- mol_ksiazkowy
- 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
-
- 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:
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.
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.