Résidus quadratiques
Lois de réciprocité quadratique


Cyril Banderier


Maîtrise de mathématiques pures
Université de Rouen
Année 1996/1997


Warning : this a work I've done few years ago (when I was a student) and that I don't have updated, since, I discovered the most complete site I have ever seen on this subject, written by a number theorist who prepares a book on the subject : Franz Lemmermeyer.

Remarque : Je n'ai pas retouché à ce travail que j'ai fait il y a quelques années déjà. En revanche, pour ceux qui voudront en savoir plus, je leur conseille le site incontestatblement le plus complet sur les lois de réciprocités (en anglais), qui est dû au théoricien des nombres Franz Lemmermeyer


 
Résidus quadratiques

Résidus quadratiques
Lois de réciprocité quadratique




Cyril Banderier



Maîtrise de mathématiques pures
Université de Rouen
Année 1996/1997


Warning : this a work I've done few years ago (when I was a student) and that I don't have updated, since, I discovered the most complete site I have ever seen on this subject, written by a number theorist who prepares a book on the subject : Franz Lemmermeyer.

Remarque : Je n'ai pas retouché à ce travail que j'ai fait il y a quelques années déjà. En revanche, pour ceux qui voudront en savoir plus, je leur conseille le site incontestatblement le plus complet sur les lois de réciprocités (en anglais), qui est dû au théoricien des nombres Franz Lemmermeyer


 
Table des matières

Table des matières


Prolégomènes

Prolégomènes

Ce mémoire a pour but d'éclairer divers liens entre la notion de résidu quadratique et de nombreux pans de la théorie des nombres (au sens large, cela va de la théorie additive, multiplicative des nombres - l'arithmétique - à la théorie algébrique des nombres en passant par la théorie analytique des nombres et en poussant jusqu'à la théorie des corps de classes). On aura ainsi un aperçu de la profondeur de la notion de résidu, tout en oscillant souvent entre prospective et épistémologie, entre démonstration et digression. On verra aussi quelques applications industrielles (traduire : algorithmiques).

