Prawo wzajemności reszt kwadratowych – twierdzenie teorii liczb, które pozwala rozstrzygnąć, czy dana kongruencja stopnia 2 ma rozwiązanie. Prawo wzajemności reszt kwadratowych udowodnił Gauss, choć jego prawdziwość podejrzewali już Euler i Legendre.

Niech ${\displaystyle p}$ i ${\displaystyle q}$ będą dwiema różnymi, nieparzystymi liczbami pierwszymi. Wynika stąd natychmiast, że ${\displaystyle p}$ i ${\displaystyle q}$ przystają modulo 4 albo do 1, albo do 3 – jeśli choć jedna z tych liczb przystaje do 1 modulo 4, to kongruencja

${\displaystyle x^{2}\equiv p\ (\mathrm {mod} \ q)}$

ma rozwiązanie ${\displaystyle x}$ wtedy i tylko wtedy, gdy kongruencja

${\displaystyle y^{2}\equiv q\ (\mathrm {mod} \ p)}$

ma rozwiązanie ${\displaystyle y;}$ na ogół rozwiązania te będą różne. Jeśli natomiast obie liczby ${\displaystyle p}$ i ${\displaystyle q}$ przystają do 3 modulo 4, to kongruencja

${\displaystyle x^{2}\equiv p\ (\mathrm {mod} \ q)}$

ma rozwiązanie ${\displaystyle x}$ wtedy i tylko wtedy, gdy kongruencja

${\displaystyle y^{2}\equiv q\ (\mathrm {mod} \ p)}$

nie ma rozwiązania ${\displaystyle y.}$

Korzystając z symbolu Legendre’a,

${\displaystyle \left({\tfrac {p}{q}}\right)=1}$ jeśli ${\displaystyle p}$ jest resztą kwadratową modulo ${\displaystyle q}$ i ${\displaystyle -1}$ w przeciwnym wypadku,

oba stwierdzenia można zapisać następująco^[2]:

${\displaystyle \left({\tfrac {p}{q}}\right)\left({\tfrac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}.}$

Ponieważ ${\displaystyle {\tfrac {(p-1)(q-1)}{4}}}$ jest parzyste jeśli któraś z liczb ${\displaystyle p}$ lub ${\displaystyle q}$ przystaje do 1 modulo 4, i nieparzyste wtedy i tylko wtedy, gdy obie liczby ${\displaystyle p}$ i ${\displaystyle q}$ przystają do 3 modulo 4, ${\displaystyle \left({\tfrac {p}{q}}\right)\left({\tfrac {q}{p}}\right)}$ jest równe 1 jeśli któraś z liczb ${\displaystyle p}$ lub ${\displaystyle q}$ przystaje do 1 modulo 4 i –1 jeśli obie liczby ${\displaystyle p}$ i ${\displaystyle q}$ przystają do 3 modulo 4.

Znanych jest co najmniej 246 różnych dowodów prawa wzajemności reszt kwadratowych^[3].