%% 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}