Considérons un nombre premier impair $p$ et calculons $a^2$, pour tout $a \in \mathbb{Z}_p-\{0\}$. Par exemple, pour $p=41$, on obtient $$1,4,9,16,25,36,8,23,40,18,39,21,5,32,20,10,2,37,33,31,31,33,37,2,10,20,32,5,21,39,18,40,23,8,36,25,16,9,4,1$$ (j'identifie ici un élément de $\mathbb{Z}_p$ avec un de ses représentants). Evidemment, comme $a^2 = (-a)^2$, la suite de nombres obtenue est palindromique, et comme $p$ est impair, chaque nombre apparaît un nombre pair de fois. Ordonnons la suite : $$1,1,2,2,4,4,5,5,8,8,9,9,10,10,16,16,18,18,20,20,21,21,23,23,25,25,31,31,32,32,33,33,36,36,37,37,39,39,40,40$$ On observe que tous les nombres apparaissent en fait exactement deux fois. Cela s'explique facilement : le polynôme $X^2 - A$ a au plus deux solutions dans le corps $\mathbb{Z}_p$, pour tout $A$ fixé. On en déduit que $\mathbb{Z}_p-\{0\}$ peut être partitionné en deux parties de même cardinal $(p-1)/2$, à savoir les nombres qui sont un carré, et qu'on appelle les résidus quadratiques, ici $$1,2,4,5,8,9,10,16,18,20,21,23,25,31,32,33,36,37,39,40 \, , $$ et les autres, qui sont n'en sont pas, et qu'on appelle les non-résidus quadratiques, ici $$ 3, 6, 7, 11, 12, 13, 14, 15, 17, 19, 22, 24, 26, 27, 28, 29, 30, 34, \ 35, 38 \, . $$ Mais comment savoir a priori si un nombre donné $A$ est un résidu quadratique ou non ?

Introduisons une notation utile. Si $A$ est un résidu quadratique (non nul) dans $\mathbb{Z}_p$, on écrit $\left( \frac{A}{p} \right)=1$, et si $A$ est un non-résidu quadratique, on écrit $\left( \frac{A}{p} \right)=-1$. Enfin, pour être complet on définit aussi $\left( \frac{0}{p} \right)=0$. Le symbole de Legendre ainsi défini revient à dire à quelle liste $A$ appartient. Mais comment le calculer ? Analysons la structure des listes ci-dessus. Clairement, la liste des carrés est un groupe, puisque $a^2 b^2 = (ab)^2$. D'autre part, la liste des non-carrés n'est pas un groupe, mais on se rend compte qu'en multipliant deux non-carrés, on obtient un carré ! Pour démontrer ce fait, notons simplement que le quotient de $\mathbb{Z}_p$ par le groupe distingué des carrés est $\mathbb{Z}_2$, et donc les règles de multiplication sont celles de $\mathbb{Z}_2$. On obtient donc aussi que le produit d'un carré par un non-carré est un non carré. Bref, la fonction $A \mapsto \left( \frac{A}{p} \right)$ est un morphisme de groupes multiplicatifs ! Par conséquent, pour calculer $\left( \frac{A}{p} \right)$, il suffit de connaître $\left( \frac{q}{p} \right)$ pour $q$ premier.

Il est maintenant temps d'énoncer la loi de réciprocité quadratique : étant donnés deux nombres premiers impairs distincts $p$ et $q$, on a $$\left( \frac{q}{p} \right) = (-1)^{(p-1)(q-1)/4} \left( \frac{p}{q} \right) \, . $$ Combinée à deux règles supplémentaires donnant la valeur de $\left( \frac{-1}{p} \right)$ (ceci vaut $1$ si et seulement si $p \equiv 1$ modulo $4$) et $\left( \frac{2}{p} \right)$ (ceci vaut $1$ si et seulement si $p \equiv \pm 1$ modulo $8$), et à la multiplicativité du symbole de Legendre, cette Loi permet de calculer aisément tout symbole de Legendre !

Par exemple, vérifions que $30$ n'est pas un carré modulo $41$. On calcule $$\left( \frac{30}{41} \right) = \left( \frac{2}{41} \right) \left( \frac{3}{41} \right)\left( \frac{5}{41} \right) =(1) \left( \frac{41}{3} \right) \left( \frac{41}{5} \right) = \left( \frac{-1}{3} \right) \left( \frac{1}{5} \right) = (-1)(1) = -1 \, . $$