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≠q, on a
(pq)⋅(qp)=(−1)p−12q−12.
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
(ap). En effet, elle permet de remplacer un symbole
(pq) par
(qp), tout en faisant attention à rajouter le signe
(−1)p−12q−12. 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 (78103). 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 (abp)=(ap)(bp) précédemment mentionnée :
(78103)=(2103)(3103)(13103). On sait déjà que (2103)=1 car 103≡−1(mod8) (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
(78103)=−(1033)(10313)=−(13)(1213), 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 (13)=1, et donc
(78103)=−(1213)=−(−113). Puisque 13≡1(mod4), on a (−113)=1 et on a donc prouvé que
(78103)=−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
(2p) suivant
p de calculer tous les symboles de Legendre. En effet, à chaque fois que l'on est en présence d'un symbole
(ap), 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.