Reszty kwadratowe mod n

[kesi]

Wiem co to jest reszta kwadratowa mod n, jest to liczba a, która jest resztą kwadratową modulo n jeśli istnieje rozwiązanie następującego równania:

\(\displaystyle{ x^2 \equiv a \left( mod n\right)}\)

A jeśli takie rozwiązanie nie istnieje to nazywamy liczbę a nieresztą kwadratową modulo n.

Ale jak określa się to w praktyce??
Mógłby ktoś pokazać mi to na przykładzie?

Na wykładzie był następ. przykład:

\(\displaystyle{ n=7}\)

\(\displaystyle{ 1^2 \equiv 1\left( mod 7\right)}\)
\(\displaystyle{ 2^2 \equiv 4\left( mod 7\right)}\)
\(\displaystyle{ 3^2 \equiv 2\left( mod 7\right)}\)
\(\displaystyle{ 4^2 \equiv 2\left( mod 7\right)}\)
\(\displaystyle{ 5^2 \equiv 4\left( mod 7\right)}\)
\(\displaystyle{ 6^2 \equiv 1\left( mod 7\right)}\)

Rozwiązanie było nastepujące:

Liczby \(\displaystyle{ {1,2,4}}\) są resztami kwadrat. mod 7.
Liczby \(\displaystyle{ {3,5,6}}\) są nieresztami kwadrat. mod 7.


Dlaczego tak? Skąd sie to bierze?

[bakala12]

Po pierwsze to jeszcze \(\displaystyle{ 0}\) jest resztą kwadratową.
Skąd to się bierze? Sprawdzamy jakie reszty z dzielenia przez \(\displaystyle{ 7}\) może dawać kwadrat liczby całkowitej. No więc powinniśmy wziąć każdą liczbę całkowitą, podnieść ją do kwadratu i wziąć modulo \(\displaystyle{ 7}\). Ale nie trzeba sprawdzać osobno każdej liczby, wystarczy sprawdzić od zera do sześć, bo to są reszty (zwykłe) z dzielenia przez \(\displaystyle{ 7}\), a jedna z własności kongruencji mówi, że jeżeli
\(\displaystyle{ x\equiv r\pmod{7} \Rightarrow x^{2}\equiv r^{2}\pmod{7}}\). Wobec tego wszystkie reszty kwadratowe można wyznaczyć sprawdzając tylko \(\displaystyle{ 0,1,2,3,4,5,6}\). I tak się sprawdza dla dowolnej liczby, nie tylko dla siódemki.

[eMaerthin]

\(\displaystyle{ 7}\) to mała liczba, więc przegląd zupełny daje radę. Istnieje lepsza (szybsza) metoda dla ogólnych wartości \(\displaystyle{ p\in\mathbb{P}}\).
Aby sprawdzić, czy \(\displaystyle{ a}\) jest resztą kwadratową modulo liczba pierwsza \(\displaystyle{ p}\) należy obliczyć wartość \(\displaystyle{ a^{\frac{p-1}{2}}\pmod{p}}\). Taka liczba może być równa tylko \(\displaystyle{ 1}\) lub \(\displaystyle{ p-1}\), przy czym \(\displaystyle{ 1}\) pojawia się wtedy i tylko wtedy, gdy \(\displaystyle{ a}\) jest resztą kwadratową modulo \(\displaystyle{ p}\).

Przykład 1:
Sprawdźmy, czy \(\displaystyle{ 3}\) jest resztą kwadratową modulo \(\displaystyle{ 7}\):
\(\displaystyle{ 3^{\frac{7-1}{2}}=3^3\equiv 6=7-1\pmod{7}}\), zatem \(\displaystyle{ 3}\) jest nieresztą kwadratową modulo \(\displaystyle{ 7}\).

Przykład 2:
Bezpośrednie obliczenie, że \(\displaystyle{ 2^3\equiv1\pmod{7}}\) przekonuje nas, że \(\displaystyle{ 2}\) jest resztą kwadratową modulo \(\displaystyle{ 7}\).