%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[10pt]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\makeatletter\relax\let\Square\@undefined\relax\makeatother
\usepackage{bbding}
\usepackage{url}
%
\newcommand{\limp}{\mathrel{\Rightarrow}}
\newcommand{\liff}{\mathrel{\Longleftrightarrow}}
\newcommand{\pgcd}{\operatorname{pgcd}}
\newcommand{\ppcm}{\operatorname{ppcm}}
\newcommand{\signe}{\operatorname{signe}}
\newcommand{\tee}{\mathbin{\top}}
\newcommand{\Frob}{\operatorname{Fr}}
\newcommand{\quadres}[2]{\Big(\frac{\strut #1}{\strut #2}\Big)}
\newcommand{\dothis}{\leavevmode\hbox to0pt{\hskip-\parindent\HandRight{}\hskip0ptplus1fil}}
\DeclareUnicodeCharacter{00A0}{~}
%
%
%
\begin{document}
\pretolerance=10000
\tolerance=8000

\textbf{Résidus et non-résidus quadratiques.}

On fixe provisoirement un entier $N \geq 1$.

On dit qu'un élément $a \in (\mathbb{Z}/N\mathbb{Z})^\times$ est un
\emph{résidu quadratique} lorsque $a$ est un carré modulo $N$,
c'est-à-dire lorsqu'il existe $b \in \mathbb{Z}/N\mathbb{Z}$ tel que
$a = b^2$.

\dothis On a nécessairement $b \in
(\mathbb{Z}/N\mathbb{Z})^\times$ dans ce cas : pourquoi ?

A contrario, si $a \in (\mathbb{Z}/N\mathbb{Z})^\times$ ne vérifie pas
cette condition, on dit que $a$ est un \emph{non-résidu quadratique}.

{\footnotesize Exemple : Les carrés de $\bar 0,\bar 1,\bar 2,\bar
  3,\bar 4,\bar 5,\bar 6,\bar 7,\bar 8$ modulo $9$ sont respectivement
  $\bar 0,\bar 1,\bar 4,\bar 0,\bar 7,\bar 7,\bar 0,\bar 4,\bar 1$ ;
  par conséquent, on dira que $\bar 1,\bar 4,\bar 7$ sont des résidus
  quadratiques modulo $9$, et que $\bar 2,\bar 5,\bar 8$ sont des
  non-résidus quadratiques (quant à $\bar 0,\bar 3,\bar 6$, ils sont
  non-inversibles et ne sont ni qualifiés de résidus quadratiques ni
  de non-résidus quadratiques).\par}

\medbreak

\textbf{Le symbole de Legendre.}

Si $p$ est un nombre premier impair et $a \in \mathbb{Z}$, on définit
le \emph{symbole de Legendre} $\quadres{a}{p}$ (attention, il ne
s'agit pas du quotient $a/b$, c'est juste une notation malheureuse)
comme l'entier valant :
\begin{itemize}
\item[$\bullet$]$+1$ si la classe de $a$ modulo $p$ est un résidu
  quadratique,
\item[$\bullet$]$-1$ si la classe de $a$ modulo $p$ est un non-résidu
  quadratique, et
\item[$\bullet$]$0$ si la classe de $a$ modulo $p$ est nulle
  (c'est-à-dire lorsque $p|a$).
\end{itemize}

{\footnotesize Exemple : Modulo $p=7$, les résidus quadratiques sont
  $\bar 1 = \bar 1^2$, $\bar 2 = \bar 3^2$ et $\bar 4 = \bar 2^2$, et
  les nonrésidus quadratiques sont $\bar 3, \bar 5, \bar 6$.  Par
  conséquent, on a $\quadres{1}{7} = \quadres{2}{7} = \quadres{4}{7} =
  \quadres{8}{7} = \quadres{9}{7} = +1$ et $\quadres{3}{7} =
  \quadres{5}{7} = \quadres{6}{7} = \quadres{10}{7} = \quadres{-1}{7}
  = -1$, et bien sûr $\quadres{0}{7} = \quadres{7}{7} =
  \quadres{-14}{7} = 0$.\par}

\smallbreak

\dothis Calculer le symbole de Legendre $\quadres{a}{11}$ pour
tout $a$ entre $0$ et $10$.

\medbreak

\textbf{Critère d'Euler.}

On suppose que $p$ est premier impair.

\dothis Quelles sont toutes les solutions de l'équation $c^2 = 1$
dans $\mathbb{Z}/p\mathbb{Z}$ ?

\dothis Si $a \in (\mathbb{Z}/p\mathbb{Z})^\times$, que vaut
$(a^{(p-1)/2})^2$ dans $\mathbb{Z}/p\mathbb{Z}$ ?  En déduire que si
$a$ est un entier non multiple de $p$, alors $a^{(p-1)/2}$ est
toujours congru soit à $+1$ soit à $-1$ modulo $p$.  Et que dire si
$a$ est multiple de $p$ ?

\dothis Si $b \in (\mathbb{Z}/p\mathbb{Z})^\times$, que vaut
$(b^2)^{(p-1)/2}$ dans $\mathbb{Z}/p\mathbb{Z}$ ?  En déduire que si
$a$ est un résidu quadratique modulo $p$, alors $a^{(p-1)/2}$ est
congru à $+1$ modulo $p$.

\dothis Si $a$ est un résidu quadratique modulo $p$, combien y
a-t-il de $b \in \mathbb{Z}/p\mathbb{Z}$ tels que $a = b^2$ ?  En
déduire que le nombre de résidus quadratiques dans
$\mathbb{Z}/p\mathbb{Z}$ vaut \emph{au plus} $(p-1)/2$.

\dothis Quel est le degré du polynôme $t^{(p-1)/2} \in
\mathbb{F}_p[t]$ ?  Combien de fois au maximum peut-il prendre la
valeur $+1$ ou bien la valeur $-1$ ?

\dothis Déduire des questions précédentes que
\[
\quadres{a}{p} \equiv a^{(p-1)/2} \pmod{p}
\tag{*}
\]
pour tout $p$ premier impair et $a \in \mathbb{Z}$ (\emph{critère
  d'Euler}).

\dothis Remarquer que $\quadres{-1}{p} = (-1)^{(p-1)/2}$.  En déduire
une condition nécessaire et suffisante simple sur un nombre premier
impair $p$ permettant de savoir si $-1$ est ou non un résidu
quadratique modulo $p$.  (Discuter selon la congruence modulo $4$.)

\dothis Montrer par ailleurs que le symbole de Legendre est
multiplicatif :
\[
\quadres{ab}{p} = \quadres{a}{p}\,\quadres{b}{p}
\]
(pour tous $a,b \in \mathbb{Z}$, à $p$ premier impair fixé).

\medbreak

\textbf{La « formule complémentaire ».}

On appelle « formule complémentaire » l'affirmation
\[
\quadres{2}{p} = (-1)^{(p^2-1)/8}
\]
(où $p$ est, de nouveau, un nombre premier impair).

\dothis Réexprimer la formule complémentaire comme une affirmation
indiquant si $2$ est un résidu quadratique ou non, en fonction de la
congruence de $p$ modulo $8$.

\dothis En admettant la formule complémentaire, écrire une affirmation
indiquant si $-2$ est un résidu quadratique ou non, en fonction de la
congruence de $p$ modulo $8$.

\smallbreak

\emph{On se propose maintenant de démontrer la formule
  complémentaire.}

Rermarquons que chaque élément de $\mathbb{Z}/p\mathbb{Z}$ est congru
à un et un seul des entiers $-\frac{p-1}{2},\ldots,
-2,-1,0,1,2,3,\ldots, \frac{p-3}{2}, \frac{p-1}{2}$ (autrement dit, il
s'agit d'un ensemble de représentants des classes de congruence
modulo $p$ --- différent de l'ensemble $0,1,2,\ldots,p-1$ qu'on
utilise plus souvent, mais tout aussi valable).

On introduit la terminologie provisoire suivante : un élément de
$(\mathbb{Z}/p\mathbb{Z})^\times$ (ou un entier non multiple de $p$)
sera dit \emph{pseudopositif} lorsqu'il est congru modulo $p$ à l'un
des entiers $1,2,3,\ldots, \frac{p-3}{2}, \frac{p-1}{2}$, et
\emph{pseudonégatif} lorsqu'il est congru modulo $p$ à l'un des
entiers $-1,-2,\ldots, -\frac{p-1}{2}$.  (Par exemple, modulo $11$,
les nombres $1$, $2$ et $5$ sont pseudopositifs, en revanche $6$ est
pseudonégatif puisque c'est $-5$, et $10$ est pseudonégatif puisque
c'est $-1$.)

On appelle $\mathscr{P} = \prod_{i=1}^{(p-1)/2} \bar\imath$ le produit
des éléments pseudopositifs de $(\mathbb{Z}/p\mathbb{Z})^\times$ (cela
vaut $((p-1)/2)!$ modulo $p$, mais peu importe).

\dothis Remarquer que $\prod_{i=1}^{(p-1)/2} (2\bar\imath) =
2^{(p-1)/2} \mathscr{P}$ (modulo $p$).

\dothis Pour quels $i$ entre $1$ et $(p-1)/2$ l'élément
$2\bar\imath$ de $\mathbb{Z}/p\mathbb{Z}$ est-il pseudopositif
(resp. pseudonégatif) ?  (Attention, tout se passe modulo $p$.)

Pour $i$ allant de $1$ à $(p-1)/2$, on écrit $2\bar\imath = \pm
\bar\jmath$, où le signe est choisi de sorte que $\bar\jmath$ soit
pseudopositif.

\dothis Montrer que $\bar\jmath$ prendra une et une seule fois
chaque valeur pseudopositive.

\dothis Montrer que $\prod_{i=1}^{(p-1)/2} (2\bar\imath) = (-1)^A
\mathscr{P}$ où $A$ est le nombre d'entiers entre $\frac{p}{4}$ et
$\frac{p}{2}$.

\dothis En discutant séparément selon la valeur possible de $p$
modulo $8$, montrer que $(-1)^A = (-1)^{(p^2-1)/8}$.

\dothis En déduire la formule complémentaire.

\medbreak

\textbf{La loi de réciprocité quadratique.}

On appelle « loi de réciprocité quadratique » l'affirmation
\[
\quadres{q}{p} \, \quadres{p}{q} = (-1)^{(p-1)(q-1)/4}
\]
où $p$ et $q$ sont deux nombres premiers impairs.

\dothis Montrer que la loi de réciprocité quadratique est
équivalente à l'affirmation suivante (pour $p$ et $q$ deux nombres
premiers impairs) :
\begin{itemize}
\item si l'un des nombres $p$ ou $q$ est congru à $1$ modulo $4$,
  alors $\quadres{q}{p} = \quadres{p}{q}$,
\item si les nombres $p$ et $q$ sont tous les deux congrus à $3$
  modulo $4$, alors on a : $\quadres{q}{p} = - \quadres{p}{q}$.
\end{itemize}

\smallbreak

On \emph{admet} maintenant la loi de réciprocité quadratique.

\dothis Écrire une affirmation indiquant si $5$ est un résidu
quadratique ou non mod $p$, en fonction de la congruence de $p$ modulo $5$.
Écrire une affirmation indiquant si $3$ est un résidu quadratique ou
non mod $p$, en fonction de la congruence de $p$ modulo $12$.  Écrire une
affirmation indiquant si $-5$ est un résidu quadratique ou non mod $p$, en
fonction de la congruence de $p$ modulo $20$.  Écrire une affirmation
indiquant si $6$ est un résidu quadratique ou non mod $p$, en fonction de la
congruence de $p$ modulo $24$.

\dothis Le nombre $97$ est-il un résidu quadratique modulo $103$ ?
(Les nombres $97$ et $103$ sont tous les deux premiers.)

\medbreak

\textbf{Quelques chinoiseries pour finir.}

(Cette partie est indépendante de la précédente.)

On suppose que $p$ et $q$ sont deux nombres premiers impairs distincts.

\dothis Combien y a-t-il de solutions de l'équation $c^2 = 1$
dans $\mathbb{Z}/pq\mathbb{Z}$ ?

\dothis À titre d'exemple, résoudre $c^2 = 1$ dans
$\mathbb{Z}/143\mathbb{Z}$.

\dothis Combien y a-t-il de résidus quadratiques modulo $pq$ ?

\dothis Le nombre $-1$ est-il un résidu quadratique modulo
$303\,386\,723 = 17\,417 \times 17\,419$ (sachant que les nombres
$17417$ et $17419$ sont tous les deux premiers) ?

%
%
%
\end{document}