Legendre, Gauss, Jacobi et les autres...

Définition : a est résidu quadratique modulo n (ou encore résidu quadratique de n) si et seulement si a est un carré dans ${\mathbb Z}/n{\mathbb Z}$. Eh oui ! C'est aussi simple que cela.

Exemple : Dans ${\mathbb Z}/6{\mathbb Z}~: 0 = 0^2, 1 = 1^2 = 5^2, 3 =3^2, 4 = 2^2 = 4^2$ sont des résidus quadratiques ; 2 et 5 sont non résidus (sous entendu : quadratiques modulo 6).

Le terme ``résidu quadratique'' est fort poétique mais nous nous efforcerons, lorsqu'il n'y aura pas ambiguïté, à employer le terme ``carré'' ; ce dernier ayant l'avantage d'être bien plus explicite que le terme ``résidu quadratique'' qui, ne faisant qu'esbroufe, ralentit la compréhension des énoncés. Par ailleurs, nous dirons que deux nombres sont ``étrangers'' plutôt que de dire qu'ils sont ``premiers entre eux'', évitant ainsi une polysémie néfaste.

La notion de résidu quadratique apparaît dans un mémoire d'Euler de 1754-1755. D'aucuns, qui ne sont pas mathématiciens, se diront que c'est encore là une futilité de matheux, d'autres, qui le sont, se diront que c'est là une futilité d'arithméticien. Eh bien ! Nous allons nous efforcer, tout au long de ce mémoire, de démontrer le profond intérêt de cette futilité, de ces carrés carrément sans intérêt.

Les jolies formules se succéderont mais, étant conscient que l'esthétique n'est pas un motif d'intérêt pour beaucoup, nous verrons donc, pour ces réfractaires, quelques applications avec les tests de primalité, dont le test de Pépin. Cette miette mathématique est également à la base d'algorithmes de factorisation, avec la méthode de Gauss et celle de Kraïtchik (1920), ancêtre du moderne ``algorithme de factorisation par crible quadratique'' de Carl Pomerance (1990). La lecture du §explicitera ce qu'on peut entendre par intérêt.

Comment savoir si a est un carré modulo n ? Construire la table des carrés de ${\mathbb Z}/n{\mathbb Z}$ devient vite fastidieux, si n est grand. Legendre donne un algorithme simple pour répondre à cette question. Celui-ci repose sur un résultat puissant de la théorie des nombres : la loi de réciprocité quadratique. Le premier à l'avoir énoncée (sans preuve) est Euler en 1783, après l'avoir frôlée en 1772. Indépendamment, Legendre l'énonce en 1785 avec une preuve incomplète, toujours insuffisante dans sa Théorie des nombres, en 1798. Gauss en trouva une preuve à l'âge de 18 ans, au bout d'un an de recherches, et en exposera la première démonstration rigoureuse dans ses Recherches arithmétiques en 1801.

Gauss considérait cette loi comme le joyau de l'arithmétique, l'appelant même le ``théorème d'or'' ; il en donnera sept démonstrations différentes. Aujourd'hui, des spécialistes en ont recensé au moins 163, on pourra en trouver une produite par un générateur informatique de théorèmes dans A mechanical proof of quadratic reciprocity, Journal of Automated Reasoning, 1992 de D. Russinoff et nous vous renvoyons à l'American Mathematical Monthly d'avril 1963 pour l'énoncé de la 152^e preuve de la loi de réciprocité quadratique, qui comme la plupart est basée sur le lemme de Gauss (voir §). En métamathématique, on dit qu'un tel théorème, aux démonstrations foisonnantes, a un degré d'ambiguïté élevé. Il en est de même, par exemple, du théorème de Pythagore ou du théorème de l'infinitude des nombres premiers. On en trouvera une douzaine copurchics dans [Ribenboim] (les noms entre crochets renvoient aux références bibliographiques à la fin du document) ; nous en donnerons une dans le § sur les progressions arithmétiques.

En revanche, le théorème des nombres premiers, qui a fêté l'an dernier son centenaire, n'est pas ambigu : il n'a pour l'instant que deux démonstrations. En effet, quoique conjecturé depuis Legendre et Gauss, et après des progrès dus à Tchebychev et Riemann, il ne fut prouvé qu'en 1896, par Hadamard et de La Vallée-Poussin, indépendamment l'un de l'autre. Ce n'est qu'en 1949 qu'on en trouva une démonstration 'élémentaire' (i.e. n'utilisant ni la fonction $\zeta$ de Riemann ni la théorie des fonctions holomorphes) due à Erdös et Selberg ( médaille Fields en 1950). On trouvera une version améliorée de cette démonstration dans [Francinou].

La plus simple manifestation des lois de réciprocité est celle, déjà connue par Pierre de Fermat, qui affirme que les seuls diviseurs premiers de x²+1 sont 2 et des nombres premiers du type 1+4k (voir §). Avec l'aide du symbole de Legendre, ceci se note

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