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}