Znajdź wszystkie liczby pierwsze nieparzyste
-
- Użytkownik
- Posty: 281
- Rejestracja: 2 wrz 2009, o 21:10
- Płeć: Mężczyzna
- Podziękował: 9 razy
- Pomógł: 2 razy
Znajdź wszystkie liczby pierwsze nieparzyste
Znajdź wszystkie liczby pierwsze nieparzyste \(\displaystyle{ p}\), takie że \(\displaystyle{ -10}\) jest resztą kwadratową modulo \(\displaystyle{ p}\).
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
Znajdź wszystkie liczby pierwsze nieparzyste
Widzimy, że \(\displaystyle{ p=5}\) spełnia warunki zadania, załóżmy więc, że \(\displaystyle{ p \neq 5}\), rozpatrzmy 2 przypadki:
1) \(\displaystyle{ p = 4a+1}\) dla pewnego naturalnego a, wtedy:
\(\displaystyle{ 1 = \left( \frac{-10}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{2}{p} \right) \left( \frac{5}{p} \right) = \left( \frac{2}{p} \right) \left( \frac{5}{p} \right) = (-1)^{\frac{p^2-1}{8}} \left( \frac{5}{p} \right) = (-1)^{a(2a+1)} \left( \frac{5}{p} \right) (*)}\)
Rozpatrzmy znowu 2 przypadki:
1a) \(\displaystyle{ a = 2b}\) dla pewnego naturalnego b, wtedy \(\displaystyle{ p = 8b+1}\)
\(\displaystyle{ (*) = 1 = \left( \frac{5}{8b+1} \right) = \left( \frac{3b+1}{5} \right)}\)
Więc \(\displaystyle{ 3b+1}\) ma być resztą kwadratową \(\displaystyle{ \pmod{5}}\) skąd może być jedynie:
\(\displaystyle{ 3b+1 \equiv 0 \pmod{5} \vee 3b+1 \equiv 1 \pmod{5} \vee 3b+1 \equiv 4 \pmod{5} \Leftrightarrow b = 5n+3 \vee b = 5n \vee b = 5n+1}\),
z tego dostajemy \(\displaystyle{ p = 40n+1 \vee p = 40n+9 \vee p = 40n+25}\) ale ostatni przypadek możemy od razu odrzucić, ponieważ będzie to liczba różna od 5 i podzielna przez 5, więc nie będzie mogła być pierwsza. Czyli stąd mamy \(\displaystyle{ p = 40n + 1 \vee p = 40n+9}\) dla dowolnej naturalnej n, takiej, że \(\displaystyle{ p \in \mathbb{P}}\), rozpatrzmy drugi przypadek:
1b) \(\displaystyle{ a = 2b+1}\), wtedy \(\displaystyle{ p = 8b+5}\), skąd:
\(\displaystyle{ (*) = 1 = -\left( \frac{5}{8b+5} \right) = -\left( \frac{3b}{5} \right)}\) czyli 3b ma być nieresztą kwadratową \(\displaystyle{ \pmod{5}}\) skąd \(\displaystyle{ 3b \equiv 2 \pmod{5} \vee 3b \equiv 3 \pmod{5} \Leftrightarrow b = 5n+4 \vee b = 5n+1}\) wtedy dostajemy nowe możliwości \(\displaystyle{ p = 40n+37 \vee p = 40n+13}\)
Rozpatrzmy drugi przypadek:
\(\displaystyle{ p = 4a+3}\), wtedy:
\(\displaystyle{ 1 = \left( \frac{-10}{p} \right) = \left( \frac{-1}{p} \right) \cdot \left( \frac{2}{p} \right) \cdot \left( \frac{5}{p} \right) = -\left( \frac{2}{p} \right)\left( \frac{5}{p} \right) = -(-1)^{\frac{p^2-1}{8}} \left( \frac{5}{p} \right) = -(-1)^{(a+1)(2a+1)}\left( \frac{5}{p} \right)(**)}\)
2a) \(\displaystyle{ a = 2b}\) wtedy \(\displaystyle{ p = 8b+3}\):
\(\displaystyle{ 1 = (**) = \left( \frac{5}{p} \right) = \left( \frac{3b+3}{5} \right)}\) skąd
\(\displaystyle{ 3b+3 \equiv 0 \pmod{5} \vee 3b+3 \equiv 1 \pmod{5} \vee 3b+3 \equiv 4\pmod{5} \Leftrightarrow b = 5n+4 \vee b = 5n+1 \vee b = 5n+2}\)
skąd dostajemy \(\displaystyle{ p = 40n+11 \vee p = 40n+19 \vee p = 40n+35}\), ostatnie odrzucamy dostając \(\displaystyle{ p = 40n+11 \vee p = 40n+19}\)
2b) \(\displaystyle{ a = 2b+1}\) wtedy \(\displaystyle{ p = 8b+7}\)
\(\displaystyle{ 1 = (**) = -\left( \frac{5}{8b+7} \right) = -\left( \frac{3b+2}{5} \right)}\) skąd wynika \(\displaystyle{ 3b+2 \equiv 2 \pmod{5} \vee 3b+2 \equiv 3\pmod{5} \Leftrightarrow b = 5n \vee b = 5n+2}\) skąd dostajemy \(\displaystyle{ p = 40n+7 \vee p = 40n+23}\)
Reasumując, liczba \(\displaystyle{ -10}\) jest resztą kwadratową \(\displaystyle{ \pmod{p}}\) gdzie \(\displaystyle{ p \in \mathbb{P} \setminus \lbrace 2 \rbrace}\) wtedy i tylko wtedy, gdy \(\displaystyle{ p=5}\) lub dla pewnego naturalnego n:
\(\displaystyle{ p = 40n+r \wedge r \in \lbrace 1;7;9;11;13;19;23;37\rbrace}\)
1) \(\displaystyle{ p = 4a+1}\) dla pewnego naturalnego a, wtedy:
\(\displaystyle{ 1 = \left( \frac{-10}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{2}{p} \right) \left( \frac{5}{p} \right) = \left( \frac{2}{p} \right) \left( \frac{5}{p} \right) = (-1)^{\frac{p^2-1}{8}} \left( \frac{5}{p} \right) = (-1)^{a(2a+1)} \left( \frac{5}{p} \right) (*)}\)
Rozpatrzmy znowu 2 przypadki:
1a) \(\displaystyle{ a = 2b}\) dla pewnego naturalnego b, wtedy \(\displaystyle{ p = 8b+1}\)
\(\displaystyle{ (*) = 1 = \left( \frac{5}{8b+1} \right) = \left( \frac{3b+1}{5} \right)}\)
Więc \(\displaystyle{ 3b+1}\) ma być resztą kwadratową \(\displaystyle{ \pmod{5}}\) skąd może być jedynie:
\(\displaystyle{ 3b+1 \equiv 0 \pmod{5} \vee 3b+1 \equiv 1 \pmod{5} \vee 3b+1 \equiv 4 \pmod{5} \Leftrightarrow b = 5n+3 \vee b = 5n \vee b = 5n+1}\),
z tego dostajemy \(\displaystyle{ p = 40n+1 \vee p = 40n+9 \vee p = 40n+25}\) ale ostatni przypadek możemy od razu odrzucić, ponieważ będzie to liczba różna od 5 i podzielna przez 5, więc nie będzie mogła być pierwsza. Czyli stąd mamy \(\displaystyle{ p = 40n + 1 \vee p = 40n+9}\) dla dowolnej naturalnej n, takiej, że \(\displaystyle{ p \in \mathbb{P}}\), rozpatrzmy drugi przypadek:
1b) \(\displaystyle{ a = 2b+1}\), wtedy \(\displaystyle{ p = 8b+5}\), skąd:
\(\displaystyle{ (*) = 1 = -\left( \frac{5}{8b+5} \right) = -\left( \frac{3b}{5} \right)}\) czyli 3b ma być nieresztą kwadratową \(\displaystyle{ \pmod{5}}\) skąd \(\displaystyle{ 3b \equiv 2 \pmod{5} \vee 3b \equiv 3 \pmod{5} \Leftrightarrow b = 5n+4 \vee b = 5n+1}\) wtedy dostajemy nowe możliwości \(\displaystyle{ p = 40n+37 \vee p = 40n+13}\)
Rozpatrzmy drugi przypadek:
\(\displaystyle{ p = 4a+3}\), wtedy:
\(\displaystyle{ 1 = \left( \frac{-10}{p} \right) = \left( \frac{-1}{p} \right) \cdot \left( \frac{2}{p} \right) \cdot \left( \frac{5}{p} \right) = -\left( \frac{2}{p} \right)\left( \frac{5}{p} \right) = -(-1)^{\frac{p^2-1}{8}} \left( \frac{5}{p} \right) = -(-1)^{(a+1)(2a+1)}\left( \frac{5}{p} \right)(**)}\)
2a) \(\displaystyle{ a = 2b}\) wtedy \(\displaystyle{ p = 8b+3}\):
\(\displaystyle{ 1 = (**) = \left( \frac{5}{p} \right) = \left( \frac{3b+3}{5} \right)}\) skąd
\(\displaystyle{ 3b+3 \equiv 0 \pmod{5} \vee 3b+3 \equiv 1 \pmod{5} \vee 3b+3 \equiv 4\pmod{5} \Leftrightarrow b = 5n+4 \vee b = 5n+1 \vee b = 5n+2}\)
skąd dostajemy \(\displaystyle{ p = 40n+11 \vee p = 40n+19 \vee p = 40n+35}\), ostatnie odrzucamy dostając \(\displaystyle{ p = 40n+11 \vee p = 40n+19}\)
2b) \(\displaystyle{ a = 2b+1}\) wtedy \(\displaystyle{ p = 8b+7}\)
\(\displaystyle{ 1 = (**) = -\left( \frac{5}{8b+7} \right) = -\left( \frac{3b+2}{5} \right)}\) skąd wynika \(\displaystyle{ 3b+2 \equiv 2 \pmod{5} \vee 3b+2 \equiv 3\pmod{5} \Leftrightarrow b = 5n \vee b = 5n+2}\) skąd dostajemy \(\displaystyle{ p = 40n+7 \vee p = 40n+23}\)
Reasumując, liczba \(\displaystyle{ -10}\) jest resztą kwadratową \(\displaystyle{ \pmod{p}}\) gdzie \(\displaystyle{ p \in \mathbb{P} \setminus \lbrace 2 \rbrace}\) wtedy i tylko wtedy, gdy \(\displaystyle{ p=5}\) lub dla pewnego naturalnego n:
\(\displaystyle{ p = 40n+r \wedge r \in \lbrace 1;7;9;11;13;19;23;37\rbrace}\)
-
- Użytkownik
- Posty: 102
- Rejestracja: 8 sie 2011, o 20:59
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
- Pomógł: 14 razy
Znajdź wszystkie liczby pierwsze nieparzyste
Czasochłonne, ale bardzo ładne rozwiązanie. Zastanawiam się, czy istnieje jakiś bardziej zwięzły argument?