From 6ba7cd4ec17b7ada30afd27444fc187d50a706ae Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Sun, 28 Sep 2014 22:40:04 +0200 Subject: Move workout file and give it a proper title. --- td2011-1.tex | 266 ----------------------------------------------------------- 1 file changed, 266 deletions(-) delete mode 100644 td2011-1.tex (limited to 'td2011-1.tex') diff --git a/td2011-1.tex b/td2011-1.tex deleted file mode 100644 index bfe7f8f..0000000 --- a/td2011-1.tex +++ /dev/null @@ -1,266 +0,0 @@ -%% 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} -- cgit v1.2.3