# Introduction à la théorie des nombres/Résidus quadratiques

Soit $p$ un nombre premier impair (c'est-à-dire différent de $2$).

## Symbole de Legendre

Pour tout $a\in \mathbb {Z}$, le symbole de Legendre $\left({\frac {a}{p}}\right)$ est défini par :
    $\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{ si }}a{\text{ est un carré mod }}p{\text{ mais n'est pas divisible par }}p,\\-1&{\text{ si }}a{\text{ n'est pas un carré mod }}p,\\0&{\text{ si }}a{\text{ est divisible par }}p.\end{cases}}$
Dans $\mathbb {Z} /p\mathbb {Z}$, le nombre de carrés non nuls est ${\frac {p-1}{2}}$.
(Apostol, p. 179.) Puisque les éléments de $\mathbb {Z} /p\mathbb {Z}$ sont les classes ${\pmod {p}}$ des $p$ entiers $-{\frac {p-1}{2}},\dots ,-2,-1,0,1,2,\dots ,{\frac {p-1}{2}}$, les carrés non nuls sont les classes de $1^{2},2^{2},\dots ,\left({\frac {p-1}{2}}\right)^{2}$, et toutes ces classes sont distinctes car ${\pmod {p}}$ : $x^{2}\equiv y^{2}\Leftrightarrow \left(x-y\right)\left(x+y\right)\equiv 0\Leftrightarrow y\equiv \pm x$.
$\left({\frac {a}{p}}\right)\equiv a^{\left(p-1\right)/2}{\bmod {p}}$.
(Apostol, p. 180.) Soit $c:=a^{\left(p-1\right)/2}$.
* Si $p\mid a$ alors $p\mid c$.
* Si $a\equiv b^{2}\not \equiv 0\mod p$ alors $c\equiv \left(b^{2}\right)^{\left(p-1\right)/2}=b^{p-1}\equiv 1\mod p$, d'après le petit théorème de Fermat.
* Si $a$ n'est pas un carré ${\bmod {p}}$ alors $c\equiv -1{\bmod {p}}$ car :
** $c\not \equiv 1{\bmod {p}}$ car le polynôme $X^{\left(p-1\right)/2}-1$ ne peut pas avoir d'autres de racines dans $\mathbb {Z} /p\mathbb {Z}$ que les ${\frac {p-1}{2}}$ carrés non nuls précédents (sur un anneau commutatif intègre, un polynôme non nul n'a jamais plus de racines que son degré) ;
** $c\equiv \pm 1{\bmod {p}}$ car $\left(c-1\right)\left(c+1\right)=c^{2}-1=a^{p-1}-1$ est divisible par $p$ (d'après le petit théorème de Fermat).
Le critère énoncé et prouvé par Euler est en réalité plus général et sera démontré en exercice.
D'après le critère d'Euler, l'application $a\mapsto \left({\frac {a}{p}}\right)$ est complètement multiplicative.
Soit $a\in \mathbb {Z}$ non divisible par $p$. On considère les restes, dans la division euclidienne par $p$, des entiers $a,2a,3a,\dots ,{\frac {p-1}{2}}a$.
Parmi ces $\left(p-1\right)/2$ entiers compris entre $1$ et $p-1$, soit $n$ le nombre de ceux qui sont supérieurs à $p/2$. Alors, $\left({\frac {a}{p}}\right)=(-1)^{n}$.
(Apostol, p. 182-183.) On raisonne comme pour le petit théorème de Fermat dans l'exercice 1-3, mais c'est ici le produit
    $Z:=a\cdot 2a\cdot 3a\ldots {\frac {p-1}{2}}a=a^{\left(p-1\right)/2}\left(1\cdot 2\cdot 3\ldots {\frac {p-1}{2}}\right)$
qu'on évalue mod $p$ :
Tout entier $y$ est congru ${\bmod {p}}$ à un unique entier $z$ compris entre $-p/2$ et $p/2$. Notons ${\overline {y}}$ la valeur absolue de cet entier $z$, caractérisée par $0\leq {\overline {y}}<p/2$ et ${\overline {y}}\equiv \pm y{\bmod {p}}$. Ainsi,
    $Z\equiv (-1)^{n}\left({\overline {a}}\cdot {\overline {2a}}\cdot {\overline {3a}}\dots {\overline {{\frac {p-1}{2}}a}}\right){\bmod {p}}$.
Or les $\left(p-1\right)/2$ entiers ${\overline {ra}}$, pour $0<r<p/2$, sont distincts et non nuls. En effet, si ${\overline {ra}}={\overline {sa}}$ pour un $s\in \left[0,p/2\right[$, alors $ra\equiv \pm sa{\bmod {p}}$, d'où (comme $a$ est inversible ${\bmod {p}}$) $r\equiv \pm s{\bmod {p}}$, donc $r=s$ (car $0<r+s<p$ et $-p<r-s<p$), ce qui prouve en même temps que ${\overline {ra}}\neq 0$ (puisque ${\overline {ra}}={\overline {sa}}\Rightarrow s=r\neq 0$). Cette suite est donc une permutation des entiers $1,2,\dots ,\left(p-1\right)/2$, et l'on obtient :
    $a^{\left(p-1\right)/2}\left(1\cdot 2\cdot 3\ldots {\frac {p-1}{2}}\right)\equiv (-1)^{n}\left(1\cdot 2\cdot 3\ldots {\frac {p-1}{2}}\right){\pmod {p}}$.
En simplifiant par $1\cdot 2\cdot 3\dots {\frac {p-1}{2}}$ (inversible ${\bmod {p}}$) et en invoquant le critère d'Euler ci-dessus, on en déduit :
    $\left({\frac {a}{p}}\right)\equiv (-1)^{n}{\bmod {p}}$.
Puisque chacun de ces deux entiers est égal à $\pm 1$, leur différence est égale à $-2$, $0$ ou $2$. Puisque cette différence est de plus divisible par $p$, elle est nulle.

## Loi de réciprocité quadratique

Elle fut d'abord conjecturée par Euler (1772). Legendre crut la démontrer (1785) mais (entre autres lacunes et erreurs) il s'appuyait sur le théorème de la progression arithmétique de Dirichlet (1850). La première preuve complète est due à Gauss (1801).
Soient $p$ et $q$ premiers impairs distincts.
* Théorème fondamental : $\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}={\begin{cases}~~1{\text{ si, }}{\bmod {4}},~p{\text{ ou }}q\equiv 1\\-1{\text{ si, }}{\bmod {4}},~p{\text{ et }}q\equiv -1.\end{cases}}$
* Première loi complémentaire : $\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}\equiv p{\bmod {4}}.$
* Deuxième loi complémentaire : $\left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}~~1{\text{ si }}p\equiv \pm 1{\bmod {8}}\\-1{\text{ si }}p\equiv \pm 3{\bmod {8}}.\end{cases}}$
Calculer $\left({\frac {365}{1847}}\right)$.
D'abord, $1847$ est bien premier mais $365=5\times 73$ ; or $5$ et $73$ sont tous deux congrus à $+1{\bmod {4}}$, donc (théorème fondamental)
    $\left({\frac {365}{1847}}\right)=\left({\frac {5}{1847}}\right)\left({\frac {73}{1847}}\right)=\left({\frac {1847}{5}}\right)\left({\frac {1847}{73}}\right)$.
