Niech \(\displaystyle{ p}\) będzie liczbą pierwszą i istnieje \(\displaystyle{ a}\) takie, że \(\displaystyle{ a^2 \equiv -2 \pmod{p}}\). Udowodnić, że choć jedno z równań
\(\displaystyle{ \begin{cases} x^2+2y^2=p \\ x^2+2y^2=2p \end{cases}}\)
ma rozwiązanie (w liczbach całkowitych \(\displaystyle{ x, y}\)).
Problem z liczbami a i p
- 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
Problem z liczbami a i p
Ostatnio zmieniony 28 maja 2022, o 19:39 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
- arek1357
- Użytkownik
- Posty: 5703
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 129 razy
- Pomógł: 524 razy
Re: Problem z liczbami a i p
żeby takie a istniało, to musi zachodzić albo:
\(\displaystyle{ p=2, a=0}\)
I wtedy np:
\(\displaystyle{ x=0, y=1}\)
Dla \(\displaystyle{ p>2}\)
chcąc aby:
\(\displaystyle{ a^2=-2 (\mod p)}\)
musi być \(\displaystyle{ -2}\) resztą kwadratową modulo \(\displaystyle{ p}\)
Co znaczy:
\(\displaystyle{ \left( \frac{-2}{p} \right) =\left( \frac{2}{p} \right) \cdot \left( \frac{-1}{p} \right) =\left( -1\right)^{ \frac{(p+1)(p-1)}{8} } \cdot \left( -1\right)^{ \frac{p-1}{2} }}\)
Wynik ten powinien wyjść jeden żeby \(\displaystyle{ -2}\) była reszta kwadratową inaczej będzie nieresztą
Co po niezbyt głębokiej analizie pozwoli zauważyć, że:
\(\displaystyle{ p=8k+1 \vee p=8k+3}\)
Dla tego typu liczb pierwszych równanie:
\(\displaystyle{ x^2+2y^2=p}\)
ma rozwiązanie...
Ponieważ:
\(\displaystyle{ \left( \frac{x}{y} \right)^2=-2 (\mod p) }\)
\(\displaystyle{ \frac{x}{y}=a ( \mod p) }\)
Jeżeli mam rozwiązanie (1)
\(\displaystyle{ (x,y)}\)
To rozwiązaniem:
\(\displaystyle{ x^2+2y^2=2p}\)
Będzie:
\(\displaystyle{ (2y,x)}\)
\(\displaystyle{ p=2, a=0}\)
I wtedy np:
\(\displaystyle{ x=0, y=1}\)
Dla \(\displaystyle{ p>2}\)
chcąc aby:
\(\displaystyle{ a^2=-2 (\mod p)}\)
musi być \(\displaystyle{ -2}\) resztą kwadratową modulo \(\displaystyle{ p}\)
Co znaczy:
\(\displaystyle{ \left( \frac{-2}{p} \right) =\left( \frac{2}{p} \right) \cdot \left( \frac{-1}{p} \right) =\left( -1\right)^{ \frac{(p+1)(p-1)}{8} } \cdot \left( -1\right)^{ \frac{p-1}{2} }}\)
Wynik ten powinien wyjść jeden żeby \(\displaystyle{ -2}\) była reszta kwadratową inaczej będzie nieresztą
Co po niezbyt głębokiej analizie pozwoli zauważyć, że:
\(\displaystyle{ p=8k+1 \vee p=8k+3}\)
Dla tego typu liczb pierwszych równanie:
\(\displaystyle{ x^2+2y^2=p}\)
ma rozwiązanie...
Ponieważ:
\(\displaystyle{ \left( \frac{x}{y} \right)^2=-2 (\mod p) }\)
\(\displaystyle{ \frac{x}{y}=a ( \mod p) }\)
Jeżeli mam rozwiązanie (1)
\(\displaystyle{ (x,y)}\)
To rozwiązaniem:
\(\displaystyle{ x^2+2y^2=2p}\)
Będzie:
\(\displaystyle{ (2y,x)}\)