summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david@procyon.(none)>2011-03-02 14:12:55 (GMT)
committerDavid A. Madore <david@procyon.(none)>2011-03-02 14:12:55 (GMT)
commit91a9447b4341fc25b8e4510ff9b4e7791c6c8960 (patch)
tree7e48333c6ea194f47fd3a921b4f1d3fee6ac3bd4
parent9a557a91220825442cfc9160bf65ac4a9da4c862 (diff)
downloadgalois-91a9447b4341fc25b8e4510ff9b4e7791c6c8960.zip
galois-91a9447b4341fc25b8e4510ff9b4e7791c6c8960.tar.gz
galois-91a9447b4341fc25b8e4510ff9b4e7791c6c8960.tar.bz2
[Fin,ACF] Déplacement de l'étude du caractère quadratique vers le chapitre « corps finis ».
La définition du caractère quadratique, ses propriétés de base, et la démonstration de la loi de réciprocité quadratique et de la formule complémentaire sont déplacés là (depuis le chapitre sur l'algorithmique des corps finis) parce qu'elles sont plus centrales que les questions d'algorithmique, que ça prépare à ce qui suit (étude des sommes de Gauß et de Jacobi), et que c'est globalement plus cohérent.
-rw-r--r--chapitres/algo-corps-finis.tex637
-rw-r--r--chapitres/corps-finis.tex604
2 files changed, 633 insertions, 608 deletions
diff --git a/chapitres/algo-corps-finis.tex b/chapitres/algo-corps-finis.tex
index f3b988b..96005c8 100644
--- a/chapitres/algo-corps-finis.tex
+++ b/chapitres/algo-corps-finis.tex
@@ -32,139 +32,21 @@
\section{Calculs de racines carrées, équations quadratiques}\label{equations-quadratiques-corps-finis}
-\subsection{Le caractère quadratique}
-
-\begin{definition2}\label{definition-caractere-quadratique}
-Soit $q$ une puissance d'un nombre premier impair. On
-appelle \emph{caractère quadratique} sur $\FF_q$ la fonction
-$a \mapsto a^{(q-1)/2}$. On note $\FF_q^{\times2}$ l'ensemble des
-éléments de $\FF_q^\times$ qui sont des carrés.
-\end{definition2}
-
-\begin{proposition2}\label{denombrement-carres-f-q}
-Si $q$ est une puissance d'un nombre premier impair, alors le caractère
-quadratique ne prend sur $\FF_q^\times$ que les valeurs $+1$ et $-1$,
-et on a $a \in \FF_q^{\times2}$ si et seulement si $a^{(q-1)/2} =
-+1$ ; de plus, $\# \FF_q^{\times2} = \frac{1}{2}(q-1)$.
-\end{proposition2}
-\begin{proof}
-L'application $z \mapsto z^2$, vue comme un morphisme
-$\FF_q^\times \to \FF_q^\times$, a pour noyau $\{\pm 1\}$ (de
-cardinal $2$), et pour image $\FF_q^{\times2}$, donc
-$2\, \#\FF_q^{\times2} = \#\FF_q^{\times}$ : ceci montre la dernière
-affirmation.
-
-Si $e = a^{(q-1)/2}$ avec $a \in \FF_q^\times$, alors $e^2 = a^{q-1} =
-1$, donc $e$ vaut $+1$ ou $-1$.
-
-Si $a = b^2$ avec $b \in \FF_q^\times$, alors $a^{(q-1)/2} = b^{q-1} =
-+1$. On a donc montré que sur tout élément de $\FF_q^{\times2}$ le
-caractère quadratique vaut $+1$ : comme on vient de voir qu'il y a
-$\frac{1}{2}(q-1)$ tels éléments et que le polynôme $X^{(q-1)/2} - 1$
-(de degré $\frac{1}{2}(q-1)$) n'est pas nul, il ne peut s'annuler en
-aucun autre point de $\FF_q$ : on voit donc que réciproquement si
-$a^{(q-1)/2} = +1$ alors $a \in \FF_q^{\times2}$.
-\end{proof}
-
-On pouvait également démontrer ce résultat en utilisant un élément
-primitif $g$ (cf. \refext{Fin}{cyclicite-groupe-multiplicatif-corps}) : les
-éléments de $\FF_q^{\times2}$ sont ceux qui s'écrivent $g^{2i}$ avec
-$i$ entier (et bien défini modulo $\frac{1}{2}(q-1)$).
-
-\begin{corollaire2}\label{produits-de-non-carres-dans-f-q}
-Un produit $ab$ dans $\FF_q$ est un carré \emph{si et seulement si}
-les deux facteurs $a,b$ sont soit tous deux des carrés soit tous deux
-des non-carrés.
-\end{corollaire2}
-\begin{proof}
-Cela découle de \ref{denombrement-carres-f-q} et du fait que le
-caractère quadratique est un morphisme multiplicatif : $(ab)^{(q-1)/2}
-= a^{(q-1)/2}\, b^{(q-1)/2}$.
-\end{proof}
-
-\subsubsection{} Le calcul du caractère quadratique peut se faire
-efficacement par un algorithme d'exponentiation rapide : ceci permet
-donc de savoir effectivement si un élément donné de $\FF_q^\times$
-admet une racine carrée. (On renvoie à \refext{Fin}{remarques-critere-rabin}
-pour la question de la représentation des corps finis et
-l'algorithmique dans ceux-ci ; mais pour beaucoup de questions
-algorithmiques considérées ici, le cas où $q = p$ est premier et
-$\FF_q = \ZZ/p\ZZ$ est déjà intéressant.) Calculer effectivement la
-racine carrée d'un élément qui en admet une est une question plus
-délicate. Commençons par considérer le cas facile où $q \equiv
-3 \pmod{4}$ :
-
-\begin{lemme2}\label{carres-extensions-corps-finis}
-Soit $q = p^r$ avec $p$ premier impair. Si $r$ est impair, alors un
-élément de $\FF_p$ est un carré dans $\FF_p$ si et seulement si il
-l'est dans $\FF_q$ (autrement dit, $\FF_q^{\times 2} \cap \FF_p
-= \FF_p^{\times 2}$). Si $r$ est pair, alors tout élément de $\FF_p$
-est un carré dans $\FF_q$.
-\end{lemme2}
-\begin{proof}
-On peut par exemple, pour $a \in \FF_p^\times$, écrire $a^{(q-1)/2} =
-a^{(p^r-1)/2} = (a^{(p-1)/2})^{p^{r-1} + \cdots + p + 1}$, et
-$a^{(p-1)/2}$ vaut $+1$ ou $-1$ selon que $a$ est un carré
-dans $\FF_p$, et la parité de $p^{r-1} + \cdots + p + 1$ est la même
-que celle de $r$, ce qui démontre le résultat.
-
-Une autre démonstration consiste à considérer le polynôme $X^2 - a$ et
-à lui
-appliquer \refext{Fin}{corollaire-scindage-partiel-polynomes-corps-finis}.
-\end{proof}
-
-Mentionnons par ailleurs le résultat combinatoire suivant, qui est une
-application inattendue des propriétés du caractère quadratique sur les
-corps finis :
-\begin{proposition2}\label{matrice-d-hadamard-par-corps-finis}
-Soit $q$ une puissance d'un nombre premier vérifiant $q \equiv
-3 \pmod{4}$. Alors il existe une matrice $M$ de taille $(q+1)\times
-(q+1)$ à coefficients dans $\{\pm 1\}$ telle que deux lignes
-distinctes quelconques de $M$ ont la même valeur en $\frac{1}{2}(q+1)$
-de leurs entrées et une valeur opposée en les $\frac{1}{2}(q+1)$
-autres.
-\end{proposition2}
-\begin{proof}
-En notant $\PP^1(\FF_q) = \FF_q \cup \{\infty\}$, on définit une
-fonction $\varphi\colon \PP^1(\FF_q) \times \PP^1(\FF_q) \to \{\pm
-1\}$ par $\varphi(\infty,\infty) = \varphi(x,\infty)
-= \varphi(\infty,y) = +1$ si $x \in \FF_q$ et $y \in \FF_q$, par
-$\varphi(x,x) = -1$ pour tout $x \in \FF_q$, et par $\varphi(x,y) =
-(x-y)^{(q-1)/2}$ (c'est-à-dire $+1$ ou $-1$ selon que $x-y$ est un
-carré ou non dans $\FF_q$, cf. \ref{denombrement-carres-f-q}) si
-$x\neq y$ avec $x,y\in \FF_q$. La matrice indicée par
-$\PP^1(\FF_q) \times \PP^1(\FF_q)$ dont les coefficients sont donnés
-par la fonction $\varphi$ répond à la question : pour le montrer, il
-s'agit de voir que si $x,x' \in \PP^1(\FF_q)$ avec $x\neq x'$ alors il
-existe $\frac{1}{2}(q+1)$ valeurs $y \in \PP^1(\FF_q)$ exactement
-telles que $\varphi(x,y) = \varphi(x',y)$.
-
-Si $x$ vaut $\infty$, il s'agit de voir que $\frac{1}{2}(q+1)$ valeurs
-$y$ vérifient $\varphi(x',y) = -1$, c'est-à-dire (puisque
-$\varphi(x',x')=-1$) que $\frac{1}{2}(q-1)$ éléments $y \in \FF_q$
-sont tels que $x'-y$ ne soit pas un carré dans $\FF_q$, ce qui est
-bien le cas (cf. \ref{denombrement-carres-f-q}). Si $x,x' \in \FF_q$,
-on s'intéresse à $\varphi(x,y)/\varphi(x',y)$. Si $y \in \FF_q$ et
-$y \not\in \{x,x'\}$, cette fonction vaut
-$(\frac{x-y}{x'-y})^{(q-1)/2}$, or l'expression $\frac{x-y}{x'-y}$
-prend toutes les valeurs de $\FF_q$ sauf $0$ et $1$, donc
-$(\frac{x-y}{x'-y})^{(q-1)/2}$ prend $\frac{1}{2}(q-3)$ fois la
-valeur $+1$ ; si $y = \infty$, l'expression
-$\varphi(x,y)/\varphi(x',y)$ vaut $+1$ ; si $y=x$ ou $y=x'$, enfin,
-l'expression $\varphi(x,y)/\varphi(x',y)$ vaut $-(x'-x)^{(q-1)/2}$ et
-$-(x-x')^{(q-1)/2}$ respectivement, et ces valeurs sont opposées
-puisque $q\equiv 3 \pmod{4}$ entraîne $(-1)^{(q-1)/2} = -1$ ; on a
-donc montré que $\varphi(x,y)/\varphi(x',y)$ prend exactement
-$\frac{1}{2}(q+1)$ fois la valeur $+1$ lorsque $y$
-parcourt $\PP^1(\FF_q)$.
-\end{proof}
-
-Une matrice telle que fournie par la
-proposition \ref{matrice-d-hadamard-par-corps-finis}
-s'appelle \emph{matrice d'Hadamard} de taille $q+1$. On conjecture
-qu'il existe une matrice d'Hadamard de toute taille multiple de $4$.
-
-\subsection{Algorithmes de calcul des racines carrées}
+\subsection{Calculs de racines carrées en caractéristique impaire}
+
+On rappelle qu'en \refext{Fin}{definition-caractere-quadratique} on a
+introduit la définition suivante : si $q$ est une puissance d'un
+nombre premier impair, on appelle \emph{caractère quadratique} sur
+$\FF_q$ la fonction $a \mapsto a^{(q-1)/2}$, et on note
+$\FF_q^{\times2}$ l'ensemble des éléments de $\FF_q^\times$ qui sont
+des carrés. On rappelle (\refext{Fin}{denombrement-carres-f-q}) que
+$a \in \FF_q^{\times2}$ si et seulement si $a^{(q-1)/2} = +1$ (tandis
+que si $a \in \FF_q^\times$ n'est pas un carré alors $a^{(q-1)/2} =
+-1$), et que de plus $\#\FF_q^{\times2} = \frac{q-1}{2}$.
+
+\XXX --- Revoir les propositions suivantes maintenant que les faits de
+base sur le caractère quadratique et la réciprocité quadratique ont
+été avancés dans le chapitre sur les corps finis.
\begin{proposition2}\label{tonelli-shanks-pour-3-mod-4}
Soit $q$ une puissance d'un nombre premier impair. On suppose
@@ -178,7 +60,8 @@ la même expression produit une racine carrée de $-D$.
\end{proposition2}
\begin{proof}
Pour ce qui est de la première affirmation, on a $(-1)^{(q-1)/2} = -1$
-car $\frac{1}{2}(q-1)$ est impair (puisque $q-1 \equiv 2 \pmod{4}$).
+car $\frac{1}{2}(q-1)$ est impair (puisque $q-1 \equiv 2 \pmod{4}$),
+cf. \refext{Fin}{caractere-quadratique-de-moins-un}.
Pour ce qui est de la seconde, soit $z = D^{(q+1)/4}$ : on a alors
$z^2 = D^{(q+1)/2} = D^q D^{-(q-1)/2} = \pm D$ où le signe est $+$ si
@@ -196,28 +79,8 @@ $D^{(q-1)/4}$ vaut $+1$ ou $-1$.
\end{itemize}
\end{proposition2}
\begin{proof}
-Montrons d'abord que $2$ n'est pas un carré dans $\FF_q$. Pour cela,
-écrivons $q = p^r$ avec $p$ premier : comme $q \equiv 5 \pmod{8}$ et
-que tous les carrés sont congrus à $1$ modulo $8$, on voit que $r$ est
-impair et $p \equiv 5 \pmod{8}$. D'après le
-lemme \ref{carres-extensions-corps-finis}, il s'agit de montrer que
-$2$ n'est pas un carré dans $\FF_p = \ZZ/p\ZZ$. Pour cela,
-considérons d'une part les $\frac{1}{2}(p-1)$ entiers
-$1,2,3,\ldots,\frac{p-1}{2}$, dont le produit est $(\frac{p-1}{2})!$,
-et considérons d'autre part leurs doubles, qui sont congrus modulo $p$
-à $2,4,6,\ldots,\frac{p-1}{2},\penalty-100
--\frac{p-3}{2},-\frac{p-5}{2},\ldots,-1$ (on a choisi systématiquement
-le représentant de plus petite valeur absolue) ; or $\frac{p-1}{4}$
-(un nombre impair) parmi ces représentants sont négatifs et leurs
-valeurs absolues comptent bien chacun des entiers entre $1$ et
-$\frac{p-1}{2}$ : donc le produit des entiers
-$2,4,6,\ldots,\frac{p-1}{2},\penalty-100
--\frac{p-3}{2},-\frac{p-5}{2},\ldots,-1$ est $-(\frac{p-1}{2})!$ ;
-mais ce produit est congru modulo $p$ à $2^{(p-1)/2}\,
-(\frac{p-1}{2})!$ puisqu'il s'agit des représentants des doubles des
-entiers $1,2,3,\ldots,\frac{p-1}{2}$. On a donc prouvé que
-$2^{(p-1)/2} \equiv -1 \pmod{p}$, donc que $2$ n'est pas un carré
-modulo $p$, ni dans $\FF_q$.
+La première affirmation a déjà été démontrée
+en \refext{Fin}{formule-complementaire}.
Passons à la seconde affirmation. Soit $x = D^{(q+3)/8}$ : on a alors
$x^2 = D^{(q+3)/4} = D \cdot D^{(q-1)/4}$. Notons que $D^{(q-1)/4}$
@@ -228,12 +91,6 @@ comme annoncé. Si $D^{(q-1)/4} = -1$, on a $x^2 = -D$ : soit $x' =
puisqu'on a démontré que $2^{(q-1)/2} = -1$.
\end{proof}
-L'affirmation que $2$ n'est pas un carré dans $\FF_q$ lorsque
-$q \equiv 5 \pmod{8}$ sera généralisée ultérieurement (on verra
-en \ref{formule-complementaire} que
-$2^{(q-1)/2} = (-1)^{(q^2-1)/8}$ dans $\FF_q$, ce qui peut se montrer
-avec la même technique qu'on a utilisée ci-dessus).
-
Les techniques de calcul de racines carrées explicitées dans les
propositions \ref{tonelli-shanks-pour-3-mod-4} et \ref{tonelli-shanks-pour-5-mod-8}
sont des cas particuliers d'un algorithme plus général appelé
@@ -365,7 +222,7 @@ se place à présent dans ce dernier cas.
Pour tout élément non nul $z$ de $\FF_q$ on a $z^{(q-1)/2} = \pm 1$,
ce nombre valant $+1$ pour $\frac{1}{2}(q-1)$ éléments $z$, et $-1$
pour les $\frac{1}{2}(q-1)$ autres
-(cf. \ref{denombrement-carres-f-q}). On en déduit que si $t =
+(cf. \refext{Fin}{denombrement-carres-f-q}). On en déduit que si $t =
y^{(q-1)/2}$ s'écrit $t = c_0 + c_1 x$, alors chacun des éléments $c_0
+ c_1 d = (a_0 + a_1 d)^{(q-1)/2}$ et $c_0 - c_1 d = (a_0 - a_1
d)^{(q-1)/2}$ vaut $+1$ ou $-1$. Et chacune des quatre combinaisons
@@ -440,58 +297,16 @@ cas particulier de l'algorithme de Cipolla que de celui de Legendre.
\subsection{La caractéristique $2$}\label{equations-quadratiques-corps-finis-caracteristique-2}
-\subsubsection{} En caractéristique $2$, calculer
-des racines carrées dans $\FF_q = \FF_{2^r}$ est facile : on a
-$x^{2^r} = x$ d'après \refext{Fin}{petit-theoreme-fermat}, donc $x^{2^{r-1}}$
-est une racine carrée de $x$. À la différence du cas où $2$ est
-inversible, cependant, savoir calculer des racines carrées ne permet
-pas de résoudre toutes les équations quadratiques puisqu'on ne peut
-pas écrire $X^2 + bX + c = 0$ sous la forme $(X+\frac{b}{2})^2 +
-(c-\frac{b^2}{4}) = 0$. À la place, si on note $\wp(Z) = Z^2 + Z$,
-l'équation $X^2 + bX + c = 0$, lorsque $b\neq 0$ (le cas $b=0$ ayant
-déjà été traité) peut se réécrire $\wp(X/b)+(c/b^2) = 0$, soit $X =
-b\,\root\wp\of{c/b^2}$ si on note $\root\wp\of E$ une solution (si
-elle existe) de l'équation $Z^2+Z = E$, l'autre solution étant alors
-$\root\wp\of E + 1$ (puisque $\wp(Z+1) = \wp(Z)$).
-
-\begin{definition2}
-Soit $q = 2^r$ une puissance de $2$. On appelle \emph{caractère
-quadratique additif} sur $\FF_q$ la fonction $\tau \colon a \mapsto a
-+ a^2 + a^4 + a^8 + \cdots + a^{2^{r-1}}$ (qu'on notera aussi $\tau_r$
-en cas d'ambiguïté). On note $\wp\FF_q$ l'ensemble des éléments de
-$\FF_q$ qui sont dans l'image de la fonction $\wp\colon z \mapsto z^2
-+ z$.
-\end{definition2}
-
-On peut aussi considérer $\tau$ comme la trace pour l'extension
-$\FF_q\bo\FF_2$ (cf. \refext{Fin}{trace-et-norme-corps-finis}).
-
-\begin{proposition2}\label{denombrement-artin-schreier-2-f-q}
-Si $q$ est une puissance de $2$, alors le caractère quadratique
-additif $\tau$ ne prend sur $\FF_q$ que les valeurs $0$ et $1$, et on
-a $a \in \wp\FF_q$ si et seulement si $\tau(a) = 0$ ; de plus,
+On rappelle qu'en
+\refext{Fin}{definition-caractere-quadratique-en-caracteristique-2} on
+a introduit la notation suivante : si $q = 2^r$ est une puissance
+de $2$, on appelle \emph{caractère quadratique additif} sur $\FF_q$ la
+fonction $\tau \colon a \mapsto a + a^2 + a^4 + a^8 + \cdots +
+a^{2^{r-1}}$, et on note $\wp\FF_q$ l'ensemble des éléments de $\FF_q$
+qui sont dans l'image de la fonction $\wp\colon z \mapsto z^2 + z$.
+On rappelle (\refext{Fin}{denombrement-artin-schreier-2-f-q}) que $a
+\in \wp\FF_q$ si et seulement si $\tau(a) = 0$, et que de plus
$\#(\wp\FF_q) = \frac{q}{2}$.
-\end{proposition2}
-\begin{proof}
-L'application $\wp\colon z \mapsto z^2+z$, vue comme une application
-$\FF_2$-linéaire $\FF_q \to \FF_q$, a pour noyau $\{0,1\}$ (de
-cardinal $2$) puisque $0,1$ sont les deux solutions de $Z^2 + Z = 0$ ;
-et elle a pour image $\wp\FF_q$, donc $2\, \#(\wp\FF_q) = \#\FF_q$ :
-ceci montre la dernière affirmation.
-
-Si $e = \tau(a)$ avec $a \in \FF_q$, alors $\wp(e) = e^2 + e = (a^2 +
-a^4 + \cdots + a^q) + (a + a^2 + \cdots + a^{q/2}) = 0$ puisque $a^{q}
-= a$, donc $e$ vaut $0$ ou $1$.
-
-Si $a = \wp(b)$ avec $b \in \FF_q$, alors $\tau(a) = a + a^2 + \cdots
-+ a^{q/2} = (b^2 + b) + (b^4 + b^2) + \cdots + (b^{q} + b^{q/2}) = 0$.
-On a donc montré que sur tout élément de $\wp\FF_q$ le caractère
-quadratique additif $\tau$ vaut $0$ : comme on vient de voir qu'il y a
-$\frac{q}{2}$ tels éléments et que le polynôme $X + X^2 + X^4 + \cdots
-+ X^{q/2}$ (de degré $\frac{q}{2}$) n'est pas nul, il ne peut
-s'annuler en aucun autre point de $\FF_q$ : on voit donc que
-réciproquement si $\tau(a) = 0$ alors $a \in \wp\FF_q$.
-\end{proof}
La proposition suivante est l'analogue
de \ref{proposition-algorithme-cipolla} pour la caractéristique $2$ :
@@ -504,7 +319,7 @@ de $Z^2+Z+E=0$ dans $\FF_q$.
\end{proposition2}
\begin{proof}
L'hypothèse $\tau(v/E^2) = 1$, c'est-à-dire que $v/E^2$ n'est pas
-dans $\wp\FF_q$ (cf. \ref{denombrement-artin-schreier-2-f-q}),
+dans $\wp\FF_q$ (cf. \refext{Fin}{denombrement-artin-schreier-2-f-q}),
implique que le polynôme $X^2 + EX + v$ n'est pas scindé sur $\FF_q$,
donc est irréductible, donc $\FF' = \FF_q[X]/(X^2+EX+v)$ est un corps,
isomorphe à $\FF_{q^2}$. L'élément $x$ représenté par $X$
@@ -548,7 +363,7 @@ l'isomorphisme $a_0 + a_1 x \mapsto (a_0+a_1 e, {(a_0+a_1)}+a_1 e)$).
Pour tout élément non nul $z$ de $\FF_q$ on a $z + z^2 + z^4 + \cdots
+ z^{q/2} \in \{0, 1\}$, ce nombre valant $0$ pour $\frac{q}{2}$
éléments $z$, et $1$ pour les $\frac{q}{2}$ autres
-(cf. \ref{denombrement-artin-schreier-2-f-q}). On en déduit que si $t
+(cf. \refext{Fin}{denombrement-artin-schreier-2-f-q}). On en déduit que si $t
= y + y^2 + y^4 + \cdots + y^{q/2}$ s'écrit $t = c_0 + c_1 x$, alors
chacun des éléments $c_0 + c_1 e = \tau(a_0 + a_1 e)$ et $(c_0+c_1) +
c_1 e = \tau((a_0+a_1) + a_1 e)$ vaut $0$ ou $1$. Et chacune des
@@ -607,396 +422,6 @@ l'application en question (si $q = 2^r$), puis à sommer les éléments
en question. On procède alors comme on vient d'expliquer.
-\section{Réciprocité quadratique}
-\label{reciprocite-quadratique}
-
-\subsection{Le symbole de Legendre}
-
-\begin{definition2}\label{definition-symbole-legendre}
-Si $p$ est un nombre premier impair et $a$ un entier, on
-appelle \emph{symbole de Legendre} de $a$ modulo $p$, et on note
-$\Legendre{a}{p}$, l'entier valant $0$ si $p|a$, et $1$ si $a$ est un
-carré dans $\FF_p$, et $-1$ si $a$ n'est pas un carré dans $\FF_p$.
-\end{definition2}
-
-Il résulte trivialement de \ref{denombrement-carres-f-q} et
-de \ref{produits-de-non-carres-dans-f-q} que :
-\begin{proposition2}\label{formule-symbole-legendre}
-Si $p$ est un nombre premier impair et $a$ un entier, alors
-\[
-\Legendre{a}{p} \equiv a^{(p-1)/2} \pmod{p}
-\]
-De plus, quels que soient les entiers $a,b$, on a $\Legendre{ab}{p}
-= \Legendre{a}{p} \Legendre{b}{p}$.
-\end{proposition2}
-
-\subsection{Réciprocité quadratique et formule complémentaire}
-
-L'énoncé suivant, qui compare le caractère quadratique de $p$ modulo
-$q$ au caractère quadratique de $q$ modulo $p$, et dont on va donner
-deux démonstrations, porte le nom de \emph{loi de réciprocité
-quadratique} :
-
-\begin{theoreme2}\label{loi-reciprocite-quadratique}
-Soient $p,q$ deux nombres premiers impairs distincts. On a alors :
-\[
-\Legendre{p}{q} \Legendre{q}{p} = (-1)^{(p-1)(q-1)/4}
-\]
---- c'est-à-dire $\Legendre{q}{p} = \Legendre{p}{q}$ sauf si
-$p,q \equiv 3 \pmod{4}$ auquel cas $\Legendre{q}{p} =
--\Legendre{p}{q}$.
-\end{theoreme2}
-\begin{proof}[Première démonstration]
-Convenons pour cette démonstration de représenter les éléments de
-$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
-dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
-lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
-$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
-l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$. Avec
-cette définition, si $k \in \ZZ$ n'est pas multiple de $p$, son
-« signe » modulo $p$ (c'est-à-dire $+1$ ou $-1$ selon qu'il a un
-résidu positif ou négatif) vaut $(-1)^{\lfloor 2k/p\rfloor}$ où
-$\lfloor\tiret\rfloor$ désigne la fonction partie entière. Remarquons
-d'ores et déjà que pour tout entier $i$ non multiple de $p$ on a
-$\lfloor \frac{2qi}{p}\rfloor + \lfloor \frac{q(p-2i)}{p}\rfloor =
-q-1$ (car $\lfloor\theta\rfloor +
-\lfloor q-\theta\rfloor = q-1$ pour tout
-$\theta \in \RR \setminus \ZZ$), et que cet entier est pair, de sorte
-que $(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$
-(ces deux expressions donnent donc le signe de $qi$ modulo $p$).
-
-Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
-$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$. Considérons
-maintenant le produit $\prod_{i=1}^{(p-1)/2} q\bar\imath$ : on peut
-manifestement l'écrire comme $q^{(p-1)/2} (\frac{p-1}{2})!$
-modulo $p$. Mais par ailleurs on ne peut pas avoir $q\bar\imath =
-\pm q\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
-donc les $q\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
-parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ donné par
-$(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$ comme
-on l'a expliqué ; ainsi, $\prod_{i=1}^{(p-1)/2} q\bar\imath =
-(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}(\frac{p-1}{2})!$, et
-en comparant les deux expressions trouvées et en
-utilisant \ref{formule-symbole-legendre}, on a $\Legendre{q}{p} =
-(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}$ (« lemme
-d'Eisenstein »), ou, mieux, $\Legendre{q}{p} =
-(-1)^{\sum_{m=1}^{(p-1)/2} \lfloor qm/p\rfloor}$ (en appelant $m$ le
-nombre $2i$ ou $p-2i$ selon que $0<i<\frac{p}{4}$ ou
-$\frac{p}{4}<i<\frac{p}{2}$, de sorte que $m$ parcourt aussi les
-entiers de $1$ à $\frac{p-1}{2}$ quand $i$ les parcourt).
-
-Cette dernière expression admet l'interprétation géométrique
-suivante : $\Legendre{q}{p}$ vaut $(-1)^\mu$ avec $\mu$ le nombre de
-points $(m,n)$ à coordonnées entières telles que $0<m<\frac{p}{2}$ et
-$0<n<\frac{q}{p}m$ et (donc) $0<n<\frac{q}{2}$, ou, si l'on préfère,
-le nombre de points à coordonnées entières strictement à l'intérieur
-du triangle du plan dont les sommets sont $(0,0)$, $(\frac{p}{2},0)$
-et $(\frac{p}{2},\frac{q}{2})$. On en déduit que
-$\Legendre{p}{q} \Legendre{q}{p}$ est $(-1)^{\mu+\nu}$ avec $\mu+\nu$
-le nombre de points $(m,n)$ à coordonnées entières vérifiant
-$0<m<\frac{p}{2}$ et $0<n<\frac{q}{2}$ : on a bien $\mu+\nu
-= \frac{(p-1)(q-1)}{4}$.
-\end{proof}
-\begin{proof}[Seconde démonstration]
-Considérons $\FF_{q^r} = \FF_q(\zeta)$ (où $r$ est l'ordre
-multiplicatif de $p$ modulo $q$) l'extension de $\FF_q$ par une racine
-primitive $p$-ième de l'unité $\zeta$, c'est-à-dire le corps de
-décomposition de $\Phi_p(X)$ sur $\FF_q$
-(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine. Dans
-ce corps, considérons la somme
-\[
-G = \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^i
-\]
-où on confond abusivement un $i \in \FF_p$ avec un représentant
-quelconque de celui-ci dans $\ZZ$ (puisque $\Legendre{i}{p}$ et
-$\zeta^i$ ne dépendent de la classe de $i$ modulo $p$).
-
-On a alors $G^2
-= \sum_{i,j\in \FF_p^\times} \Legendre{ij}{p} \zeta^{i+j}
-= \sum_{i,t \in \FF_p^\times} \Legendre{t}{p} \zeta^{i(1+t)}$ (en
-posant $t = j/i \in \FF_p^\times$ et en utilisant le fait que
-$\Legendre{i}{p}^2 = 1$) ; comme $\sum_{i\in\FF_p^\times} \zeta^{iu}$
-vaut $-1$ si $u \in \FF_p^\times$ et vaut $p - 1$ si $u = 0$, on en
-déduit (en distinguant selon que $t=-1$ ou non) $G^2
-= \Legendre{-1}{p}(p-1) - \sum_{t\neq 0,-1} \Legendre{t}{p}
-= \Legendre{-1}{p} p$ car $\sum_{t\in\FF_p^\times} \Legendre{t}{p} =
-0$ en vertu de \ref{denombrement-carres-f-q}.
-
-Par ailleurs, $G^q = \Frob_q(G)
-= \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^{qi}
-= \sum_{j\in\FF_p^\times} \Legendre{q}{p} \Legendre{j}{p} \zeta^j$ (en
-posant $j = qi$ et en utilisant de nouveau le fait que
-$\Legendre{q}{p}$ est son inverse), donc $G^q = \Legendre{q}{p} G$, et
-par conséquent $G^{q-1} = \Legendre{q}{p}$.
-
-En écrivant $G^{q-1} = (G^2)^{(q-1)/2}$, on a donc prouvé
-$\Legendre{q}{p} = \Legendre{-1}{p}^{(q-1)/2} p^{(q-1)/2} =
-(-1)^{(p-1)(q-1)/4} \Legendre{p}{q}$ ; cette égalité entre éléments de
-$\{\pm 1\}$ a lieu dans $\FF_{q^r}$ donc dans $\ZZ$ : c'est ce qu'on
-voulait prouver.
-\end{proof}
-
-Pour ce qui est du caractère quadratique de $2$, il est déterminé par
-la proposition suivante souvent appelée « formule complémentaire » :
-\begin{proposition2}\label{formule-complementaire}
-Soit $p$ un nombre premier impair. On a alors :
-\[
-\Legendre{2}{p} = (-1)^{(p^2-1)/8}
-\]
---- c'est-à-dire $\Legendre{2}{p} = 1$ si $p\equiv 1,7 \pmod{8}$ et
-$\Legendre{2}{p} = -1$ si $p\equiv 3,5 \pmod{8}$.
-\end{proposition2}
-\begin{proof}[Première démonstration]
-Convenons pour cette démonstration de représenter les éléments de
-$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
-dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
-lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
-$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
-l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$.
-
-Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
-$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$. Considérons
-maintenant le produit $\prod_{i=1}^{(p-1)/2} 2\bar\imath$ : on peut
-manifestement l'écrire comme $2^{(p-1)/2} (\frac{p-1}{2})!$
-modulo $p$. Mais par ailleurs on ne peut pas avoir $2\bar\imath =
-\pm 2\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
-donc les $2\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
-parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ (donné par
-$(-1)^{\lfloor 4i/p\rfloor}$ si l'on veut) vaut $+$ pour
-$0<i<\frac{p}{4}$ et $-$ pour $\frac{p}{4}<i<\frac{p}{2}$. Le nombre
-de signes $-$ est donc égal au nombre d'entiers entre $\frac{p}{4}$ et
-$\frac{p}{2}$ et il est facile de se convaincre (par exemple en
-considérant séparément chaque cas $1,3,5,7$ modulo $8$) que le signe
-du produit est alors $(-1)^{(p^2-1)/8}$. Ainsi,
-$\prod_{i=1}^{(p-1)/2} 2\bar\imath =
-(-1)^{(p^2-1)/8}(\frac{p-1}{2})!$, et en comparant les deux
-expressions trouvées et en utilisant \ref{formule-symbole-legendre},
-on a $\Legendre{2}{p} = (-1)^{(p^2-1)/8}$.
-
-(Cette démonstration a déjà été donnée, dans un cas particulier,
-en \ref{tonelli-shanks-pour-5-mod-8}.)
-\end{proof}
-\begin{proof}[Seconde démonstration]
-Considérons $\FF_{p^r} = \FF_p(\zeta)$ (où $r$ est l'ordre
-multiplicatif de $8$ modulo $p$) l'extension de $\FF_p$ par une racine
-primitive $8$-ième de l'unité $\zeta$, c'est-à-dire le corps de
-décomposition de $\Phi_8(X)$ sur $\FF_p$
-(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine. Dans
-ce corps, considérons la somme
-\[
-G = \zeta - \zeta^3 - \zeta^5 + \zeta^7
-\]
-
-On a alors $G^2 = 4 - 4\zeta^4 = 8$.
-
-Par ailleurs, $G^p = \Frob_p(G) = \zeta^p - \zeta^{3p} - \zeta^{5p}
-+ \zeta^{7p}$, donc $G^p = (-1)^{(p^2-1)/8} G$ (en considérant
-séparément les cas $p\equiv 1,7\pmod{8}$ et $p\equiv 3,5\pmod{8}$), et
-par conséquent $G^{p-1} = (-1)^{(p^2-1)/8}$.
-
-En écrivant $G^{p-1} = (G^2)^{(p-1)/2}$, on a donc prouvé
-$(-1)^{(p^2-1)/8} = 8^{(p-1)/2} = \Legendre{8}{p} = \Legendre{2}{p}$ ;
-cette égalité entre éléments de $\{\pm 1\}$ a lieu dans $\FF_{p^r}$
-donc dans $\ZZ$ : c'est ce qu'on voulait prouver.
-
-Signalons la variante suivante. L'élément $ζ+ζ_{-1}$ est,
-dans $𝐅_{p^r}$ une racine carré de $2$ car
-$(ζ+ζ_{-1})²=2+ζ²+{ζ²}^{-1}=2$. Il en résulte que $2$ est un carré
-dans $𝐅_p$ si et seulement si $ζ^p+ζ^{-p}=ζ+ζ^{-1}$. Cette condition
-ne dépend que de $±p$ modulo $8$ et on vérifie immédiatement quelles
-sont les valeurs pour lesquelles elle est satisfaite.
-\end{proof}
-
-\begin{remarque2}
-L'étude des nombres premiers $p$ pour lesquels $2$ est un \emph{cube}
-est plus délicate et s'insère naturellement dans la « théorie
-non abélienne du corps de classes » (ou « programme de Langlands »).
-On démontre que le nombre de solutions
-dans $𝐅_p$ de l'équation $x³=2$
-est $1+a_p$, où les $a_n$ sont les coefficients
-de la série formelle
-\[
-x∏_{n=1}^∞ \big((1-x^{6n})(1-x^{18n})\big)=∑^∞_{n=1} a_n x^n.
-\]
-% cf. nouveau livre de Katô p. 36. À déplacer ?
-\end{remarque2}
-
-\begin{remarques2}\label{remarque-periodicite-symbole-legendre}
-La loi de réciprocité quadratique et la formule complémentaire (ainsi
-que la formule \ref{formule-symbole-legendre} pour le cas $a=-1$)
-permettent de conclure que $\Legendre{a}{p}$, qui est évidemment une
-fonction périodique de $a$ à $p$ fixé, est aussi, ce qui n'était pas
-évident a priori, une fonction périodique de $p$ à $a$ fixé (au sens
-où il existe un entier $T$ ne dépendant que de $a$ tel que si $p,p'$
-sont premiers impairs et $p \equiv p' \pmod{T}$ alors $\Legendre{a}{p}
-= \Legendre{a}{p'}$) ; plus précisément, il admet pour période $T =
-4|a|$ (cela sera démontré en \ref{proprietes-symbole-jacobi}
-ci-dessous). Ceci peut inciter à vouloir donner un sens à
-$\Legendre{a}{n}$ dans des cas où $n$ n'est plus nécessairement
-premier, en appliquant cette périodicité (par exemple, puisque
-$\Legendre{3}{p} = +1$ pour tout premier $p \equiv 1 \pmod{12}$, on
-est tenté de convenir que $\Legendre{3}{25} = +1$ et $\Legendre{3}{85}
-= +1$ même si $25$ et $85$ ne sont pas premiers et que $3$ n'est même
-pas un carré dans $\ZZ/25\ZZ$ ni $\ZZ/85\ZZ$). Le symbole de Jacobi
-constitue une telle généralisation du symbole de Legendre :
-\end{remarques2}
-
-\subsection{Symboles de Jacobi et de Kronecker}
-
-\begin{definition2}\label{definition-symbole-jacobi}
-Pour tout $a \in \ZZ$ et tout $b \in \NN$ impair, on
-appelle \emph{symbole de Jacobi} de $a$ et $b$, et on note
-$\Legendre{a}{b}$, le symbole défini par $\Legendre{a}{b}
-= \Legendre{a}{p_1}\cdots \Legendre{a}{p_k}$ où $b = p_1\cdots p_k$
-avec $p_i$ des nombres premiers impairs, et où $\Legendre{a}{p_i}$
-désigne alors le symbole de
-Legendre (\ref{definition-symbole-legendre}).
-\end{definition2}
-
-\begin{proposition2}\label{proprietes-symbole-jacobi}
-Le symbole de Jacobi défini en \ref{definition-symbole-jacobi} a les
-propriétés suivantes :
-\begin{itemize}
-\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
-premiers entre eux.
-\item Pour tous $a,a',b \in \ZZ$ avec $b$ positif impair, on a
-$\Legendre{aa'}{b} = \Legendre{a}{b} \Legendre{a'}{b}$.
-\item Pour tous $a,b,b' \in \ZZ$ avec $b,b'$ positifs impairs, on a
-$\Legendre{a}{bb'} = \Legendre{a}{b} \Legendre{a}{b'}$.
-\item À $b$ positif impair fixé, la fonction $\Legendre{a}{b}$ est
-périodique admettant $b$ pour période.
-\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
-admettant $4|a|$ pour période, et même $2|a|$ si $a \equiv 1
-\pmod{4}$ et $|a|$ si $a \equiv 0 \pmod{4}$.
-\item Pour tout $b$ positif impair, on a $\Legendre{-1}{b} =
-(-1)^{(b-1)/2}$.
-\item Pour tout $b$ positif impair, on a $\Legendre{2}{b} =
-(-1)^{(b^2-1)/8}$.
-\item Pour tous $a,b$ positifs impairs, on a
-$\Legendre{a}{b} \Legendre{b}{a} = (-1)^{(a-1)(b-1)/4}$.
-\end{itemize}
-\end{proposition2}
-\begin{proof}
-Les deux premières propriétés découlent immédiatement des propriétés
-correspondantes du symbole de Legendre. La troisième propriété est
-une conséquence immédiate de la définition. La quatrième propriété
-(périodicité en $a$) découle de nouveau de la propriété correspondante
-du symbole de Legendre. La propriété suivante (périodicité en $b$)
-sera démontrée en dernier.
-
-Les formules $\Legendre{-1}{b} = (-1)^{(b-1)/2}$, $\Legendre{2}{b} =
-(-1)^{(b^2-1)/8}$ et $\Legendre{a}{b} \Legendre{b}{a} =
-(-1)^{(a-1)(b-1)/4}$ résultent des formules correspondantes pour le
-symbole de Legendre
-(\ref{formule-symbole-legendre}, \ref{formule-complementaire}
-et \ref{loi-reciprocite-quadratique}) et du fait que ces formules sont
-multiplicatives en $b$.
-
-Montrons enfin que $\Legendre{a}{b}$ est périodique en $b$ avec les
-périodes annoncées. Si $a$ est positif impair, on a $\Legendre{a}{b}
-= (-1)^{(a-1)(b-1)/4} \Legendre{b}{a}$ comme on vient de le voir, et
-le membre de droite admet $4a$ pour période ou même $2a$ si $a \equiv
-1 \pmod{4}$ ; si $a = -1$ alors $\Legendre{-1}{b}$ est périodique de
-période $4$ et on en déduit le résultat pour tout $a$ impair. Enfin,
-si $a = 2^v a'$ avec $a'$ impair, on a $\Legendre{a}{b}
-= \Legendre{2}{b}^v \Legendre{a'}{b}$. Pour $v=1$ (cas où $a \equiv
-2 \pmod{4}$), le premier facteur a pour période $8$ et le second admet
-la période $4|a'|$, donc le produit admet la période $8|a'| = 4|a|$ ;
-pour $v=2$, le premier facteur est constant et le second admet la
-période $4|a'|$ donc le produit admet la période $4|a'| = |a|$ ; et
-pour $v\geq 3$, le premier facteur admet la période $8$ et le second
-la période $4|a'|$, donc le produit admet la période $8|a'|$
-donc $|a|$.
-\end{proof}
-
-\begin{remarques2}
-\begin{itemize}
-\item Comme on l'a déjà illustré
-en \ref{remarque-periodicite-symbole-legendre} par l'exemple de
-$\Legendre{3}{25} = +1$ et $\Legendre{3}{85} = +1$, on peut très bien
-avoir $\Legendre{a}{b} = +1$ sans que $a$ soit un carré
-dans $\ZZ/b\ZZ$. En revanche, si $\Legendre{a}{b} = -1$ (avec $b$
-positif impair) alors $a$ n'est pas un carré dans $\ZZ/b\ZZ$ puisque
-$a$ n'est pas un carré modulo l'un des facteurs premiers de $b$.
-Voir cependant \ref{symbole-de-jacobi-et-corps-finis} ci-dessous.
-\item La formule \ref{formule-symbole-legendre} n'est pas valable en
-général pour le symbole de Jacobi, même si $a$ est effectivement un
-carré modulo $b$ (le nombre noté $p$
-en \ref{formule-symbole-legendre}) : par exemple, $\Legendre{11}{35} =
-+1$, et de fait $11 \equiv 9^2 \pmod{35}$, pourtant
-$11^{(35-1)/2} \equiv 16 \pmod{35}$.
-\end{itemize}
-\end{remarques2}
-
-La proposition suivante est utile pour certains calculs, mais elle est
-vraie pour des raisons essentiellement triviales :
-\begin{proposition2}\label{symbole-de-jacobi-et-corps-finis}
-Soit $q$ une puissance d'un nombre premier $p$ impair, et $a \in \ZZ$
-non multiple de $p$. Alors $a$ est un carré dans $\FF_q$ si et
-seulement si $\Legendre{a}{q} = +1$ où $\Legendre{a}{q}$ désigne le
-symbole de Jacobi.
-\end{proposition2}
-\begin{proof}
-Écrivons $q = p^r$. Si $r$ est pair alors $\Legendre{a}{q}
-= \Legendre{a}{p}^2 = +1$, et $a$ est bien un carré dans $\FF_q$
-d'après \ref{carres-extensions-corps-finis}. Si $r$ est impair alors
-$\Legendre{a}{q} = \Legendre{a}{p}^r = \Legendre{a}{p}$, et $a$ est un
-carré dans $\FF_q$ si et seulement s'il l'est dans $\FF_p$ de nouveau
-d'après \ref{carres-extensions-corps-finis}.
-\end{proof}
-
-\begin{remarque2}
-On définit parfois une généralisation encore plus poussée des symboles
-de Legendre et de Jacobi : le \emph{symbole de Kronecker}
-$\Legendre{a}{b}$ défini pour tous $a,b\in\ZZ$. Celui-ci est défini
-en écrivant $b = u p_1\cdots p_k$ avec $u \in \{\pm 1\}$ et $p_i$ des
-nombres premiers (cette fois $p_i=2$ est admis), où $\Legendre{a}{p}$
-désigne le symbole de Legendre (\ref{definition-symbole-legendre}) si
-$p$ est premier impair, et de plus :
-\[\Legendre{a}{2} = \left\{
-\begin{array}{ll}
-0&\textrm{si $a$ est pair}\\
-(-1)^{(a^2-1)/8}&\textrm{si $a$ est impair}\\
-\end{array}
-\right.\]
-\[\Legendre{a}{-1} = \left\{
-\begin{array}{ll}
-1&\textrm{si $a\geq 0$}\\
--1&\textrm{si $a<0$}\\
-\end{array}
-\right.\]
-et enfin
-\[\Legendre{a}{0} = \left\{
-\begin{array}{ll}
-1&\textrm{si $a = \pm 1$}\\
-0&\textrm{sinon}\\
-\end{array}
-\right.\]
-Le prix à payer pour une telle généralisation est principalement de
-perdre la périodicité de $\Legendre{a}{b}$ par rapport à $b$ lorsque
-$a \equiv -1 \pmod{4}$ (ainsi que la périodicité par rapport à $a$
-lorsque $b \leq 0$). En fait, le choix de $\Legendre{a}{2} =
-(-1)^{(a^2-1)/8}$ (pour $a$ impair) est quelque peu arbitraire, et le
-symbole de Kronecker ne possède pas le caractère naturel du symbole de
-Jacobi. Il vérifie néanmoins les propriétés suivantes dont la
-vérification est laissée au lecteur :
-\begin{itemize}
-\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
-premiers entre eux.
-\item Pour tous $a,a',b \in \ZZ$, on a $\Legendre{aa'}{b}
-= \Legendre{a}{b} \Legendre{a'}{b}$.
-\item Pour tous $a,b,b' \in \ZZ$, on a $\Legendre{a}{bb'}
-= \Legendre{a}{b} \Legendre{a}{b'}$ sauf éventuellement si $a=-1$ et
-$bb'=0$.
-\item À $b>0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
-admettant $4b$ pour période, et même $b$ si $b \not\equiv 2 \pmod{4}$.
-\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
-admettant $4|a|$ pour période si $a \not\equiv -1 \pmod{4}$, et même
-$|a|$ si $a \equiv 0,1 \pmod{4}$.
-\end{itemize}
-\end{remarque2}
-
-
\section{Factorisation de polynômes sur les corps finis}\label{factorisation-polynomes-corps-finis}
On a vu dans la section \ref{equations-quadratiques-corps-finis}
diff --git a/chapitres/corps-finis.tex b/chapitres/corps-finis.tex
index 6448e5a..8c6650d 100644
--- a/chapitres/corps-finis.tex
+++ b/chapitres/corps-finis.tex
@@ -211,8 +211,8 @@ bien un sous-corps de $K$ à $q$ éléments.
\begin{proposition2}\label{existence-et-unicite-corps finis}
Soit $q=p^r$ une puissance d'un nombre premier. Il existe un corps à
$q$ éléments, unique à isomorphisme près. Un tel corps est un corps
-de décomposition (\refext{Alg}{décomposition}) du polynôme
-$X^q-X∈𝐅_p[X]$.
+de décomposition (\refext{Alg}{définition corps de décomposition}) du
+polynôme $X^q-X∈𝐅_p[X]$.
\end{proposition2}
\begin{proof}
L'existence se déduit du lemme \ref{sous-corps-a-q-elements} appliqué
@@ -1782,6 +1782,606 @@ $p=7$&$p^n=7$&$h_1 = X + 4$\\
\end{tabular}
\end{center}
+\section{Le caractère quadratique et la réciprocité quadratique}\label{caractere-quadratique-corps-finis}
+
+\subsection{Le caractère quadratique en caractéristique impaire}\label{caractere-quadratique-corps-finis-caracteristique-impaire}
+
+\subsubsection{} Si on se penche sur la question de la factorisation
+des polynômes (ou la résolution des équations) de degré $2$ sur
+$\FF_q$, en remarquant que, pour $q$ impair l'équation $X^2 + bX + c =
+0$ peut se réécrire sous la forme $(X+\frac{b}{2})^2 =
+(\frac{b^2}{4} - c)$, on voit que tout se ramène, en caractéristique
+impaire, à déterminer \emph{quels éléments de $\FF_q$ sont des
+ carrés}. Nous allons, pour approfondir cette question, introduire
+la définition suivante :
+
+\begin{definition2}\label{definition-caractere-quadratique}
+Soit $q$ une puissance d'un nombre premier impair. On
+appelle \emph{caractère quadratique} sur $\FF_q$ la fonction
+$a \mapsto a^{(q-1)/2}$. On note $\FF_q^{\times2}$ l'ensemble des
+éléments de $\FF_q^\times$ qui sont des carrés.
+\end{definition2}
+
+\begin{proposition2}\label{denombrement-carres-f-q}
+Si $q$ est une puissance d'un nombre premier impair, alors le caractère
+quadratique ne prend sur $\FF_q^\times$ que les valeurs $+1$ et $-1$,
+et on a $a \in \FF_q^{\times2}$ si et seulement si $a^{(q-1)/2} =
++1$ ; de plus, $\# \FF_q^{\times2} = \frac{1}{2}(q-1)$.
+\end{proposition2}
+\begin{proof}
+L'application $z \mapsto z^2$, vue comme un morphisme
+$\FF_q^\times \to \FF_q^\times$, a pour noyau $\{\pm 1\}$ (de
+cardinal $2$), et pour image $\FF_q^{\times2}$, donc
+$2\, \#\FF_q^{\times2} = \#\FF_q^{\times}$ : ceci montre la dernière
+affirmation.
+
+Si $e = a^{(q-1)/2}$ avec $a \in \FF_q^\times$, alors $e^2 = a^{q-1} =
+1$, donc $e$ vaut $+1$ ou $-1$.
+
+Si $a = b^2$ avec $b \in \FF_q^\times$, alors $a^{(q-1)/2} = b^{q-1} =
++1$. On a donc montré que sur tout élément de $\FF_q^{\times2}$ le
+caractère quadratique vaut $+1$ : comme on vient de voir qu'il y a
+$\frac{1}{2}(q-1)$ tels éléments et que le polynôme $X^{(q-1)/2} - 1$
+(de degré $\frac{1}{2}(q-1)$) n'est pas nul, il ne peut s'annuler en
+aucun autre point de $\FF_q$ : on voit donc que réciproquement si
+$a^{(q-1)/2} = +1$ alors $a \in \FF_q^{\times2}$.
+\end{proof}
+
+On pouvait également démontrer ce résultat en utilisant un élément
+primitif $g$ (cf. \ref{cyclicite-groupe-multiplicatif-corps}) : les
+éléments de $\FF_q^{\times2}$ sont ceux qui s'écrivent $g^{2i}$ avec
+$i$ entier (et bien défini modulo $\frac{1}{2}(q-1)$).
+
+\begin{corollaire2}\label{produits-de-non-carres-dans-f-q}
+Un produit $ab$ dans $\FF_q$ est un carré \emph{si et seulement si}
+les deux facteurs $a,b$ sont soit tous deux des carrés soit tous deux
+des non-carrés.
+\end{corollaire2}
+\begin{proof}
+Cela découle de \ref{denombrement-carres-f-q} et du fait que le
+caractère quadratique est un morphisme multiplicatif : $(ab)^{(q-1)/2}
+= a^{(q-1)/2}\, b^{(q-1)/2}$.
+\end{proof}
+
+On peut déjà résoudre complètement la question du caractère
+quadratique de $-1$.
+
+\begin{corollaire2}\label{caractere-quadratique-de-moins-un}
+Pour $q$ une puissance d'un nombre premier impair, l'élément $-1$ de
+$\FF_q$ est un carré \emph{si et seulement si} $q \equiv 1 \pmod{4}$.
+\end{corollaire2}
+\begin{proof}
+Cela découle de \ref{denombrement-carres-f-q} et du fait que
+$(-1)^{(q-1)/2}$ vaut $+1$ si $q \equiv 1 \pmod{4}$ et $-1$ si $q
+\equiv 3 \pmod{4}$.
+\end{proof}
+
+On va voir en \ref{reciprocite-quadratique} plus bas ce qu'on peut
+dire du caractère quadratique de $2$ et plus généralement de tout
+entier.
+
+\subsubsection{} Le calcul du caractère quadratique peut se faire
+efficacement par un algorithme d'exponentiation rapide : ceci permet
+donc de savoir effectivement si un élément donné de $\FF_q^\times$
+admet une racine carrée. (On renvoie à \ref{remarques-critere-rabin}
+pour la question de la représentation des corps finis et
+l'algorithmique dans ceux-ci ; mais pour beaucoup de questions
+algorithmiques considérées ici, le cas où $q = p$ est premier et
+$\FF_q = \ZZ/p\ZZ$ est déjà intéressant.) Calculer effectivement la
+racine carrée d'un élément qui en admet une est une question plus
+délicate, qui sera considérée
+en \refext{ACF}{equations-quadratiques-corps-finis}.
+
+\begin{lemme2}\label{carres-extensions-corps-finis}
+Soit $q = p^r$ avec $p$ premier impair. Si $r$ est impair, alors un
+élément de $\FF_p$ est un carré dans $\FF_p$ si et seulement si il
+l'est dans $\FF_q$ (autrement dit, $\FF_q^{\times 2} \cap \FF_p
+= \FF_p^{\times 2}$). Si $r$ est pair, alors tout élément de $\FF_p$
+est un carré dans $\FF_q$.
+\end{lemme2}
+\begin{proof}
+On peut par exemple, pour $a \in \FF_p^\times$, écrire $a^{(q-1)/2} =
+a^{(p^r-1)/2} = (a^{(p-1)/2})^{p^{r-1} + \cdots + p + 1}$, et
+$a^{(p-1)/2}$ vaut $+1$ ou $-1$ selon que $a$ est un carré
+dans $\FF_p$, et la parité de $p^{r-1} + \cdots + p + 1$ est la même
+que celle de $r$, ce qui démontre le résultat.
+
+Une autre démonstration consiste à considérer le polynôme $X^2 - a$ et
+à lui
+appliquer \ref{corollaire-scindage-partiel-polynomes-corps-finis}.
+\end{proof}
+
+Mentionnons par ailleurs le résultat combinatoire suivant, qui est une
+application inattendue des propriétés du caractère quadratique sur les
+corps finis :
+\begin{proposition2}\label{matrice-d-hadamard-par-corps-finis}
+Soit $q$ une puissance d'un nombre premier vérifiant $q \equiv
+3 \pmod{4}$. Alors il existe une matrice $M$ de taille $(q+1)\times
+(q+1)$ à coefficients dans $\{\pm 1\}$ telle que deux lignes
+distinctes quelconques de $M$ ont la même valeur en $\frac{1}{2}(q+1)$
+de leurs entrées et une valeur opposée en les $\frac{1}{2}(q+1)$
+autres.
+\end{proposition2}
+\begin{proof}
+En notant $\PP^1(\FF_q) = \FF_q \cup \{\infty\}$, on définit une
+fonction $\varphi\colon \PP^1(\FF_q) \times \PP^1(\FF_q) \to \{\pm
+1\}$ par $\varphi(\infty,\infty) = \varphi(x,\infty)
+= \varphi(\infty,y) = +1$ si $x \in \FF_q$ et $y \in \FF_q$, par
+$\varphi(x,x) = -1$ pour tout $x \in \FF_q$, et par $\varphi(x,y) =
+(x-y)^{(q-1)/2}$ (c'est-à-dire $+1$ ou $-1$ selon que $x-y$ est un
+carré ou non dans $\FF_q$, cf. \ref{denombrement-carres-f-q}) si
+$x\neq y$ avec $x,y\in \FF_q$. La matrice indicée par
+$\PP^1(\FF_q) \times \PP^1(\FF_q)$ dont les coefficients sont donnés
+par la fonction $\varphi$ répond à la question : pour le montrer, il
+s'agit de voir que si $x,x' \in \PP^1(\FF_q)$ avec $x\neq x'$ alors il
+existe $\frac{1}{2}(q+1)$ valeurs $y \in \PP^1(\FF_q)$ exactement
+telles que $\varphi(x,y) = \varphi(x',y)$.
+
+Si $x$ vaut $\infty$, il s'agit de voir que $\frac{1}{2}(q+1)$ valeurs
+$y$ vérifient $\varphi(x',y) = -1$, c'est-à-dire (puisque
+$\varphi(x',x')=-1$) que $\frac{1}{2}(q-1)$ éléments $y \in \FF_q$
+sont tels que $x'-y$ ne soit pas un carré dans $\FF_q$, ce qui est
+bien le cas (cf. \ref{denombrement-carres-f-q}). Si $x,x' \in \FF_q$,
+on s'intéresse à $\varphi(x,y)/\varphi(x',y)$. Si $y \in \FF_q$ et
+$y \not\in \{x,x'\}$, cette fonction vaut
+$(\frac{x-y}{x'-y})^{(q-1)/2}$, or l'expression $\frac{x-y}{x'-y}$
+prend toutes les valeurs de $\FF_q$ sauf $0$ et $1$, donc
+$(\frac{x-y}{x'-y})^{(q-1)/2}$ prend $\frac{1}{2}(q-3)$ fois la
+valeur $+1$ ; si $y = \infty$, l'expression
+$\varphi(x,y)/\varphi(x',y)$ vaut $+1$ ; si $y=x$ ou $y=x'$, enfin,
+l'expression $\varphi(x,y)/\varphi(x',y)$ vaut $-(x'-x)^{(q-1)/2}$ et
+$-(x-x')^{(q-1)/2}$ respectivement, et ces valeurs sont opposées
+puisque $q\equiv 3 \pmod{4}$ entraîne $(-1)^{(q-1)/2} = -1$ ; on a
+donc montré que $\varphi(x,y)/\varphi(x',y)$ prend exactement
+$\frac{1}{2}(q+1)$ fois la valeur $+1$ lorsque $y$
+parcourt $\PP^1(\FF_q)$.
+\end{proof}
+
+Une matrice telle que fournie par la
+proposition \ref{matrice-d-hadamard-par-corps-finis}
+s'appelle \emph{matrice d'Hadamard} de taille $q+1$. On conjecture
+qu'il existe une matrice d'Hadamard de toute taille multiple de $4$.
+
+\subsection{La caractéristique $2$}\label{caractere-quadratique-corps-finis-caracteristique-2}
+
+\subsubsection{} En caractéristique $2$, calculer
+des racines carrées dans $\FF_q = \FF_{2^r}$ est facile : on a
+$x^{2^r} = x$ d'après \refext{Fin}{petit-theoreme-fermat}, donc $x^{2^{r-1}}$
+est une racine carrée de $x$. À la différence du cas où $2$ est
+inversible, cependant, savoir calculer des racines carrées ne permet
+pas de résoudre toutes les équations quadratiques puisqu'on ne peut
+pas écrire $X^2 + bX + c = 0$ sous la forme $(X+\frac{b}{2})^2 +
+(c-\frac{b^2}{4}) = 0$. À la place, si on note $\wp(Z) = Z^2 + Z$,
+l'équation $X^2 + bX + c = 0$, lorsque $b\neq 0$ (le cas $b=0$ ayant
+déjà été traité) peut se réécrire $\wp(X/b)+(c/b^2) = 0$, soit $X =
+b\,\root\wp\of{c/b^2}$ si on note $\root\wp\of E$ une solution (si
+elle existe) de l'équation $Z^2+Z = E$, l'autre solution étant alors
+$\root\wp\of E + 1$ (puisque $\wp(Z+1) = \wp(Z)$).
+
+\begin{definition2}\label{definition-caractere-quadratique-en-caracteristique-2}
+Soit $q = 2^r$ une puissance de $2$. On appelle \emph{caractère
+quadratique additif} sur $\FF_q$ la fonction $\tau \colon a \mapsto a
++ a^2 + a^4 + a^8 + \cdots + a^{2^{r-1}}$ (qu'on notera aussi $\tau_r$
+en cas d'ambiguïté). On note $\wp\FF_q$ l'ensemble des éléments de
+$\FF_q$ qui sont dans l'image de la fonction $\wp\colon z \mapsto z^2
++ z$.
+\end{definition2}
+
+On peut aussi considérer $\tau$ comme la trace pour l'extension
+$\FF_q\bo\FF_2$ (cf. \ref{trace-et-norme-corps-finis}).
+
+\begin{proposition2}\label{denombrement-artin-schreier-2-f-q}
+Si $q$ est une puissance de $2$, alors le caractère quadratique
+additif $\tau$ ne prend sur $\FF_q$ que les valeurs $0$ et $1$, et on
+a $a \in \wp\FF_q$ si et seulement si $\tau(a) = 0$ ; de plus,
+$\#(\wp\FF_q) = \frac{q}{2}$.
+\end{proposition2}
+\begin{proof}
+L'application $\wp\colon z \mapsto z^2+z$, vue comme une application
+$\FF_2$-linéaire $\FF_q \to \FF_q$, a pour noyau $\{0,1\}$ (de
+cardinal $2$) puisque $0,1$ sont les deux solutions de $Z^2 + Z = 0$ ;
+et elle a pour image $\wp\FF_q$, donc $2\, \#(\wp\FF_q) = \#\FF_q$ :
+ceci montre la dernière affirmation.
+
+Si $e = \tau(a)$ avec $a \in \FF_q$, alors $\wp(e) = e^2 + e = (a^2 +
+a^4 + \cdots + a^q) + (a + a^2 + \cdots + a^{q/2}) = 0$ puisque $a^{q}
+= a$, donc $e$ vaut $0$ ou $1$.
+
+Si $a = \wp(b)$ avec $b \in \FF_q$, alors $\tau(a) = a + a^2 + \cdots
++ a^{q/2} = (b^2 + b) + (b^4 + b^2) + \cdots + (b^{q} + b^{q/2}) = 0$.
+On a donc montré que sur tout élément de $\wp\FF_q$ le caractère
+quadratique additif $\tau$ vaut $0$ : comme on vient de voir qu'il y a
+$\frac{q}{2}$ tels éléments et que le polynôme $X + X^2 + X^4 + \cdots
++ X^{q/2}$ (de degré $\frac{q}{2}$) n'est pas nul, il ne peut
+s'annuler en aucun autre point de $\FF_q$ : on voit donc que
+réciproquement si $\tau(a) = 0$ alors $a \in \wp\FF_q$.
+\end{proof}
+
+\subsection{Symbole de Legendre, réciprocité quadratique et formule complémentaire}\label{reciprocite-quadratique}
+
+On s'intéresse dans cette section au caractère quadratique des
+éléments de $\FF_p$ avec $p$ un nombre premier impair.
+
+\begin{definition2}\label{definition-symbole-legendre}
+Si $p$ est un nombre premier impair et $a$ un entier, on
+appelle \emph{symbole de Legendre} de $a$ modulo $p$, et on note
+$\Legendre{a}{p}$, l'entier valant $0$ si $p|a$, et $1$ si $a$ est un
+carré dans $\FF_p$, et $-1$ si $a$ n'est pas un carré dans $\FF_p$.
+\end{definition2}
+
+Il résulte trivialement de \ref{denombrement-carres-f-q} et
+de \ref{produits-de-non-carres-dans-f-q} que :
+\begin{proposition2}\label{formule-symbole-legendre}
+Si $p$ est un nombre premier impair et $a$ un entier, alors
+\[
+\Legendre{a}{p} \equiv a^{(p-1)/2} \pmod{p}
+\]
+De plus, quels que soient les entiers $a,b$, on a $\Legendre{ab}{p}
+= \Legendre{a}{p} \Legendre{b}{p}$.
+\end{proposition2}
+
+L'énoncé suivant, qui compare le caractère quadratique de $p$ modulo
+$q$ au caractère quadratique de $q$ modulo $p$, et dont on va donner
+deux démonstrations, porte le nom de \emph{loi de réciprocité
+quadratique} :
+
+\begin{theoreme2}\label{loi-reciprocite-quadratique}
+Soient $p,q$ deux nombres premiers impairs distincts. On a alors :
+\[
+\Legendre{p}{q} \Legendre{q}{p} = (-1)^{(p-1)(q-1)/4}
+\]
+--- c'est-à-dire $\Legendre{q}{p} = \Legendre{p}{q}$ sauf si
+$p,q \equiv 3 \pmod{4}$ auquel cas $\Legendre{q}{p} =
+-\Legendre{p}{q}$.
+\end{theoreme2}
+\begin{proof}[Première démonstration]
+Convenons pour cette démonstration de représenter les éléments de
+$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
+dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
+lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
+$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
+l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$. Avec
+cette définition, si $k \in \ZZ$ n'est pas multiple de $p$, son
+« signe » modulo $p$ (c'est-à-dire $+1$ ou $-1$ selon qu'il a un
+résidu positif ou négatif) vaut $(-1)^{\lfloor 2k/p\rfloor}$ où
+$\lfloor\tiret\rfloor$ désigne la fonction partie entière. Remarquons
+d'ores et déjà que pour tout entier $i$ non multiple de $p$ on a
+$\lfloor \frac{2qi}{p}\rfloor + \lfloor \frac{q(p-2i)}{p}\rfloor =
+q-1$ (car $\lfloor\theta\rfloor +
+\lfloor q-\theta\rfloor = q-1$ pour tout
+$\theta \in \RR \setminus \ZZ$), et que cet entier est pair, de sorte
+que $(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$
+(ces deux expressions donnent donc le signe de $qi$ modulo $p$).
+
+Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
+$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$. Considérons
+maintenant le produit $\prod_{i=1}^{(p-1)/2} q\bar\imath$ : on peut
+manifestement l'écrire comme $q^{(p-1)/2} (\frac{p-1}{2})!$
+modulo $p$. Mais par ailleurs on ne peut pas avoir $q\bar\imath =
+\pm q\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
+donc les $q\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
+parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ donné par
+$(-1)^{\lfloor 2qi/p\rfloor} = (-1)^{\lfloor q(p-2i)/p\rfloor}$ comme
+on l'a expliqué ; ainsi, $\prod_{i=1}^{(p-1)/2} q\bar\imath =
+(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}(\frac{p-1}{2})!$, et
+en comparant les deux expressions trouvées et en
+utilisant \ref{formule-symbole-legendre}, on a $\Legendre{q}{p} =
+(-1)^{\sum_{i=1}^{(p-1)/2} \lfloor 2qi/p\rfloor}$ (« lemme
+d'Eisenstein »), ou, mieux, $\Legendre{q}{p} =
+(-1)^{\sum_{m=1}^{(p-1)/2} \lfloor qm/p\rfloor}$ (en appelant $m$ le
+nombre $2i$ ou $p-2i$ selon que $0<i<\frac{p}{4}$ ou
+$\frac{p}{4}<i<\frac{p}{2}$, de sorte que $m$ parcourt aussi les
+entiers de $1$ à $\frac{p-1}{2}$ quand $i$ les parcourt).
+
+Cette dernière expression admet l'interprétation géométrique
+suivante : $\Legendre{q}{p}$ vaut $(-1)^\mu$ avec $\mu$ le nombre de
+points $(m,n)$ à coordonnées entières telles que $0<m<\frac{p}{2}$ et
+$0<n<\frac{q}{p}m$ et (donc) $0<n<\frac{q}{2}$, ou, si l'on préfère,
+le nombre de points à coordonnées entières strictement à l'intérieur
+du triangle du plan dont les sommets sont $(0,0)$, $(\frac{p}{2},0)$
+et $(\frac{p}{2},\frac{q}{2})$. On en déduit que
+$\Legendre{p}{q} \Legendre{q}{p}$ est $(-1)^{\mu+\nu}$ avec $\mu+\nu$
+le nombre de points $(m,n)$ à coordonnées entières vérifiant
+$0<m<\frac{p}{2}$ et $0<n<\frac{q}{2}$ : on a bien $\mu+\nu
+= \frac{(p-1)(q-1)}{4}$.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Considérons $\FF_{q^r} = \FF_q(\zeta)$ (où $r$ est l'ordre
+multiplicatif de $p$ modulo $q$) l'extension de $\FF_q$ par une racine
+primitive $p$-ième de l'unité $\zeta$, c'est-à-dire le corps de
+décomposition de $\Phi_p(X)$ sur $\FF_q$
+(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine. Dans
+ce corps, considérons la somme
+\[
+G = \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^i
+\]
+où on confond abusivement un $i \in \FF_p$ avec un représentant
+quelconque de celui-ci dans $\ZZ$ (puisque $\Legendre{i}{p}$ et
+$\zeta^i$ ne dépendent de la classe de $i$ modulo $p$).
+
+On a alors $G^2
+= \sum_{i,j\in \FF_p^\times} \Legendre{ij}{p} \zeta^{i+j}
+= \sum_{i,t \in \FF_p^\times} \Legendre{t}{p} \zeta^{i(1+t)}$ (en
+posant $t = j/i \in \FF_p^\times$ et en utilisant le fait que
+$\Legendre{i}{p}^2 = 1$) ; comme $\sum_{i\in\FF_p^\times} \zeta^{iu}$
+vaut $-1$ si $u \in \FF_p^\times$ et vaut $p - 1$ si $u = 0$, on en
+déduit (en distinguant selon que $t=-1$ ou non) $G^2
+= \Legendre{-1}{p}(p-1) - \sum_{t\neq 0,-1} \Legendre{t}{p}
+= \Legendre{-1}{p} p$ car $\sum_{t\in\FF_p^\times} \Legendre{t}{p} =
+0$ en vertu de \ref{denombrement-carres-f-q}.
+
+Par ailleurs, $G^q = \Frob_q(G)
+= \sum_{i\in\FF_p^\times} \Legendre{i}{p} \zeta^{qi}
+= \sum_{j\in\FF_p^\times} \Legendre{q}{p} \Legendre{j}{p} \zeta^j$ (en
+posant $j = qi$ et en utilisant de nouveau le fait que
+$\Legendre{q}{p}$ est son inverse), donc $G^q = \Legendre{q}{p} G$, et
+par conséquent $G^{q-1} = \Legendre{q}{p}$.
+
+En écrivant $G^{q-1} = (G^2)^{(q-1)/2}$, on a donc prouvé
+$\Legendre{q}{p} = \Legendre{-1}{p}^{(q-1)/2} p^{(q-1)/2} =
+(-1)^{(p-1)(q-1)/4} \Legendre{p}{q}$ ; cette égalité entre éléments de
+$\{\pm 1\}$ a lieu dans $\FF_{q^r}$ donc dans $\ZZ$ : c'est ce qu'on
+voulait prouver.
+\end{proof}
+
+Pour ce qui est du caractère quadratique de $2$, il est déterminé par
+la proposition suivante souvent appelée « formule complémentaire » :
+\begin{proposition2}\label{formule-complementaire}
+Soit $p$ un nombre premier impair. On a alors :
+\[
+\Legendre{2}{p} = (-1)^{(p^2-1)/8}
+\]
+--- c'est-à-dire $\Legendre{2}{p} = 1$ si $p\equiv 1,7 \pmod{8}$ et
+$\Legendre{2}{p} = -1$ si $p\equiv 3,5 \pmod{8}$.
+\end{proposition2}
+\begin{proof}[Première démonstration]
+Convenons pour cette démonstration de représenter les éléments de
+$\ZZ/p\ZZ$ par $-\frac{p-1}{2},\ldots,\frac{p-1}{2}$, et de
+dire d'un élément de $(\ZZ/p\ZZ)^\times$ qu'il est « positif »
+lorsqu'il est congru à l'un des $\frac{p-1}{2}$ entiers
+$1,2,3,\ldots,\frac{p-1}{2}$, et « négatif » lorsqu'il est congru à
+l'un des $\frac{p-1}{2}$ entiers $-\frac{p-1}{2},\ldots,-1$.
+
+Le produit $\prod_{i=1}^{(p-1)/2} \bar\imath$ des éléments positif de
+$(\ZZ/p\ZZ)^\times$ vaut $(\frac{p-1}{2})!$ modulo $p$. Considérons
+maintenant le produit $\prod_{i=1}^{(p-1)/2} 2\bar\imath$ : on peut
+manifestement l'écrire comme $2^{(p-1)/2} (\frac{p-1}{2})!$
+modulo $p$. Mais par ailleurs on ne peut pas avoir $2\bar\imath =
+\pm 2\bar\imath'$ pour $i,i' \in \{1,\ldots,\frac{p-1}{2}\}$ distincts,
+donc les $2\bar\imath$ s'écrivent $\pm\bar\jmath$ avec $\bar\jmath$
+parcourant $1,2,3,\ldots,\frac{p-1}{2}$ et le signe $\pm$ (donné par
+$(-1)^{\lfloor 4i/p\rfloor}$ si l'on veut) vaut $+$ pour
+$0<i<\frac{p}{4}$ et $-$ pour $\frac{p}{4}<i<\frac{p}{2}$. Le nombre
+de signes $-$ est donc égal au nombre d'entiers entre $\frac{p}{4}$ et
+$\frac{p}{2}$ et il est facile de se convaincre (par exemple en
+considérant séparément chaque cas $1,3,5,7$ modulo $8$) que le signe
+du produit est alors $(-1)^{(p^2-1)/8}$. Ainsi,
+$\prod_{i=1}^{(p-1)/2} 2\bar\imath =
+(-1)^{(p^2-1)/8}(\frac{p-1}{2})!$, et en comparant les deux
+expressions trouvées et en utilisant \ref{formule-symbole-legendre},
+on a $\Legendre{2}{p} = (-1)^{(p^2-1)/8}$.
+\end{proof}
+\begin{proof}[Seconde démonstration]
+Considérons $\FF_{p^r} = \FF_p(\zeta)$ (où $r$ est l'ordre
+multiplicatif de $8$ modulo $p$) l'extension de $\FF_p$ par une racine
+primitive $8$-ième de l'unité $\zeta$, c'est-à-dire le corps de
+décomposition de $\Phi_8(X)$ sur $\FF_p$
+(cf. \refext{Fin}{factorisation-phi-n}) dont on note $\zeta$ une racine. Dans
+ce corps, considérons la somme
+\[
+G = \zeta - \zeta^3 - \zeta^5 + \zeta^7
+\]
+
+On a alors $G^2 = 4 - 4\zeta^4 = 8$.
+
+Par ailleurs, $G^p = \Frob_p(G) = \zeta^p - \zeta^{3p} - \zeta^{5p}
++ \zeta^{7p}$, donc $G^p = (-1)^{(p^2-1)/8} G$ (en considérant
+séparément les cas $p\equiv 1,7\pmod{8}$ et $p\equiv 3,5\pmod{8}$), et
+par conséquent $G^{p-1} = (-1)^{(p^2-1)/8}$.
+
+En écrivant $G^{p-1} = (G^2)^{(p-1)/2}$, on a donc prouvé
+$(-1)^{(p^2-1)/8} = 8^{(p-1)/2} = \Legendre{8}{p} = \Legendre{2}{p}$ ;
+cette égalité entre éléments de $\{\pm 1\}$ a lieu dans $\FF_{p^r}$
+donc dans $\ZZ$ : c'est ce qu'on voulait prouver.
+
+Signalons la variante suivante. L'élément $ζ+ζ^{-1}$ est,
+dans $𝐅_{p^r}$ une racine carré de $2$ car
+$(ζ+ζ^{-1})²=2+ζ²+{ζ²}^{-1}=2$. Il en résulte que $2$ est un carré
+dans $𝐅_p$ si et seulement si $ζ^p+ζ^{-p}=ζ+ζ^{-1}$. Cette condition
+ne dépend que de $±p$ modulo $8$ et on vérifie immédiatement quelles
+sont les valeurs pour lesquelles elle est satisfaite.
+\end{proof}
+
+\begin{remarque2}
+L'étude des nombres premiers $p$ pour lesquels $2$ est un \emph{cube}
+est plus délicate et s'insère naturellement dans la « théorie
+non abélienne du corps de classes » (ou « programme de Langlands »).
+On démontre que le nombre de solutions
+dans $𝐅_p$ de l'équation $x³=2$
+est $1+a_p$, où les $a_n$ sont les coefficients
+de la série formelle
+\[
+x∏_{n=1}^∞ \big((1-x^{6n})(1-x^{18n})\big)=∑^∞_{n=1} a_n x^n.
+\]
+% cf. nouveau livre de Katô p. 36. À déplacer ?
+\end{remarque2}
+
+\begin{remarques2}\label{remarque-periodicite-symbole-legendre}
+La loi de réciprocité quadratique et la formule complémentaire (ainsi
+que la formule \ref{formule-symbole-legendre} pour le cas $a=-1$)
+permettent de conclure que $\Legendre{a}{p}$, qui est évidemment une
+fonction périodique de $a$ à $p$ fixé, est aussi, ce qui n'était pas
+évident a priori, une fonction périodique de $p$ à $a$ fixé (au sens
+où il existe un entier $T$ ne dépendant que de $a$ tel que si $p,p'$
+sont premiers impairs et $p \equiv p' \pmod{T}$ alors $\Legendre{a}{p}
+= \Legendre{a}{p'}$) ; plus précisément, il admet pour période $T =
+4|a|$ (cela sera démontré en \ref{proprietes-symbole-jacobi}
+ci-dessous). Ceci peut inciter à vouloir donner un sens à
+$\Legendre{a}{n}$ dans des cas où $n$ n'est plus nécessairement
+premier, en appliquant cette périodicité (par exemple, puisque
+$\Legendre{3}{p} = +1$ pour tout premier $p \equiv 1 \pmod{12}$, on
+est tenté de convenir que $\Legendre{3}{25} = +1$ et $\Legendre{3}{85}
+= +1$ même si $25$ et $85$ ne sont pas premiers et que $3$ n'est même
+pas un carré dans $\ZZ/25\ZZ$ ni $\ZZ/85\ZZ$). Le symbole de Jacobi
+constitue une telle généralisation du symbole de Legendre :
+\end{remarques2}
+
+\subsection{Symboles de Jacobi et de Kronecker}
+
+\begin{definition2}\label{definition-symbole-jacobi}
+Pour tout $a \in \ZZ$ et tout $b \in \NN$ impair, on
+appelle \emph{symbole de Jacobi} de $a$ et $b$, et on note
+$\Legendre{a}{b}$, le symbole défini par $\Legendre{a}{b}
+= \Legendre{a}{p_1}\cdots \Legendre{a}{p_k}$ où $b = p_1\cdots p_k$
+avec $p_i$ des nombres premiers impairs, et où $\Legendre{a}{p_i}$
+désigne alors le symbole de
+Legendre (\ref{definition-symbole-legendre}).
+\end{definition2}
+
+\begin{proposition2}\label{proprietes-symbole-jacobi}
+Le symbole de Jacobi défini en \ref{definition-symbole-jacobi} a les
+propriétés suivantes :
+\begin{itemize}
+\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
+premiers entre eux.
+\item Pour tous $a,a',b \in \ZZ$ avec $b$ positif impair, on a
+$\Legendre{aa'}{b} = \Legendre{a}{b} \Legendre{a'}{b}$.
+\item Pour tous $a,b,b' \in \ZZ$ avec $b,b'$ positifs impairs, on a
+$\Legendre{a}{bb'} = \Legendre{a}{b} \Legendre{a}{b'}$.
+\item À $b$ positif impair fixé, la fonction $\Legendre{a}{b}$ est
+périodique admettant $b$ pour période.
+\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
+admettant $4|a|$ pour période, et même $2|a|$ si $a \equiv 1
+\pmod{4}$ et $|a|$ si $a \equiv 0 \pmod{4}$.
+\item Pour tout $b$ positif impair, on a $\Legendre{-1}{b} =
+(-1)^{(b-1)/2}$.
+\item Pour tout $b$ positif impair, on a $\Legendre{2}{b} =
+(-1)^{(b^2-1)/8}$.
+\item Pour tous $a,b$ positifs impairs, on a
+$\Legendre{a}{b} \Legendre{b}{a} = (-1)^{(a-1)(b-1)/4}$.
+\end{itemize}
+\end{proposition2}
+\begin{proof}
+Les deux premières propriétés découlent immédiatement des propriétés
+correspondantes du symbole de Legendre. La troisième propriété est
+une conséquence immédiate de la définition. La quatrième propriété
+(périodicité en $a$) découle de nouveau de la propriété correspondante
+du symbole de Legendre. La propriété suivante (périodicité en $b$)
+sera démontrée en dernier.
+
+Les formules $\Legendre{-1}{b} = (-1)^{(b-1)/2}$, $\Legendre{2}{b} =
+(-1)^{(b^2-1)/8}$ et $\Legendre{a}{b} \Legendre{b}{a} =
+(-1)^{(a-1)(b-1)/4}$ résultent des formules correspondantes pour le
+symbole de Legendre
+(\ref{formule-symbole-legendre}, \ref{formule-complementaire}
+et \ref{loi-reciprocite-quadratique}) et du fait que ces formules sont
+multiplicatives en $b$.
+
+Montrons enfin que $\Legendre{a}{b}$ est périodique en $b$ avec les
+périodes annoncées. Si $a$ est positif impair, on a $\Legendre{a}{b}
+= (-1)^{(a-1)(b-1)/4} \Legendre{b}{a}$ comme on vient de le voir, et
+le membre de droite admet $4a$ pour période ou même $2a$ si $a \equiv
+1 \pmod{4}$ ; si $a = -1$ alors $\Legendre{-1}{b}$ est périodique de
+période $4$ et on en déduit le résultat pour tout $a$ impair. Enfin,
+si $a = 2^v a'$ avec $a'$ impair, on a $\Legendre{a}{b}
+= \Legendre{2}{b}^v \Legendre{a'}{b}$. Pour $v=1$ (cas où $a \equiv
+2 \pmod{4}$), le premier facteur a pour période $8$ et le second admet
+la période $4|a'|$, donc le produit admet la période $8|a'| = 4|a|$ ;
+pour $v=2$, le premier facteur est constant et le second admet la
+période $4|a'|$ donc le produit admet la période $4|a'| = |a|$ ; et
+pour $v\geq 3$, le premier facteur admet la période $8$ et le second
+la période $4|a'|$, donc le produit admet la période $8|a'|$
+donc $|a|$.
+\end{proof}
+
+\begin{remarques2}
+\begin{itemize}
+\item Comme on l'a déjà illustré
+en \ref{remarque-periodicite-symbole-legendre} par l'exemple de
+$\Legendre{3}{25} = +1$ et $\Legendre{3}{85} = +1$, on peut très bien
+avoir $\Legendre{a}{b} = +1$ sans que $a$ soit un carré
+dans $\ZZ/b\ZZ$. En revanche, si $\Legendre{a}{b} = -1$ (avec $b$
+positif impair) alors $a$ n'est pas un carré dans $\ZZ/b\ZZ$ puisque
+$a$ n'est pas un carré modulo l'un des facteurs premiers de $b$.
+Voir cependant \ref{symbole-de-jacobi-et-corps-finis} ci-dessous.
+\item La formule \ref{formule-symbole-legendre} n'est pas valable en
+général pour le symbole de Jacobi, même si $a$ est effectivement un
+carré modulo $b$ (le nombre noté $p$
+en \ref{formule-symbole-legendre}) : par exemple, $\Legendre{11}{35} =
++1$, et de fait $11 \equiv 9^2 \pmod{35}$, pourtant
+$11^{(35-1)/2} \equiv 16 \pmod{35}$.
+\end{itemize}
+\end{remarques2}
+
+La proposition suivante est utile pour certains calculs, mais elle est
+vraie pour des raisons essentiellement triviales :
+\begin{proposition2}\label{symbole-de-jacobi-et-corps-finis}
+Soit $q$ une puissance d'un nombre premier $p$ impair, et $a \in \ZZ$
+non multiple de $p$. Alors $a$ est un carré dans $\FF_q$ si et
+seulement si $\Legendre{a}{q} = +1$ où $\Legendre{a}{q}$ désigne le
+symbole de Jacobi.
+\end{proposition2}
+\begin{proof}
+Écrivons $q = p^r$. Si $r$ est pair alors $\Legendre{a}{q}
+= \Legendre{a}{p}^2 = +1$, et $a$ est bien un carré dans $\FF_q$
+d'après \refext{Fin}{carres-extensions-corps-finis}. Si $r$ est impair alors
+$\Legendre{a}{q} = \Legendre{a}{p}^r = \Legendre{a}{p}$, et $a$ est un
+carré dans $\FF_q$ si et seulement s'il l'est dans $\FF_p$ de nouveau
+d'après \refext{Fin}{carres-extensions-corps-finis}.
+\end{proof}
+
+\begin{remarque2}
+On définit parfois une généralisation encore plus poussée des symboles
+de Legendre et de Jacobi : le \emph{symbole de Kronecker}
+$\Legendre{a}{b}$ défini pour tous $a,b\in\ZZ$. Celui-ci est défini
+en écrivant $b = u p_1\cdots p_k$ avec $u \in \{\pm 1\}$ et $p_i$ des
+nombres premiers (cette fois $p_i=2$ est admis), où $\Legendre{a}{p}$
+désigne le symbole de Legendre (\ref{definition-symbole-legendre}) si
+$p$ est premier impair, et de plus :
+\[\Legendre{a}{2} = \left\{
+\begin{array}{ll}
+0&\textrm{si $a$ est pair}\\
+(-1)^{(a^2-1)/8}&\textrm{si $a$ est impair}\\
+\end{array}
+\right.\]
+\[\Legendre{a}{-1} = \left\{
+\begin{array}{ll}
+1&\textrm{si $a\geq 0$}\\
+-1&\textrm{si $a<0$}\\
+\end{array}
+\right.\]
+et enfin
+\[\Legendre{a}{0} = \left\{
+\begin{array}{ll}
+1&\textrm{si $a = \pm 1$}\\
+0&\textrm{sinon}\\
+\end{array}
+\right.\]
+Le prix à payer pour une telle généralisation est principalement de
+perdre la périodicité de $\Legendre{a}{b}$ par rapport à $b$ lorsque
+$a \equiv -1 \pmod{4}$ (ainsi que la périodicité par rapport à $a$
+lorsque $b \leq 0$). En fait, le choix de $\Legendre{a}{2} =
+(-1)^{(a^2-1)/8}$ (pour $a$ impair) est quelque peu arbitraire, et le
+symbole de Kronecker ne possède pas le caractère naturel du symbole de
+Jacobi. Il vérifie néanmoins les propriétés suivantes dont la
+vérification est laissée au lecteur :
+\begin{itemize}
+\item On a $\Legendre{a}{b} = 0$ si et seulement si $a,b$ sont
+premiers entre eux.
+\item Pour tous $a,a',b \in \ZZ$, on a $\Legendre{aa'}{b}
+= \Legendre{a}{b} \Legendre{a'}{b}$.
+\item Pour tous $a,b,b' \in \ZZ$, on a $\Legendre{a}{bb'}
+= \Legendre{a}{b} \Legendre{a}{b'}$ sauf éventuellement si $a=-1$ et
+$bb'=0$.
+\item À $b>0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
+admettant $4b$ pour période, et même $b$ si $b \not\equiv 2 \pmod{4}$.
+\item À $a \neq 0$ fixé, la fonction $\Legendre{a}{b}$ est périodique
+admettant $4|a|$ pour période si $a \not\equiv -1 \pmod{4}$, et même
+$|a|$ si $a \equiv 0,1 \pmod{4}$.
+\end{itemize}
+\end{remarque2}
+
+
\section{Hypersurfaces diagonales ; réciprocité quadratique}
\subsection{Dualité dans les groupes abéliens finis}