Prawo wzajemności reszt kwadratowych

W części IV podręcznika Disquisitiones Arithmeticae opublikowanego w 1801 roku Gauss przedstawił dowód prawa wzajemności reszt kwadratowych.

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.

Twierdzenie

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

$x^2\equiv p(\mathrm{m}\mathrm{o}\mathrm{d}q)$

ma rozwiązanie $x$ wtedy i tylko wtedy, gdy kongruencja

$y^2\equiv q(\mathrm{m}\mathrm{o}\mathrm{d}p)$

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

$x^2\equiv p(\mathrm{m}\mathrm{o}\mathrm{d}q)$

ma rozwiązanie $x$ wtedy i tylko wtedy, gdy kongruencja

$y^2\equiv q(\mathrm{m}\mathrm{o}\mathrm{d}p)$

nie ma rozwiązania $y.$

Korzystając z symbolu Legendre’a,

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

oba stwierdzenia można zapisać następująco:

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

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

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