Toutefois, pour des raisons de limitation (du nombre de pages et des connaissances de l'auteur), bien souvent, seuls les résultats sont cités, les démonstrations se trouvant dans les livres cités dans la bibliographie ou dans les articles cités dans ce mémoire. Cependant, un résultat aussi puissant que la loi de réciprocité d'Artin n'est même pas démontré dans l'ardu Corps locaux de J.P. Serre, qui renvoie à un livre de théorie des corps de classes. On trouvera dans nos pages quelques autres rouleaux compresseurs. Néanmoins, divers résultats d'arithmétiques seront démontrés aux chapitres 2 et 3, dont last but not least la loi de réciprocité quadratique, serpent de mer de ce TER. Nous espérons que le lecteur aura autant de plaisir que nous à se promener à travers les notions qui nous ont été offertes par deux siècles d'algèbre, voire d'analyse. Et maintenant, commençons à ouvrir nos horizons en définissant le champ de bataille.

Épisode premier : résidus historiques

Épisode premier : résidus historiques


 
Legendre, Gauss, Jacobi et les autres...

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 x2 +1 sont 2 et des nombres premiers du type 1+4k (voir §). Avec l'aide du symbole de Legendre, ceci se note

\begin{displaymath} \left(\frac{-1}{p}\right)= (-1)^{\frac{p-1}{2}}.\end{displaymath}

Lois de réciprocité d'ordre supérieur

Lois de réciprocité d'ordre supérieur

La loi de réciprocité de Gauss a été généralisée à des congruences du type $x^n \equiv a \ [p]$ (n>2) ; on parle de réciprocité cubique pour n=3, de réciprocité biquadratique ou quartique pour n=4, de réciprocité quintique pour n=5...Ceci impose une transition de l'arithmétique sur ${\mathbb Q}$ vers une arithmétique sur une extension finie ${\mathbb K}$ de ${\mathbb Q}$. Une telle extension de ${\mathbb Q}$ ou d'un corps fini ${\mathbb F}_p(X)$ est nommée un corps global, par opposition aux corps locaux [Serre 2] qui sont les complétés d'un corps de nombres algébriques, pour sa valeur absolue : c'est-à-dire soit ${\mathbb R}$, soit ${\mathbb C}$, soit les corps de nombres p-adiques (théorème d'Ostrowski). Un corps de nombres (algébriques) est une extension finie de ${\mathbb Q}$ contenue dans ${\mathbb C}$.

Dans la généralisation aux résidus énièmes, l'extension doit contenir $\zeta$, une racine énième primitive de l'unité (i.e. $\zeta^n=1$ et $\zeta^k \not = 1 \ \forall k<n$). Nous désignerons, conventionnellement voire traditionnellement, un idéal premier par la lettre ${\mathfrak P}$ (ou $\mathfrak p$), P majuscule (ou minuscule) en alphabet gothique, en honneur à l'école algébrique allemande : en effet Kummer a introduit ses 'nombres idéaux' en 1844 [Dahan], puis Dedekind a développé la théorie des idéaux premiers. Dedekind, dans le Supplément aux `` Vorselungen über Zahlentheorie '' de Dirichlet, 1871, a introduit explicitement les notions de corps, d'anneau, de module et d'idéal.

Les idéaux premiers ${\mathfrak P}$ de ${\mathbb K}$ qui ne divisent pas n vérifient $N_{\mathfrak P}\equiv 1 \ [n]$ où $N_{\mathfrak P}$ est la norme de l'idéal ${\mathfrak P}$, égale au nombre de classes du plus grand ordre du corps modulo ${\mathfrak P}$, dit plus simplement, $N_{\mathfrak P}$ est le cardinal de ${\mathbb A}/{\mathfrak P}$ lorsque ${\mathfrak P}$ est un idéal de l'anneau ${\mathbb A}$ des entiers du corps ${\mathbb K}$. L'analogue du symbole de Legendre est défini par $\left(\frac{a}{{\mathfrak P}}\right)_n \equiv \zeta^k \equiv a^{(N_{\mathfrak P}-1)/n}\ [{\mathfrak P}]$. Tout comme pour le symbole de Jacobi, si $(b)=\prod_i{\mathfrak P}^{m_i}_i$ est la décomposition de l'idéal principal (b) en idéaux premiers, et si a et b sont des entiers algébriques étrangers, alors : $\left(\frac{a}{b}\right)_n =\prod_i \left(\frac{a}{{\mathfrak P}_i}\right)_n^{m_i}$.Si, avec ce symbole de résidu n-ième, on a $\left(\frac{a}{{\mathfrak P}}\right)=1$, alors il existe un entier algébrique $b \in {\mathbb A}$ tel que $b^2\equiv a \ [{\mathfrak P}]$.

La loi de réciprocité pour n=4 dans le corps ${\mathbb Q}(i)={\mathbb Q}(e^{2i\pi/4})$ a été établie par Gauss. Pour n=3 dans le corps ${\mathbb Q}(e^{2i \pi/3})$, elle a été établie par Eisenstein : Beweis des Reziprozitätgesetze für cübischen Reste, J. Math., 1844, utilisant la formule

\begin{displaymath} \sum\sp {m-1}\sb {k=1}\sin \frac{2k\alpha \pi}m\cot \frac{k\pi}m=m-2\alpha\end{displaymath}

(valable pour $1\leq a<m$). Kummer dans Allgemeine Reziprozitätgesezte beliebig hohe Potentzreste, Ber. K. Akad. Wiss., 1850, a établi la loi générale de réciprocité pour le symbole des résidus de degré p dans le corps ${\mathbb Q}(e^{2i \pi/p})$, pour p premier. Dans le chapitre sur les nombres premiers réguliers p (voir §), on donnera une loi de réciprocité dans ${\mathbb Q}(e^{2i \pi/p})$.

Le neuvième problème de Hilbert

Le neuvième problème de Hilbert

En 1900, à Paris, lors du II e Congrès international des Mathématiciens, Hilbert avait dressé une liste de 23 problèmes ouverts qui lui semblaient fondamentaux et dont la résolution était un défi pour le XX e siècle. Le neuvième de ces problèmes consistait à établir une loi de réciprocité dans les corps de nombres algébriques.

On pourra remarquer que plusieurs sujets de T.E.R., outre le nôtre, recoupent des problèmes mis en évidence par Hilbert : le quatrième sur les géométries non euclidiennes, le septième sur la transcendance de certains nombres, le dix-huitième sur les pavages (de l'espace), le vingtième sur le problème de Dirichlet...

A cette époque, une nouvelle étape dans la recherche de lois de réciprocité générales avait été franchie par Hilbert avec ses deux articles : Die Theorie der algebraischen Zahlkörper et Über die Theorie der relativquadratischen Zahlkörpern, Jahresber. Deutsch. Math., 1897 et 1899, dans lesquels il a éclairci leurs aspects locaux. Il avait établi, dans certains cas, une loi de réciprocité pour le symbole de Hilbert :

\begin{displaymath} \prod _{\mathfrak P}\left(\frac{a,b}{{\mathfrak P}}\right)=1.\end{displaymath}

Il avait aussi noté l'analogie entre cette formule et le théorème sur les résidus d'une fonction algébrique : ses points réguliers (dont la norme de Hilbert $\not = 1$) correspondent aux points de branchements sur une surface de Riemann (i.e. une variété analytique complexe de dimension 1).

La première moitié du XX e siècle a vu diverses avancées dans l'étude des lois de réciprocité dues à Furtwängler, Artin, Hasse et Takagi. La loi de réciprocité dans les corps quadratiques dans le cas général est due à [Hecke] et la forme la plus élaborée a été obtenue par une apothéose due à I.R. Shafarevich : A general reciprocity law, Uspekhi Mat. Nauk., 1948.
Elle est, tout comme la loi de réciprocité de Gauss, très liée à l'étude de la décomposition d'un idéal ${\mathfrak P}$ d'un corps de nombres algébriques ${\mathbb K}$ dans une extension algébrique ${\mathbb L}/{\mathbb K}$ à groupe de Galois abélien. En particulier, la théorie des classes, qui donne la solution de ce problème, peut être basée sur la loi de réciprocité de Shafarevich comme l'ont fait Lapin, Cassels et [Neukirch].

Au jour d'aujourd'hui (redondance pléonastique voire superfétatoire ?), il reste quelques grandes conjectures offertes au monde mathématique. Gageons qu'elles figureront sur la liste des problèmes ouverts pour le XXI e siècle.

Nous citerons les suivantes, qui sont plus ou moins en rapport avec notre sujet : - la conjecture de Riemann affirme que la fonction $\zeta$ (une fois prolongée analytiquement à ${\mathbb C}-\{ 1 \} $) ne s'annule que sur la droite Re(z)=1/2 (à l'exception des zéros triviaux $-2{\mathbb N}^*$). La conjecture de Riemann généralisée affirme la ``même chose'' pour les L-séries de Dirichlet. Ces dernières sont définies par

\begin{displaymath} L(s,\chi)=\sum_{n=1}^{\infty}\chi(n)n^{-s}\end{displaymath}

où $\chi$ est un caractère modulo k. La convergence a lieu si Re(s)>0 pour les caractères non principaux. Un caractère est un homomorphisme d'un groupe ${\mathbb G}$ dans le groupe multiplicatif ${\mathbb C}^*$.Il est dit principal s'il est constamment égal à 1 (on aurait pu plus simplement l'appeler caractère trivial). $\chi_k$, le caractère modulo k, est défini par $\chi_k(n)=0$ si $(n,k)\not = 1$ et par $\chi_k(n)=\chi(n \ {\bmod}\ k)$ sinon. On a l'équivalent de l'identité d'Euler :

\begin{displaymath} L(s,\chi)=\prod_{p} (1-\chi(p) p^{-s})^{-1}.\end{displaymath}

Les L-séries interviennent dans la démonstration du théorème de la progression arithmétique (voir §). Il y a un lien important entre la factorisation de polynômes sur des corps finis et la conjecture de Riemann, de plus le rapport entre la factorisation de polynômes et la notion de résidu quadratique (ou d'ordre supérieur) transpire au regard de l'équation $x^n \equiv a \ [p]$.

- la conjecture P $\not =$ NP : tout problème résoluble en temps polynomial non déterministe est-il résoluble en temps polynomial ? C'est-à-dire : si on peut vérifier une solution en temps polynomial, peut-on la trouver en temps polynomial ? Bien sûr, quelque soit la réponse, il restera toujours à trouver des algorithmes de complexité minimale pour une multitude de problèmes...On connaît l'importance de tels progrès, et les retombées qu'ils pourraient avoir, en cryptographie notamment, puisque cette dernière est basée sur l'hypothèse que la factorisation ou que le logarithme modulaire sont NP.

- les mathématiciens, du moins ceux qui ne sont pas trop découragés par la réponse négative de Matijasevich au dixième problème de Hilbert (on s'est même demandé si le problème de Fermat n'était pas indécidable !), n'ont toujours pas résolu moult équations diophantiennes (Waring, Catalan).

- on ignore encore si de nombreuses familles de nombres vérifiant telle propriété sont finies : par exemple les nombres premiers jumeaux (p,p+2), repunits (1...1), de Mersenne (2 n -1), de Fermat (22 n +1), de Cullen ($n2^n\pm1$), de Sophie Germain (p, 2p+1), réguliers (voir §), de Wieferich ($2^{p-1}\equiv 1 \ [p^2]$), de Wilson ($(p-1) ! \equiv -1 \ [p^2]$) [Guy].

- voici, pour finir, un problème important de la théorie des nombres : la conjecture ABC. Soit $\mathcal E$ l'ensemble des triplets (A,B,C) d'entiers vérifiant

\begin{displaymath} \frac{ \ln {\textrm{max}}(\vert A\vert,\vert B\vert,\vert C\vert)}{\ln R} \geq \eta\end{displaymath}

avec A+B=C et pgcd(A,B,C)=1 et où R est le plus grand entier sans carré divisant ABC. La conjecture affirme que $\mathcal E$ est fini. La conjecture ABC généralisée affirme la même chose avec des n-uplets.
Pour les connexions entre la conjecture ABC et différents grands problèmes de la théorie des nombres, on pourra consulter [Granville] et la thèse d'A. Nitaj : Conséquences et aspects de conjectures ABC et de Spiro, université de Caen, 1994.
Par exemple, le lien avec le grand théorème de Fermat se fait en posant : a p =A, b p =B, c p =C et alors, puisque A+B=C, on est ramené à l'étude de la courbe elliptique y2 =x(x-A)(x+B) de discriminant (4ABC)2 (voir §). D'après une idée de G. Frey, K. Ribet a montré en 1988 qu'une courbe elliptique associée à des solutions de a p +b p =c p ne peut être modulaire. Or la conjecture de Taniyama-Weil (1955, 1967) implique que les courbes de Frey sont modulaires. Wiles (en juin 1993, puis comblant le fameux 'trou' avec R. Taylor en septembre 1994) a démontré un cas suffisamment large de cette conjecture pour impliquer la contradiction. Notons par ailleurs que, en 1977, G. Terjanian a utilisé la loi de réciprocité quadratique pour démontrer un cas général du `premier cas du théorème de Fermat' (i.e. l'équation mod n).

Épisode second : un peu de symbolique

Épisode second : un peu de symbolique

`` Un symbole est une concrétisation d'une réalité abstraite. Le sens étymologique du mot grec $\sigma \acute{\upsilon} \mu \beta o\lambda o \nu$, dérivé du verbe $\sigma \upsilon \mu \beta \acute{\alpha} \lambda \lambda \omega$, ``je joins'', définit un objet partagé en deux, la possession de chacune des deux parties par deux individus différents leur permettant de se rejoindre et de se reconnaître. [...] Le champ du symbole peut-il être limité ? Il semble que non. '' Encyclopædia Universalis, article ``symbole''.


 
Le symbole de Legendre

Le symbole de Legendre

On définit $\left(\frac{a}{p}\right)$ pour p premier comme égal à 1 si a est un carré dans ${\mathbb Z}/p{\mathbb Z}$, à -1 sinon. Ce symbole est multiplicatif :

\begin{displaymath} \left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right) \left(\frac{b}{p}\right).\end{displaymath}

Ceci est dû au fait que le produit de deux carrés est un carré, (ceci est toujours vrai dans un groupe cyclique ${\mathbb Z}/n{\mathbb Z}$) et que, si nous sommes dans ${\mathbb Z}/p{\mathbb Z}$, p premier, alors le produit d'un carré par un non carré est un non carré et le produit de deux non carrés est un carré.

On peut aussi énoncer le fait suivant :
g est un générateur du groupe cyclique ${\mathbb G}\Longrightarrow g$ est un non carré. La réciproque est vraie si $ \char93 {\mathbb G}-1=2^k$.

La loi de réciprocité pour le symbole de Legendre affirme

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

Ainsi, de même que dans l'algorithme d'Euclide pour le calcul du PGCD ou que dans le test de primalité par descente-remontée (voir §), on est ramené, de proche en proche, à traiter des nombres de plus en plus petits.

L'intérêt d'une stratégie de ``rapetissement progressif du problème'' transparaît dans l'algorithme de calcul du pgcd de (a,b)= :(r,s), dont voici l'algorithme :


DEBUT
tant que $s \not = 0$ faire $(r,s)~:=(s, r \ {\bmod} \ s)$ ;
(* on crunche et squeeze avec allégresse *)
retourner r ;
FIN

Le symbole de Jacobi

Le symbole de Jacobi

On trouvera dans [Naudin] une approche du symbole de Jacobi par Zolotarev basée sur la signature d'une permutation. Nous utiliserons la définition classique.
On prolonge le symbole de Legendre par $\left(\frac{a}{b}\right)=0$ si a est un multiple de b. Pour $a \in {\mathbb Z}$ et b entier impair, on définit le symbole de Jacobi par $\left(\frac{a}{b}\right)=\prod_i \left(\frac{a}{p_i}\right)$ avec $b=\prod_i p_i$ décomposition de b en facteurs premiers.On peut d'ores et déjà remarquer que $\left(\frac{a}{b}\right)=0$ si et seulement si a et b ne sont pas étrangers.
Ainsi, si a est un carré modulo b (b étant étranger avec a) alors $\left(\frac{a}{b}\right)=1$. On remarquera aussi que $\left(\frac{a}{b}\right)=-1 \Longrightarrow a$est non carré modulo b mais qu'on peut avoir $\left(\frac{a}{b}\right)=1$ sans que a soit un carré modulo b. Exemple : $\forall a \in {\mathbb Z}\ \left(\frac{a}{9}\right)=\left(\frac{a}{3}\right) \left(\frac{a}{3}\right)=1$, or a=5 n'est pas un carré dans ${\mathbb Z}/9{\mathbb Z}$. Il est facile de voir que le symbole de Jacobi est un symbole totalement bimultiplicatif : il est totalement multiplicatif en sa première variable car

\begin{displaymath} \left(\frac{a_1 a_2}{b}\right)=\left(\frac{a_1}{b}\right) \left(\frac{a_2}{b}\right)\end{displaymath}

et il est totalement multiplicatif en sa deuxième variable car

\begin{displaymath} \left(\frac{a}{b_1 b_2}\right)=\left(\frac{a}{b_1}\right) \left(\frac{a}{b_2}\right).\end{displaymath}

Par conséquent, la loi de réciprocité, une fois démontrée pour le symbole de Legendre (ce que nous ferons dans le chapitre suivant), vaut aussi pour le symbole de Jacobi ; on obtient la loi de réciprocité généralisée :

\begin{displaymath} \left(\frac{a}{b}\right)=\left(\frac{b}{a}\right) (-1)^\frac{(a-1)(b-1)}{ 4}.\end{displaymath}

La multiplicativité du symbole de Jacobi en fait un caractère réel, on a vu l'importance de cette notion au §

Application

Application

713 est-il un carré modulo le premier 1009 ? En utilisant la loi de réciprocité quadratique et le calcul de $\left(\frac{2}{p}\right)$ fait au §, on a aisément :

\begin{displaymath} \left(\frac{713}{1009}\right) =\left(\frac{1009}{713}\right)... ...}\right)=\left(\frac{8}{713}\right) \left(\frac{37}{713}\right)\end{displaymath}

\begin{displaymath} =\left(\frac{2}{713}\right) \left(\frac{37}{713}\right) \un... ...t)}=\left(\frac{713-740}{37}\right)=\left(\frac{-27}{37}\right)\end{displaymath}

