Sprawdzić czy 349

[max123321]

Sprawdzić czy \(\displaystyle{ 349}\) jest resztą kwadratową \(\displaystyle{ \mod 2010}\).

Jak to zrobić?

[HelperNES]

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}.}\)

[max123321]

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?

[HelperNES]

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}\)

[max123321]

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}\)?

[PoweredDragon]

"Prosty przykład"

Brał pewnie liczby postaci
\(\displaystyle{ 349+a \cdot 2010}\)
I pierwiastkował