Workout for 2011-10-25.

1 files changed, 266 insertions, 0 deletions

diff --git a/td2011-1.tex b/td2011-1.tex
new file mode 100644
index 0000000..735cf22
--- /dev/null
+++ b/td2011-1.tex
@@ -0,0 +1,266 @@
+%% 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, en fonction de la congruence de $p$ modulo $5$.
+Écrire une affirmation indiquant si $3$ est un résidu quadratique ou
+non, en fonction de la congruence de $p$ modulo $12$.  Écrire une
+affirmation indiquant si $-5$ est un résidu quadratique ou non, en
+fonction de la congruence de $p$ modulo $20$.  Écrire une affirmation
+indiquant si $6$ est un résidu quadratique ou non, 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.
+
+\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}