\begin{displaymath} =\left(\frac{10}{37}\right)=\left(\frac{2}{37}\right) \left(... ... \left(\frac{2}{5}\right)(-1)^\frac{(4)(36)}{4}=(-1)(-1)(+1)=1.\end{displaymath}

Ainsi $\left(\frac{713}{1009}\right)=1$ donc 713 est bien un carré modulo 1009.


Quelques démonstrations de la loi de réciprocité

Quelques démonstrations de la loi de réciprocité

`` Les problèmes posés par les nombres entiers nécessitent de tels travaux et de telles réflexions que, finalement, c'est de là que sortent à peu près la moitié des théories mathématiques [...] Il y a beaucoup de mathématiciens à la suite de Bourbaki qui pensent que c'est la théorie des ensembles qu'il faut mettre au départ ; eh bien ! je ne le pense pas, je pense que c'est la théorie des nombres, des nombres entiers. '' Charles Pisot.


 
Savez-vous compter les résidus...

Savez-vous compter les résidus...

Ce paragraphe et les suivants sont directement recopiés sur [Francinou], ces derniers étant eux-mêmes parfois directement repiqués sur [Hardy]...Mais puisque ni une démonstration ni une mise en page ne peut être copyrightée, n'ayons pas d'état d'âme et saluons ainsi ces deux ouvrages de références, quoiqu'aux ambitions différentes.

Soit $p\geq 3$ un nombre premier (notation conservée dans TOUT ce chapitre). $f~: x \in ({\mathbb Z}/p{\mathbb Z})^* \mapsto x^2$ est un endomorphisme du groupe multiplicatif du corps ${\mathbb F}_p={\mathbb Z}/p{\mathbb Z}$.Son noyau est {-1, +1}, les racines de X2 -1. Le noyau étant de cardinal 2, l'image de f est de cardinal Card(${\mathbb F}_p^*$)/Card($\textrm{Ker}f$)$=\frac{p-1}{2}$. Il y a donc $\frac{p-1}{2}$ carrés dans $({\mathbb Z}/p{\mathbb Z})^*$. 0 étant aussi un carré, ${\mathbb F}_p$ contient $\frac{p+1}{2}$ carrés.


Critère d'Euler

Critère d'Euler

$\forall x \not = 0, (x^{(p-1)/2})^2=x^{p-1} \equiv 1 [n]$donc x (p-1)/2 est dans $\textrm{Ker}f={\pm 1}$.Im(f) est un sous-groupe de F p * de cardinal $\frac{p-1}{2}$.Si x est un carré non nul, on a $x \in$ Im (f) et donc $x^{(p-1)/2}=(y^2)^{(p-1)/2}=y^{p-1}\equiv 1 [p]$.D'autre part, remarquons que l'ensemble des racines du polynômes X (p-1)/2-1 contient les $\frac{p-1}{2}$ carrés non nuls. Or ce polynôme a au plus $\frac{p-1}{2}$ racines. Donc les racines de X (p-1)/2-1 et les carrés non nuls coïncident.

On en déduit le critère d'Euler : x est carré non nul si et seulement si

x (p-1)/2=1.

En résumé, avec le symbole de Legendre : $\left(\frac{x}{p}\right) \equiv x^{(p-1)/2}\ [p]$.

Il est intéressant de citer le critère d'Euler généralisé aux résidus n-ièmes : en posant q=pgcd(n, p-1), $x^n \equiv a \ [p]$ est résoluble si et seulement si $a^\frac{p-1}{q} \equiv 1 \ [p]$ et il y a alors q racines modulo p. On a donc, au total, 1+(p-1)/q résidus n-ièmes et (q-1)(p-1)/q non résidus dans ${\mathbb Z}/p{\mathbb Z}$.

Vinogradov a par ailleurs montré que le nombre R de résidus quadratiques compris entre 1 et $n\leq p-1$ est $R=\frac{1}{2} n+ \theta \sqrt{p} \ln p$ où $\vert\theta \vert \leq 1$ et a formulé l'hypothèse que la distance entre deux non résidus est $O(p^\varepsilon)$, Linnik a d'ailleurs montré que c'était ``presque toujours'' le cas. En outre, le plus petit non résidu quadratique est $\leq p^{1/(2 \sqrt e)} (\ln p)^2$.

Calcul de

Calcul de $\left(\frac{-1}{p}\right)$

En appliquant le critère d'Euler à -1, on obtient : -1 est un carré dans ${\mathbb Z}/p{\mathbb Z}$ si et seulement si (-1)(p-1)/2=1, i.e. si et seulement si (p-1)/2 est pair.

En résumé : -1 est carré modulo $p \Longleftrightarrow p=4n+1$.


 
Application sur les diviseurs de a2+b2

Application sur les diviseurs de a2 +b2

$a^2+b^2\equiv 0\ [p] \Longleftrightarrow$ (avec r=a2 mod p et r'=b2 mod p) $r+r' \equiv 0\ [p] \Longleftrightarrow r' \equiv -r\ [p] \Longleftrightarrow r'q \equiv -1\ [p] $ où q est l'inverse de r, l'ensemble des carrés de ${\mathbb Z}/p{\mathbb Z}$étant un groupe multiplicatif, q et donc qr' sont aussi des carrés. D'où -1= r'q est un carré modulo p or on vient de voir que ceci équivaut à p=4n+1.

Les lecteurs attentifs ne devraient pas être parvenus à cette étape sans avoir au moins froncé les sourcils : en effet les lignes précédentes mal recopiées sur [Itard] souffrent d'une imperfection (euphémisme). Justifierez-vous cette litote en trouvant quelle est l'équivalence aporétique ?

Solution : Il suffit de remplacer ${\mathbb Z}/p{\mathbb Z}$ par $({\mathbb Z}/p{\mathbb Z})^*$ qui lui sera bien un groupe multiplicatif. En effet, si $r \equiv 0 \ [p]$, il ne sera pas inversible. On peut pallier cet inconvénient, si r ou r' n'est pas nul (ce qui revient à ce que tous deux soient non nuls), ainsi l'achoppement fatal saute si p ne divise ni a ni b, a fortiori si a et b sont étrangers, hypothèse apodictique et même salvatrice.

En résumé : les seuls diviseurs d'une somme de deux carrés étrangers sont 2 et des nombres premiers de la forme 4n+1.
Un résultat de Fermat affirme même qu'un nombre premier de la forme 4n+1 est somme de deux carrés ; en 1977, Larson en a donné une démonstration qui utilise le placement de n reines sur un échiquier $n \times n$ sans qu'aucune ne soit en prise.

Lemme de Gauss

Lemme de Gauss

Soit p un premier impair. Pour $n \in {\mathbb N}$, on appelle résidu minimal de n (modulo p) l'unique entier $n' \in ]-p/2,p/2[$tel que $n \equiv n'\ [p]$. Soit $m \in {\mathbb N}$, non multiple de p. On note $\mu$ le nombre d'entiers de $\{m,2m,\dots,\frac{p-1}{2}m\}$ dont le résidu minimal est strictement négatif.

Montrons que $\left(\frac{m}{p}\right)=(-1)^\mu$.

Posons $\lambda = \frac{p-1}{2} - \mu$. Considérons l'ensemble des résidus minimaux de

\begin{displaymath} \{m,2m,\dots,\frac{p-1}{2}m\}.\end{displaymath}

Soient $r_1,\dots, r_\lambda$ les résidus minimaux positifs et $-r_1',\dots, -r_\mu'$ les résidus minimaux strictement négatifs. Comme les éléments de $\{m,2m,\dots,\frac{p-1}{2}m\}$ ne sont pas congrus deux à deux, les r i sont distincts deux à deux. Il en va de même des r i '. Montrons par l'absurde que pour tout $(i,j), r_i \not = r_j'$. Soient donc a et b dans $\{1, 2, \dots, (p-1)/2\}$ tels que $am \equiv r_i = r_j' \equiv -bm\ [p]$. Alors $0\equiv am+bm \equiv (a+b)m\ [p]$. p ne divisant pas m, p divise a+b ce qui est impossible car 0<a+b<p. Ainsi, $\{r_1, r_2, \dots, r_\lambda, r_1', r_2', \dots, r_\mu'\}= \{1, 2, \dots, \frac{p-1}{2}\}$.
On peut donc écrire modulo p :
$m.2m.3m\dots\frac{p-1}{2}.m \equiv (-1)^\mu r_1 r_2 \dots r_\lambda. r_1' r_2' \dots r_\mu' \equiv (-1)^\mu \frac{p-1}{2} !$

Comme p ne divise pas $\frac{p-1}{2} !$, il vient : $m^{\frac{p-1}{2}} \equiv (-1)^\mu\ [p]$ donc, d'après le critère d'Euler :

\begin{displaymath} \left(\frac{m}{p}\right)= (-1)^\mu.\end{displaymath}

Le lemme de Gauss peut être utilisé pour déterminer les nombres premiers pour lesquels un entier préalablement choisi est un carré. C'est ce que nous allons faire avec les entiers 2 et -3 pour obtenir quelques formules, souvent appelées ``complémentaires''.

Calcul de

Calcul de $\left(\frac{2}{p}\right)$

Nous allons montrer que $\left(\frac{2}{p}\right)=(-1)^{E(\frac{p+1}{4})}=(-1)^{\frac{p^2-1}{8}}$ où E(x) désigne la partie entière de x, i.e. le plus petit entier $\leq x$.

Il s'agit de calculer $\mu$ pour m=2, i.e. le nombres de résidus minimaux de $\{2, 4, \dots, p-1\}$ strictement négatifs.
On est donc ramené à compter les entiers k tels que : p/2 < 2k<p.
On vérifie aisément que si $p\equiv 1\ [4], \lambda = \frac{p-1}{4}$ et $ \mu= \frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}$.
Si $p\equiv 3\ [4], \lambda= E(\frac{p-1}{4})=\frac{p-3}{4}$ et $\mu = \frac{p-1}{2}-\frac{p-3}{4}=\frac{p+1}{4}$.
Ainsi, dans tous les cas : $\mu = E(\frac{p+1}{4})$. Notons $r=2 \frac{p-1}{4}\frac{p+1}{4}=\frac{p^2-1}{8}$. Ainsi $r\in {\mathbb N}$ et si $p \equiv 1\ [4]$ (resp. $p \equiv 3\ [4]$), r a la même parité que $\frac{p-1}{4}$ (resp. $\frac{p+1}{4}$). Donc, dans tous les cas, r a même parité que $\mu$ et : $\left(\frac{2}{p}\right) =(-1)^r=(-1)^{\frac{p^2-1}{8}}$.

En résumé : 2 est un carré modulo $p \Longleftrightarrow p=8n \pm 1$.


Calcul de

Calcul de $\left(\frac{-3}{p}\right)$

Il s'agit de calculer $\mu$ pour m=-3, i.e. le nombres de résidus minimaux de $\{-3, -6, \dots, -3 \frac{p-1}{2}\}$strictement négatifs. On est donc ramené à compter les entiers k tels que : p/2 <-3k<p. Ainsi, les valeurs de k pour lesquelles les résidus minimaux sont strictement négatifs sont : $1,2,\dots,E(p/6)$ et $E(p/3)+1, E(p/3)+2, \dots, E(p/2)$ donc $\mu = E(p/6)+E(p/2)-E(p/3)$.D'où si p=6n+1 alors $\mu = n +3n -2n$ est pair et si p=6n+5 alors $\mu = n +(3n+2) -(2n+1)$ est impair.

En résumé : -3 est un carré modulo $p\geq 5 \Longleftrightarrow p=6n+1$.


Calcul de

Calcul de $\left(\frac{5}{p}\right)$

p, car premier > 5, est de la forme 10n+k où k vaut 1,3,7 ou 9. Nous appliquons alors la loi de réciprocité quadratique :

\begin{displaymath} \left(\frac{5}{p}\right)= \left(\frac{p}{5}\right) (-1)^{\fr... ...{2}}= \left(\frac{10n+k}{5}\right)= \left(\frac{k}{5}\right) .\end{displaymath}

Or dans $({\mathbb Z}/5{\mathbb Z})^*$, les seuls carrés sont 1 et 4, d'où $\left(\frac{k}{5}\right)=1$ pour k=1,9 et $\left(\frac{k}{5}\right)=-1$ pour k=3,7.

En résumé : 5 est un carré modulo $p \Longleftrightarrow p=10n \pm 1$.

On montre également : 7 est un carré modulo $p \Longleftrightarrow p \equiv \pm 1, \pm 3, \pm 9 \ [28] $.

Avec ces quelques résultats et la bimultiplicativité du symbole de Jacobi, il vous est désormais possible de calculer très rapidement $\left(\frac{a}{b}\right)$. Par exemple, $\left(\frac{3}{p}\right)$ peut s'obtenir comme combinaison des résultats précédents sur $\left(\frac{-1}{p}\right)$et $\left(\frac{-3}{p}\right)$, on obtient ainsi :
3 est un carré modulo $p \Longleftrightarrow p=12n \pm 1$.


Quod erat demanstrandum

Quod erat demanstrandum

Soient p et q deux nombres premiers impairs, $p \not = q$. On écrit p=2p'+1 et q=2q'+1. Pour tout $k \in \{1,2,\dots,q'\}$, on note (-1)ekrk (où $1\leq r_k \leq q'$ et $e_k \in \{0,1\}$) le résidu de kp modulo q de plus petite valeur absolue.


 
Primo

Primo

Soit $\alpha \in {\mathbb Z}$ avec $kp=q \alpha + (-1)^{e_k}r_k$. Alors $\alpha= kp/q-(-1)^{e_k}r_k/q$.
On a 0<|(-1) e k r k /q|<1/2. Si $e_k=0, \alpha \in ]\frac{kp}{q}-\frac{1}{2},\frac{kp}{q}[$ et nécessairement, $ \alpha = E(kp/q)=E(kp/q)+e_k$.Si $e_k=1, \alpha \in ]\frac{kp}{q},\frac{kp}{q}+\frac{1}{2}[$ et nécessairement, $ \alpha = E(kp/q)+1=E(kp/q)+e_k$.

Ainsi $kp=q(E(\frac{kp}{q})+e_k)+(-1)^{e_k} r_k$.


Secundo

Secundo

Montrons que $\{r_1, \dots, r_q'\} = \{1,\dots,q'\}$.

Il suffit de prouver que si $k \not = l$ alors $r_k \not = r_l$. Soit $(k,l) \in \{1,2,\dots,q'\}^2$.
Si r k =r l , on obtient modulo q : $0\equiv (-1)^{e_k} kp- (-1)^{e_l} lp \equiv p (\pm k \pm l)$.
D'où $\pm k \pm l \equiv 0\ [q]$, et comme $\vert\pm k \pm l \vert \leq 2 q' <q, \pm k \pm l =0$ et nécessairement k=l. CQFD.


Cyril Banderier
7/23/1997