Reszta kwadratowa modulo

Reszta kwadratowa modulo $p$ (gdzie $p$ jest liczbą pierwszą) – w teorii liczb, taka liczba całkowita $a,$ że istnieje rozwiązanie kongruencji:

$x^2\equiv a(\mathrm{mod}p).$

Jeśli powyższa kongruencja nie ma rozwiązania dla pewnej liczby całkowitej $a$, to taką liczbę nazywamy nieresztą kwadratową modulo $p$.

Własności

Symbol Legendre'a

Wartość $\left(\frac{a}{p}\right)$ symbolu Legendre'a określamy wzorem:

$\left(\frac{a}{p}\right)=\{\begin{array}{cc}\phantom{-}0,& \text{jeśli }p\mid a,\\ \phantom{-}1,& \text{jeśli }a\text{ jest resztą kwadratową modulo }p,\\ -1,& \text{jeśli }a\text{ jest nieresztą kwadratową modulo }p.\end{array}$

Jeśli $a\equiv b(\mathrm{mod}p),$ to $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$. Symbol Legendre’a jest również funkcją ściśle multiplikatywną licznika:

$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$

Kryterium Eulera

Jeśli $p$ jest liczbą pierwszą większą od 2 i $a$ jest liczbą całkowitą spełniającą $a\equiv ̸0(\mathrm{mod}p)$, to $a$ jest resztą kwadratową modulo $p$ wtedy i tylko wtedy, gdy zachodzi kongruencja

$a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p).$

Z wykorzystaniem symbolu Legendre'a kryterium to można zapisać następująco:

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$.

Prawo wzajemności reszt kwadratowych

Dla różnych liczb pierwszych $p$ i $q$ większych od 2 zachodzi równość

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)\equiv (-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$

Przykłady

• Kwadrat dowolnej liczby całkowitej kończy się jedną z cyfr: 0, 1, 4, 5, 6, 9. Oznacza to, że liczby te są resztami kwadratowymi modulo 10.
• Resztami kwadratowymi modulo 8 są liczby 0, 1 i 4. Nieresztami są liczby 2, 3, 5, 6, 7. Wynika stąd, że kwadrat dowolnej liczby nieparzystej daje z dzielenia przez 8 resztę 1.

Zobacz też

• kryterium Eulera
• niereszta kwadratowa modulo
• symbol Jacobiego
• symbol Legendre’a