summaryrefslogtreecommitdiffstats
path: root/td2011-1.tex
blob: bfe7f8f7ff15d101740f4204f8c42c2268997724 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
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 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}