$1847$ étant congru à $2{\bmod {5}}$ et à $22{\bmod {7}}3$, l'égalité précédente devient :
    $\left({\frac {365}{1847}}\right)=\left({\frac {2}{5}}\right)\left({\frac {22}{73}}\right)=\left({\frac {2}{5}}\right)\left({\frac {2}{73}}\right)\left({\frac {11}{73}}\right)$.
puis (deuxième loi complémentaire), constatant que $5\equiv -3{\bmod {8}}$ et $73\equiv +1{\bmod {8}}$ :
    $\left({\frac {365}{1847}}\right)=-\left({\frac {11}{73}}\right)$.
Utilisant à nouveau que $73\equiv +1{\bmod {4}}$,
    $\left({\frac {365}{1847}}\right)=-\left({\frac {73}{11}}\right)$.
Deux choix sont loisibles pour conclure, selon le représentant de $73{\bmod {11}}$ choisi :
* $73\equiv -4{\bmod {11}}$ et première loi complémentaire :
    $\left({\frac {365}{1847}}\right)=-\left({\frac {-4}{11}}\right)=-\left({\frac {2^{2}}{11}}\right)\left({\frac {-1}{11}}\right)=-\left({\frac {-1}{11}}\right)=1$ ;
* $73\equiv 7{\bmod {11}}$ et théorème fondamental (avec $7\equiv 11\equiv -1{\bmod {4}}$) :
    $\left({\frac {365}{1847}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {2^{2}}{7}}\right)=1$.
* La première loi complémentaire est une conséquence immédiate du critère d'Euler ci-dessus : les deux entiers $\left({\frac {-1}{p}}\right)$ et $(-1)^{\left(p-1\right)/2}$ sont congrus ${\bmod {p}}$. Or — comme à la fin de la preuve ci-dessus du lemme de Gauss — chacun est égal à $-1$ ou $1$ donc leur différence vaut $-2$, $0$ ou $2$, et puisque ni $2$ ni $-2$ n'est divisible par $p$, la seule possibilité est que la différence soit nulle.
* Pour démontrer la seconde loi (Baker, p. 29), appliquons le lemme de Gauss ci-dessus à $a=2$ : $n$ est alors le nombre d'entiers $r$ tels que $p/4<r<p/2$.
** Si $p=4m+1$, ce sont les entiers de $m+1$ à $2m$ ;
** Si $p=4m-1$, ce sont les entiers de $m$ à $2m-1$.
    Donc dans les deux cas, $n=m$. Par conséquent, $2$ est un carré mod $p$ si et seulement si $m$ est pair, c'est-à-dire si celui des deux entiers pairs consécutifs $p-1,p+1$ qui est divisible par $4$ est même divisible par $8$, d'où la condition : $p\equiv \pm 1{\bmod {8}}$.
