Sprawdzić czy \(\displaystyle{ 349}\) jest resztą kwadratową \(\displaystyle{ \mod 2010}\).
Jak to zrobić?
Sprawdzić czy 349
-
- Użytkownik
- Posty: 70
- Rejestracja: 2 lut 2017, o 10:12
- Płeć: Mężczyzna
- Lokalizacja: Stęszew
- Podziękował: 5 razy
- Pomógł: 14 razy
Re: Sprawdzić czy 349
Prosto
Definicja:
Resztą kwadratową modulo \(\displaystyle{ p}\) nazywamy taką liczbę całkowitą \(\displaystyle{ a}\), że równanie:
\(\displaystyle{ x^2\equiv a\pmod{p}}\), ma rozwiązanie.
W takim razie musisz rozwiązać równanie \(\displaystyle{ x^2\equiv 349\pmod{2010}.}\)
Definicja:
Resztą kwadratową modulo \(\displaystyle{ p}\) nazywamy taką liczbę całkowitą \(\displaystyle{ a}\), że równanie:
\(\displaystyle{ x^2\equiv a\pmod{p}}\), ma rozwiązanie.
W takim razie musisz rozwiązać równanie \(\displaystyle{ x^2\equiv 349\pmod{2010}.}\)
Ostatnio zmieniony 3 sty 2019, o 15:55 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Sprawdzić czy 349
A dobra chyba już wiem. Trzeba obliczyć symbol Jacobiego \(\displaystyle{ \left( \frac{349}{2010} \right)}\).
Liczę tak:
\(\displaystyle{ \left( \frac{349}{2010} \right)=\left( \frac{349}{3} \right)\left( \frac{349}{670} \right)=\left( \frac{1}{3} \right)\left( -1 \right)^{348*669/4}\left( \frac{670}{349} \right)=\left( \frac{670}{349} \right)=\left( \frac{321}{349} \right)=\left( \frac{3}{349} \right)\left( \frac{107}{349} \right)=\left( -1 \right)^{2*348/4}\left( \frac{349}{3} \right)\left( -1\right)^{106*348/4}\left( \frac{349}{107} \right)=\left( \frac{1}{3} \right)\left( \frac{349}{107} \right)=\left( \frac{28}{107} \right)=\left( \frac{7}{107} \right)=\left( -1 \right)^{6*106/4}\left( \frac{107}{7} \right)=-\left( \frac{2}{7} \right)=\left( -1 \right)\left( -1 \right)^6=-1}\)
Czyli \(\displaystyle{ 349}\) nie jest resztą kwadratową modulo \(\displaystyle{ 2010}\).
Tak jest dobrze?
Liczę tak:
\(\displaystyle{ \left( \frac{349}{2010} \right)=\left( \frac{349}{3} \right)\left( \frac{349}{670} \right)=\left( \frac{1}{3} \right)\left( -1 \right)^{348*669/4}\left( \frac{670}{349} \right)=\left( \frac{670}{349} \right)=\left( \frac{321}{349} \right)=\left( \frac{3}{349} \right)\left( \frac{107}{349} \right)=\left( -1 \right)^{2*348/4}\left( \frac{349}{3} \right)\left( -1\right)^{106*348/4}\left( \frac{349}{107} \right)=\left( \frac{1}{3} \right)\left( \frac{349}{107} \right)=\left( \frac{28}{107} \right)=\left( \frac{7}{107} \right)=\left( -1 \right)^{6*106/4}\left( \frac{107}{7} \right)=-\left( \frac{2}{7} \right)=\left( -1 \right)\left( -1 \right)^6=-1}\)
Czyli \(\displaystyle{ 349}\) nie jest resztą kwadratową modulo \(\displaystyle{ 2010}\).
Tak jest dobrze?
-
- Użytkownik
- Posty: 70
- Rejestracja: 2 lut 2017, o 10:12
- Płeć: Mężczyzna
- Lokalizacja: Stęszew
- Podziękował: 5 razy
- Pomógł: 14 razy
Re: Sprawdzić czy 349
Nie znam się ani na symbolu Legendre'a ani na Jacobiego, ale na pewno jest coś nie tak..
Prosty przykład:
\(\displaystyle{ 143^2 = 20449 = 20100 + 349 = 2010 \cdot 10 + 349 = 349}\) w modulo \(\displaystyle{ 2010}\)
Co daje nam odwrotny rezultat do Twojego.
Jest też coś co w Twoich obliczeniach szczypie mnie w oczy: W definicji symbolu Jacobiego widzę, że dany symbol równa się iloczynowi danych symboli gdzie "mianownikami" są liczby pierwsze, które są zawarte w faktoryzacji pierwszego "manownika" .
Czyli:
\(\displaystyle{ \left(\frac{349}{2010}\right) = \left(\frac{349}{2}\right)\left(\frac{349}{3}\right)\left(\frac{349}{5}\right)\left(\frac{349}{67}\right)}\)
Lecz jak to dalej liczyć nie wiem, ale patrząc na przykład wyżej wiadomo, że wynik musi być równy \(\displaystyle{ 1}\)
Prosty przykład:
\(\displaystyle{ 143^2 = 20449 = 20100 + 349 = 2010 \cdot 10 + 349 = 349}\) w modulo \(\displaystyle{ 2010}\)
Co daje nam odwrotny rezultat do Twojego.
Jest też coś co w Twoich obliczeniach szczypie mnie w oczy: W definicji symbolu Jacobiego widzę, że dany symbol równa się iloczynowi danych symboli gdzie "mianownikami" są liczby pierwsze, które są zawarte w faktoryzacji pierwszego "manownika" .
Czyli:
\(\displaystyle{ \left(\frac{349}{2010}\right) = \left(\frac{349}{2}\right)\left(\frac{349}{3}\right)\left(\frac{349}{5}\right)\left(\frac{349}{67}\right)}\)
Lecz jak to dalej liczyć nie wiem, ale patrząc na przykład wyżej wiadomo, że wynik musi być równy \(\displaystyle{ 1}\)
Ostatnio zmieniony 3 sty 2019, o 22:14 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Sprawdzić czy 349
Aj faktycznie widzę już błąd. W po trzeciej równości powinien być minus wszak \(\displaystyle{ \left( \frac{1}{3} \right)\left( -1 \right)^{348 \cdot 669/4}\left( \frac{670}{349} \right)=-\left( \frac{670}{349} \right)}\), a nie plus. Całe obliczenia:
\(\displaystyle{ \left( \frac{349}{2010} \right)=\left( \frac{349}{3} \right)\left( \frac{349}{670} \right)=\left( \frac{1}{3} \right)\left( -1 \right)^{348 \cdot 669/4}\left( \frac{670}{349} \right)=-\left( \frac{670}{349} \right)=-\left( \frac{321}{349} \right)=-\left( \frac{3}{349} \right)\left( \frac{107}{349} \right)=-\left( -1 \right)^{2 \cdot 348/4}\left( \frac{349}{3} \right)\left( -1\right)^{106 \cdot 348/4}\left( \frac{349}{107} \right)=-\left( \frac{1}{3} \right)\left( \frac{349}{107} \right)=-\left( \frac{28}{107} \right)=-\left( \frac{7}{107} \right)=-\left( -1 \right)^{6 \cdot 106/4}\left( \frac{107}{7} \right)=\left( \frac{2}{7} \right)=\left( -1 \right)^6=1}\)
Teraz już powinno być dobrze, ale będę wdzięczny jak ktoś sprawdzi te obliczenia.
A tak swoją drogą jak znalazłeś to \(\displaystyle{ 143^2}\)?
\(\displaystyle{ \left( \frac{349}{2010} \right)=\left( \frac{349}{3} \right)\left( \frac{349}{670} \right)=\left( \frac{1}{3} \right)\left( -1 \right)^{348 \cdot 669/4}\left( \frac{670}{349} \right)=-\left( \frac{670}{349} \right)=-\left( \frac{321}{349} \right)=-\left( \frac{3}{349} \right)\left( \frac{107}{349} \right)=-\left( -1 \right)^{2 \cdot 348/4}\left( \frac{349}{3} \right)\left( -1\right)^{106 \cdot 348/4}\left( \frac{349}{107} \right)=-\left( \frac{1}{3} \right)\left( \frac{349}{107} \right)=-\left( \frac{28}{107} \right)=-\left( \frac{7}{107} \right)=-\left( -1 \right)^{6 \cdot 106/4}\left( \frac{107}{7} \right)=\left( \frac{2}{7} \right)=\left( -1 \right)^6=1}\)
Teraz już powinno być dobrze, ale będę wdzięczny jak ktoś sprawdzi te obliczenia.
A tak swoją drogą jak znalazłeś to \(\displaystyle{ 143^2}\)?
Ostatnio zmieniony 4 sty 2019, o 20:17 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 817
- Rejestracja: 19 lis 2016, o 23:48
- Płeć: Mężczyzna
- wiek: 21
- Lokalizacja: Polska
- Podziękował: 3 razy
- Pomógł: 115 razy
Re: Sprawdzić czy 349
"Prosty przykład"
Brał pewnie liczby postaci
\(\displaystyle{ 349+a \cdot 2010}\)
I pierwiastkował
Brał pewnie liczby postaci
\(\displaystyle{ 349+a \cdot 2010}\)
I pierwiastkował