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

Début de la boite de navigation du chapitre

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

fin de la boite de navigation du chapitre

Symbole de Legendre

Définition

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}}$

Début d'un lemme

Lemme

Dans $\mathbb {Z} /p\mathbb {Z}$, le nombre de carrés non nuls est ${\frac {p-1}{2}}$.

Fin du lemme

Démonstration

(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$.

 

Critère d'Euler

$\left({\frac {a}{p}}\right)\equiv a^{\left(p-1\right)/2}{\bmod {p}}$.

Démonstration

(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).

 

Faites ces exercices : Exercice 4-6.

Le critère énoncé et prouvé par Euler est en réalité plus général et sera démontré en exercice.

Remarque

D'après le critère d'Euler, l'application $a\mapsto \left({\frac {a}{p}}\right)$ est complètement multiplicative.

Début d'un lemme

Lemme de Gauss

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}$.

Fin du lemme

Démonstration

(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).

Début d’un théorème

Théorème

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}}$

Fin du théorème

Début de l'exemple

Exemple

Calculer $\left({\frac {365}{1847}}\right)$.

Solution

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$.

 

Fin de l'exemple

Preuve des deux lois complémentaires

• 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}}$.

 

Faites ces exercices : Exercice 4-8.

On verra en exercice une autre preuve de la deuxième loi complémentaire.

Preuve du théorème fondamental

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$.

Lemme 1 : $\tau _{a}=\left({\frac {a}{p}}\right)\tau _{1}$.

Démonstration

$\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]$).

Démonstration

$\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}$.

 

Faites ces exercices : Exercice 4-13.

On verra en exercice une autre preuve du théorème fondamental.