On verra en exercice une autre preuve de la deuxième loi complémentaire.
Considérons :
* le polynôme cyclotomique $\Phi _{p}\left(X\right)={\frac {X^{p}-1}{X-1}}=X^{p-1}+X^{p-2}+\dots +X^{2}+X+1$ à coefficients dans le corps ${\rm {F}}_{q}:=\mathbb {Z} /q\mathbb {Z}$ ;
* l'anneau quotient ${\rm {F}}_{q}\left[\zeta \right]:={\rm {F}}_{q}\left[X\right]/\left(\Phi _{p}\left(X\right)\right)$ (non nécessairement intègre), dans lequel $p$ et $2$ sont inversibles — ils le sont même dans le sous-anneau ${\rm {F}}_{q}$ — et $\sum _{k\in \mathbb {Z} /p\mathbb {Z} }\zeta ^{k}=0$ ;
* dans cet anneau, les sommes quadratiques de Gauss $\tau _{a}:=\sum _{j\in \mathbb {Z} /p\mathbb {Z} }\zeta ^{aj^{2}}$, pour $a$ entier non divisible par $p$.
* ↑ En fait (mais cela ne sera pas utilisé dans cette preuve), l'anneau fini ${\rm {F}}_{q}\left[X\right]/\left(\Phi _{p}\left(X\right)\right)$ est intègre — donc est un corps — si et seulement si q (mod p) fait partie des φ(p – 1) générateurs du groupe cyclique $(\mathbb {Z} /p\mathbb {Z} )^{*}$.
* ↑ Seules nous intéresseront les valeurs $a=1$, $a=-1$ et $a=q$.
Lemme 1 : $\tau _{a}=\left({\frac {a}{p}}\right)\tau _{1}$.
$\tau _{a}=\sum _{k\in \mathbb {Z} /p\mathbb {Z} }\left(1+\left({\frac {k}{p}}\right)\right)\zeta ^{ak}=\sum _{k\in \mathbb {Z} /p\mathbb {Z} }\left({\frac {k}{p}}\right)\zeta ^{ak}=\left({\frac {a}{p}}\right)\sum _{m\in \mathbb {Z} /p\mathbb {Z} }\left({\frac {m}{p}}\right)\zeta ^{m}$.
Lemme 2 : $\tau _{-1}\tau _{1}=p$ (en particulier, $\tau _{1}$ est inversible dans ${\rm {F}}_{q}\left[\zeta \right]$).
    $\tau _{-1}\tau _{1}=\sum _{j,k\in \mathbb {Z} /p\mathbb {Z} }\zeta ^{\left(j+k\right)\left(j-k\right)}=\sum _{u,v\in \mathbb {Z} /p\mathbb {Z} }\zeta ^{uv}=p\zeta ^{0}+\sum _{u\in \left(\mathbb {Z} /p\mathbb {Z} \right)^{*},\,v\in \mathbb {Z} /p\mathbb {Z} }\zeta ^{uv}=p+\left(p-1\right)\sum _{k\in \mathbb {Z} /p\mathbb {Z} }\zeta ^{k}=p$.
En appliquant le lemme 1 à $a=-1$ et la première loi complémentaire, le lemme 2 se réécrit :
    $\tau _{1}^{2}=(-1)^{\left(p-1\right)/2}p$.
D'autre part, en utilisant le fait que $z\mapsto z^{q}$ est un endomorphisme de l'anneau ${\rm {F}}_{q}\left[\zeta \right]$, on a $\tau _{1}^{q}=\tau _{q}$ donc en appliquant le lemme 1 à $a=q$ :
    $\left({\frac {q}{p}}\right)=\tau _{q}\tau _{1}^{-1}=\tau _{1}^{q-1}$.
Par conséquent :
    $\left({\frac {q}{p}}\right)=\left(\tau _{1}^{2}\right)^{\frac {q-1}{2}}=\left((-1)^{\left(p-1\right)/2}p\right)^{\frac {q-1}{2}}$
d'où, en utilisant le critère d'Euler :
    $\left({\frac {q}{p}}\right)=(-1)^{\frac {\left(p-1\right)\left(q-1\right)}{4}}\left({\frac {p}{q}}\right)$.
Cette égalité est vraie a priori seulement dans ${\rm {F}}_{q}\left[\zeta \right]$ mais — par le même raisonnement que dans les preuves ci-dessus du lemme de Gauss et de la seconde loi complémentaire — comme chacun des deux membres, en tant qu'entier, est égal à $\pm 1$, l'égalité est vraie dans $\mathbb {Z}$.
On verra en exercice une autre preuve du théorème fondamental.
| Séries et produits infinis formels | Formes quadratiques entières |