La loi de réciprocité quadratique s'énonce comme suit. Elle fut conjecturée par Euler et Legendre et prouvée par Gauss.
Loi de réciprocité quadratique
Pour tous nombres premiers impairs $p$ et $q$ avec $p \neq q$, on a
$$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}.$$
Nous n'en donnons pas la démonstration.
L'intérêt de cette formule est qu'elle permet de calculer plus facilement tout symbole de Legendre $\left(\frac{a}{p}\right)$. En effet, elle permet de remplacer un symbole $\left(\frac{p}{q}\right)$ par $\left(\frac{q}{p}\right)$, tout en faisant attention à rajouter le signe $(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$. Autrement dit, il faut simplement rajouter un signe $-$ si $p$ et $q$ sont tous les deux égaux à $3$ modulo $4$.
À titre d'exemple, examinons le problème suivant :
Solution
On remarque tout de suite que l'existence d'une solution est équivalente à dire que $78$ est un résidu quadratique modulo $103$. Il s'agit donc dans un premier temps de voir si cela est vrai pour déterminer si une solution existe. On doit dès lors calculer le symbole $\left(\frac{78}{103}\right)$. Avant de pouvoir utiliser la loi de réciprocité quadratique, il faut que le numérateur soit premier. On commence donc par décomposer $78$ en facteurs premiers en utilisant la formule $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)$ précédemment mentionnée :
$$\left(\frac{78}{103}\right) = \left(\frac{2}{103}\right)\left(\frac{3}{103}\right) \left(\frac{13}{103}\right).$$ On sait déjà que $\left(\frac{2}{103}\right) = 1$ car $103 \equiv -1 \pmod 8$ (voir formule dans le cas $a = 2$). On peut à présent utiliser la loi de réciprocité quadratique pour chacun des deux termes. Vu que $3$ et $103$ sont tous les deux égaux à $3$ modulo $4$, inverser ce symbole va faire apparaître un signe $-$. Par contre, $13$ est égal à $1$ modulo $4$ donc ce symbole n'apportera pas de signe $-$. On a ainsi
$$\left(\frac{78}{103}\right) = - \left(\frac{103}{3}\right) \left(\frac{103}{13}\right) = -\left(\frac{1}{3}\right) \left(\frac{12}{13}\right),$$ où on peut remplacer $103$ par sa valeur modulo $3$ dans le premier symbole et par sa valeur modulo $13$ dans le deuxième, comme la valeur d'un symbole ne dépend que de la valeur du numérateur modulo le dénominateur. On a clairement $\left(\frac{1}{3}\right) = 1$, et donc
$$\left(\frac{78}{103}\right) = - \left(\frac{12}{13}\right) = - \left(\frac{-1}{13}\right).$$ Puisque $13 \equiv 1 \pmod 4$, on a $\left(\frac{-1}{13}\right) = 1$ et on a donc prouvé que
$$\left(\frac{78}{103}\right) = -1,$$ ce qui signifie que $78$ est un non-résidu quadratique modulo $103$ et qu'il n'y a aucun couple $(x,y)$ satisfaisant l'énoncé.
Il est possible grâce à cette loi et à la valeur de $\left(\frac{2}{p}\right)$ suivant $p$ de calculer tous les symboles de Legendre. En effet, à chaque fois que l'on est en présence d'un symbole $\left(\frac{a}{p}\right)$, on peut décomposer $a$ en ses facteurs premiers, trouver la valeur des symboles apparaissant avec un numérateur égal à $2$, et retourner les autres symboles en utilisant la loi de réciprocité quadratique. En remplaçant le numérateur obtenu par sa valeur modulo le dénominateur et en répétant l'opération, les nombres en jeu deviennent de plus en plus petits et on finit par pouvoir tout calculer.