diff options
| -rw-r--r-- | exercices.tex | 170 |
1 files changed, 170 insertions, 0 deletions
diff --git a/exercices.tex b/exercices.tex new file mode 100644 index 0000000..243bf28 --- /dev/null +++ b/exercices.tex @@ -0,0 +1,170 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt]{article} +\usepackage[francais]{babel} +\usepackage[latin1]{inputenc} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\exercice{% +\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\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}} +% +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} +% +% +% +\begin{document} +\ifcorrige +\title{INFMDI720\\Exercices --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}} +\else +\title{INFMDI720\\Exercices\\{\normalsize Rappels mathématiques pour la cryptographie}} +\fi +\author{} +\date{} +\maketitle +\pretolerance=10000 +\tolerance=8000 + +% +% +% + +\exercice + +(A) Quel entier entre $0$ et $100$ est congru à $19$ modulo $13$ et à +$13$ modulo $19$ ? + +\begin{corrige} +(A) Commençons par trouver un entier qui convient. On pourrait se + rendre compte que $19+13 = 32$ convient pour des raisons de + symétrie. Pour procéder de façon plus systématique, cherchons une + relation de Bézout entre $19$ et $13$, qui sont visiblement premiers + entre eux (et ceci va de toute façon le confirmer) : on a $19 = 1\times 13 + + 6$ puis $13 = 2\times 6 + 1$ donc le pgcd est bien $1$, et on a $1 = + 13 - 2\times 6 = 3\times 13 - 2\times 19$. Ainsi, d'après un + résultat du cours (version « effective » du théorème chinois), un + nombre congru à $19$ (soit $6$) modulo $13$ et à $13$ modulo $19$ + est donné par $3 \times 13 \times 13 - 2 \times 19 \times 6$ : ceci + vaut $279$, mais pour simplifier les calculs on pouvait calculer + $3\times 13 \equiv 1 \pmod{19}$ et $-2 \times 6 \equiv 1 \pmod{13}$, + donc il reste $13 + 19 = 32$. En tout état de cause, comme $13$ et + $19$ sont premiers entre eux, les nombres congrus à $x$ modulo $13$ + et à $y$ modulo $19$, quels que soient $x$ et $y$ entiers, forment + une unique classe de congruence modulo $13 \times 19 = 247$ (qu'il + n'était pas vraiment nécessaire de calculer, seul importe que ce + soit $>100$, ce qui est évident), donc dès qu'on a trouvé un nombre + vérifiant les congruences demandées (en l'occurrence $32$), on sait + que les autres sont les nombres qui lui sont congrus modulo $13 + \times 19$, et en particulier il n'y en a pas d'autre entre $0$ + et $100$. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(B) Quel entier à trois chiffres en base $10$ se termine par $23$ et +est multiple de $19$ ? + +\begin{corrige} +(B) Se terminer par $23$ en base $10$ signifie être congru à $23$ + modulo $100$. Cherchons une relation de Bézout entre $100$ et $19$ + qui sont premiers entre eux : on a $100 = 5\times 19 + 5$ et $19 = + 3\times 5 + 4$ et $5 = 1\times 4 + 1$ donc $1 = 5 - 4 = 4 \times 5 - 19 = 4 + \times 100 - 21 \times 19$. Ainsi, d'après un résultat du cours + (version « effective » du théorème chinois), un nombre congru à $23$ + modulo $100$ et à $0$ modulo $19$ (i.e., divisible par $19$) est + donné par $- 21 \times 19 \times 23$ : ceci vaut $-9177$, mais pour + simplifier les calculs on pouvait calculer $-21\times 23 \equiv -83 + \equiv 17 \pmod{100}$ et ainsi $- 21 \times 19 \times 23 \equiv 17 + \times 19 = 323 \pmod{1900}$. Le nombre $323$ répond aux conditions + demandées, et comme tout les entiers congrus à $23$ modulo $100$ et + à $0$ modulo $19$ forment une unique classe de congruence + modulo $1900$, on a trouvé le seul nombre à trois chiffres. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(C) Quel entier entre $0$ et $100$ est congru respectivement à +$1,2,3,4$ modulo $2,3,5,7$ ? (C'est-à-dire : congru à $1$ modulo $2$, +et à $2$ modulo $3$, et à $3$ modulo $5$, et à $4$ modulo $7$.) + +\begin{corrige} +(C) Les nombres $2,3,5,7$ sont premiers entre eux deux à deux. + Commençons par trouver des solutions à deux congruences + simultanées : comme les nombres sont assez petits, il est plus + simple de le faire par tâtonnement : par exemple, $5$ est congru à + $1$ modulo $2$ et à $2$ modulo $3$, cela se trouve immédiatement en + parcourant les entiers de $0$ à $5$ ou plus astucieusement ceux qui + vérifient une des deux congruences pour chercher ceux qui vérifient + l'autre. Comme on va vouloir mettre ensuite ensemble deux + congruences de ce genre, il vaut mieux les trouver de même taille + et, si possible, vérifiant une relation de Bézout simple : le plus + économique est donc de mettre $2$ avec $7$ et $3$ avec $5$, ce qui a + le bon goût que $1\times 15 - 1\times 14 = 1$ est une relation de Bézout évidente + entre $3\times 5$ et $2\times 7$. Par tâtonnement, on trouve que + $11$ (et exactement les nombres de sa classe modulo $14$) est congru + à $1$ modulo $2$ et à $4$ modulo $7$, et que $8$ (et exactement les + nombres de sa classe modulo $15$) est congru à $2$ modulo $3$ et à + $3$ modulo $5$. Avec la relation de Bézout $1\times 15 - 1\times 14 + = 1$, toujours en appliquant la même version « effective » du + théorème chinois, on voit que les entiers vérifiant les quatre + congruences demandées sont exactement la classe de $1\times 15\times + 11 - 1\times 14\times 8 = 53$ modulo $15 \times 14 = 210$, donc le + seul entre $0$ et $100$ est $53$. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(D) Déterminer tous les entiers entre $0$ et $2009$ congrus à $1$ +modulo chacun des nombres $7$, $11$ et $13$. (C'est-à-dire : congrus +à $1$ modulo $7$, et à $1$ modulo $11$, et à $1$ modulo $13$.) +(Indication : y-t-il un nombre évident qui répond à cette condition ?) + +\begin{corrige} +(D) Comme le suggère l'indication, il y a un nombre évident congru à + $1$ modulo $7$ et $11$ et $13$ à la fois, c'est $1$ lui-même. Le + théorème chinois assure que, comme $7$ et $11$ et $13$ sont premiers + entre eux deux à deux, les entiers congrus à $1$ modulo chacun d'eux + forment une classe de congruence modulo $7 \times 11 \times 13 = + 1001$. Les nombres entre $0$ et $2009$ vérifiant les congruences + demandées sont donc : $1$, $1002$ et $2003$. +\end{corrige} + +\ifcorrige\medbreak\else\relax\fi + +(E) Déterminer tous les entiers entre $0$ et $100\,000$ congrus à +$192$ modulo $300$ et à $169$ modulo $305$. + +\begin{corrige} +(E) Un entier congru à $192$ modulo $300$ est (comme $5|300$) congru à + $192 \equiv 2$ modulo $5$, et un entier congru à $169$ modulo $305$ + est (comme $5|305$) congru à $169 \equiv 4$ modulo $5$. Comme $2 + \not\equiv 4 \pmod{5}$, il n'existe \emph{aucun} entier vérifiant + les deux congruences demandées. +\end{corrige} + +% +% +% +\end{document} |