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{\pmod {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{cases}{\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{cases}}$

Jeśli $a\equiv b{\pmod {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\not \equiv 0{\pmod {p}}$, to $a$ jest resztą kwadratową modulo $p$ wtedy i tylko wtedy, gdy zachodzi kongruencja

$a^{\frac {p-1}{2}}\equiv 1{\pmod {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}}{\pmod {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