1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
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}
|
