From 57879cb8b96dce286907779e3cfa6720d6c07062 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 24 Oct 2011 17:35:44 +0200 Subject: Workout for 2011-10-25. --- td2011-1.tex | 266 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 266 insertions(+) create mode 100644 td2011-1.tex 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} -- cgit v1.2.3