summaryrefslogtreecommitdiffstats
path: root/controle-20091124.tex
blob: bbc62dc67d9173896a333dc5f39f4c8728ce2ce0 (plain)
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
%% 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\\Contrôle de connaissance --- Corrigé\\{\normalsize Rappels mathématiques pour la cryptographie}}
\else
\title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}}
\fi
\author{}
\date{24 novembre 2009}
\maketitle
\pretolerance=10000
\tolerance=8000

\vskip1truein\relax

\textbf{Consignes :}

Les exercices sont complètement indépendants.  Ils pourront être
traités dans un ordre quelconque, mais on demande de faire apparaître
de façon très visible dans les copies où commence chaque exercice.

À l'intérieur d'un exercice donné (sauf l'exercice 3), les parties
A,B,C..., sont encore essentiellement indépendantes, mais comme elles
peuvent se ressembler et s'éclairer les unes les autres il est
recommandé de les traiter dans l'ordre.  Les questions
1,2,3... dépendent les unes des autres.

Le sujet étant volontairement trop long pour le temps imparti, il ne
sera pas nécessaire de traiter tous les exercices pour avoir le
maximum des points.  Il est suggéré de prendre le temps de tous les
lire, pour bien choisir ceux que l'on traitera.

Il n'est pas nécessaire de faire des réponses longues.

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, livres) est autorisé.

L'usage des calculatrices électroniques est interdit.  (Certains
exercices peuvent apparaître calculatoires, mais les calculs sont
toujours faisables à la main en un temps raisonnable, parfois au prix
de quelques astuces.)

Durée : 1h30

\newpage

%
%
%

\exercice

(A) (1) À quoi est congru $10^n$ modulo $9$ (en fonction
éventuellement de l'entier naturel $n$) ?  (2) En déduire une
démonstration de l'affirmation suivante : un entier naturel écrit en
décimal (=base $10$) est congru modulo $9$ à la somme de ses chiffres.
Comment faire pour calculer très simplement le reste de la division
euclidienne par $9$ d'un entier naturel écrit en décimal ?
(3) Montrer que la multiplication suivante est erronée :
$745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,507\,306\,660$.

\begin{corrige}
(A) (1) On a $10 \equiv 1 \pmod{9}$ donc $10^n \equiv 1^n \equiv
  1\pmod{9}$.  (2) Si $A = \sum_{i=0}^{+\infty} a_i\, 10^i$ (avec $a_i
  \in \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier
  naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} a_i \pmod{9}$
  puisque $10^i \equiv 1$ comme on vient de le voir : on a bien montré
  que $A$ est congru modulo $9$ à la somme $\sum_{i=0}^{+\infty} a_i$
  de ses chiffres décimaux.  Pour calculer le reste de la division
  euclidienne par $9$ d'un entier naturel $A$, il suffit donc de
  calculer celui de la somme de ses chiffres décimaux (ce qui peut se
  faire en itérant l'opération « somme des chiffres décimaux » jusqu'à
  obtenir un résultat à un chiffre, et remplacer $9$ par $0$ à la fin
  si nécessaire).  Remarquons qu'on peut simplifier certaines choses :
  par exemple, ignorer les $9$ dans l'écriture décimale, et remplacer
  les $8$ par des $-1$, et évidemment remplacer un nombre par la somme
  de ses chiffres décimaux à n'importe quelle étape du calcul.

\leavevmode\hphantom{(A)} (3) En appliquant ce procédé, on voit que
$745\,330\,964 \equiv\penalty-100 7+4+5+\penalty0 3+3+\penalty0 6+4
=\penalty0 32 \equiv 5 \pmod{9}$, que $390\,158\,565
\equiv\penalty-100 3+\penalty0 1+5+8+\penalty0 5+6+5 =\penalty0 33
\equiv 6 \pmod{9}$ et que $290\,797\,259\,507\,306\,660
\equiv\penalty-100 2+\penalty0 7+7+\penalty0 2+5+\penalty0
5+7+\penalty0 3+6+\penalty0 6+6 = 56 \equiv 2 \pmod{9}$.  Comme
$5\times 6 \equiv 3 \not\equiv 2 \pmod{9}$, cette « preuve par $9$ »
montre que la multiplication proposée est erronée.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(B) (1) À quoi est congru $10^n$ modulo $11$ (en fonction
éventuellement de l'entier naturel $n$) ?  (Remarque : le nombre $10$
peut s'écrire d'une manière très simple modulo $11$...)  (2) Comment
faire pour calculer très simplement le reste de la division
euclidienne par $11$ d'un entier naturel écrit en décimal ?
(3) Montrer que la multiplication suivante est encore erronée :
$745\,330\,964 \times 390\,158\,565 = 290\,797\,259\,517\,306\,660$.

\begin{corrige}
(B) (1) On a $10 \equiv -1 \pmod{11}$ donc $10^n \equiv (-1)^n \equiv
  1\pmod{11}$, c'est-à-dire concrètement que $10^n$ vaut $+1$ ou $-1$
  modulo $11$ selon que $n$ est respectivement pair ou impair.  (2) Si
  $A = \sum_{i=0}^{+\infty} a_i\, 10^i$ (avec $a_i \in
  \{0,1,2,\ldots,9\}$) est l'écriture en base $10$ d'un entier
  naturel $A$, alors $A \equiv \sum_{i=0}^{+\infty} (-1)^i a_i
  \pmod{11}$ puisque $10^i \equiv (-1)^i$ comme on vient de le voir :
  on a bien montré que $A$ est congru modulo $11$ à la somme
  \emph{alternée} $\sum_{i=0}^{+\infty} (-1)^i a_i$ de ses chiffres
  décimaux, c'est-à-dire en comptant avec un $+$ tous les chiffres de
  puissance paire (unités, centaines, dizaines de milliers...) et avec
  un $-$ tous les chiffres de puissance impaire (dizaines, milliers,
  etc.).  Pour calculer le reste de la division euclidienne par $11$
  d'un entier naturel $A$, il suffit donc de calculer celui de la
  somme alternée de ses chiffres décimaux (ce qui peut se faire en
  itérant l'opération « somme alternée des chiffres décimaux », en
  n'oubliant pas les signes, jusqu'à obtenir un résultat entre $-9$ et
  $9$, et ajouter $11$ à la fin si nécessaire pour obtenir un reste
  entre $0$ et $10$ inclus).

\leavevmode\hphantom{(B)} (3) En appliquant ce procédé, on voit que
$745\,330\,964 \equiv\penalty-100 7-4+5-\penalty0 3+3+\penalty0 9-6+4
=\penalty0 15 \equiv 4 \pmod{11}$, que $390\,158\,565
\equiv\penalty-100 3-9-\penalty0 1+5-8+\penalty0 5-6+5 =\penalty0 -6
\equiv 5 \pmod{11}$ et que $290\,797\,259\,517\,306\,660
\equiv\penalty-100 -2+9+\penalty0 7-9+7-\penalty0 2+5-9+\penalty0
5-1+7-\penalty0 3-6+\penalty0 6-6 =\penalty0 8 \pmod{11}$.  Comme
$4\times 5 \equiv\penalty0 9 \not\equiv 8 \pmod{11}$, cette « preuve
  par $11$ » montre que la multiplication proposée est erronée.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(C) (1) À quoi est congru $10^n$ modulo $7$, selon la valeur de $n$ ?
(2) Proposer une méthode (moins simple que celles données en A et B,
mais néanmoins plus économique que de poser la division) permettant de
calculer le reste de la division euclidienne par $7$ d'un entier
naturel écrit en décimal.  (On cherchera à se limiter à des additions
et des multiplications par $\pm 1, \pm 2, \pm 3$.)  (3) Montrer que le
calcul suivant est erroné : $3^{31} = 617\,673\,693\,283\,947$.

\begin{corrige}
(C) (1) Remarquons tout d'abord que $10 \equiv 3 \pmod{7}$.  On peut
dresser de proche en proche la table suivante des puissances de $10$
modulo $7$ :

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c}
$i$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline
$10^i$&$1$&$3$&$2$&$-1$&$-3$&$-2$\\
\end{tabular}
\end{center}

\noindent (On a représenté $6$, $4$ et $5$ modulo $7$ par $-1$, $-3$
et $-2$ respectivement, de façon à rendre les calculs plus faciles.)
Le fait (qu'on trouve ensuite) que $10^6 \equiv 1 \pmod{7}$ était
prévu par le petit théorème de Fermat (et le fait qu'on n'ait pas
trouvé $1$ plus tôt signifie que $10 \equiv 3$ est primitif
modulo $7$).  De façon plus générale, $10^{6k} \equiv 1 \pmod{7}$ donc
$10^{6k+i} \equiv 10^i \pmod{7}$ : ainsi, dans la table ci-dessus,
l'indice $i$ peut se lire modulo $6$.

\leavevmode\hphantom{(C)} (2) D'après ce qu'on vient d'expliquer, un
entier naturel $A = \sum_{i=0}^{+\infty} a_i\, 10^i$ (écrit en décimal)
est congru modulo $7$ à la somme de ses chiffres décimaux $a_i$ chacun
multiplié par une valeur dans $\{\pm 1, \pm 2, \pm 3\}$ donnée (en
fonction de $i$ modulo $6$) par la table ci-dessus : c'est-à-dire $a_0
+\penalty100 3 \times a_1 +\penalty0 2 \times a_2 -\penalty0 a_3
-\penalty0 3\times a_4 -\penalty0 2 \times a_5 +\penalty0 a_6
+\penalty0 3 \times a_7 + \cdots$.  Pour simplifier les calculs
ultérieurs, il peut être astucieux de précalculer les multiplications
par tous les chiffres décimaux possibles, c'est-à-dire de dresser le
tableau des valeurs de $a_i \times 10^i$ modulo $7$ en fonction de
$a_i$ et de $i$ :

\begin{center}
\footnotesize
\begin{tabular}{r|c|c|c|c|c|c}
$a_i\downarrow$\textbackslash $i\rightarrow$&$0$&$1$&$2$&$3$&$4$&$5$\\\hline
$0$\rlap{, $7$}\hphantom{\textbackslash $i\rightarrow$}&$0$&$0$&$0$&$0$&$0$&$0$\\
$1$\rlap{, $8$}\hphantom{\textbackslash $i\rightarrow$}&$1$&$3$&$2$&$6$&$4$&$5$\\
$2$\rlap{, $9$}\hphantom{\textbackslash $i\rightarrow$}&$2$&$6$&$4$&$5$&$1$&$3$\\
$3$\hphantom{\textbackslash $i\rightarrow$}&$3$&$2$&$6$&$4$&$5$&$1$\\
$4$\hphantom{\textbackslash $i\rightarrow$}&$4$&$5$&$1$&$3$&$2$&$6$\\
$5$\hphantom{\textbackslash $i\rightarrow$}&$5$&$1$&$3$&$2$&$6$&$4$\\
$6$\hphantom{\textbackslash $i\rightarrow$}&$6$&$4$&$5$&$1$&$3$&$2$\\
\end{tabular}
\end{center}

\noindent Avec ce tableau, pour calculer la classe modulo $7$ de $A =
\sum_{i=0}^{+\infty} a_i\, 10^i$, il suffit de sommer modulo $7$ les valeurs des
cases de chaque chiffre (la ligne étant déterminée par la valeur $a_i$
du chiffre décimal en question, et la colonne par l'exposant $i$
modulo $6$ de la puissance de $10$ utilisée).  Il s'agit simplement
d'une façon de regrouper une fois pour toutes le calcul des
multiplications par $\pm 1, \pm 2, \pm 3$, le calcul étant toujours le
même.  Pour être encore plus efficace, on peut d'ailleurs remplir le
tableau de façon « paresseuse », c'est-à-dire en ne calculant le
contenu des cases que lorsqu'on en a besoin.

\leavevmode\hphantom{(C)} (3) En appliquant ce procédé, on voit qu'on
a $617\,673\,693\,283\,947 \equiv\penalty-100 2\times 6 +\penalty1000
3\times 1 +\penalty1000 7 -\penalty0 2\times 6 -\penalty1000 3\times 7
-\penalty1000 3 +\penalty0 2\times 6 +\penalty1000 3\times 9
+\penalty1000 3 -\penalty0 2\times 2 -\penalty1000 3\times 8
-\penalty1000 3 +\penalty0 2\times 9 +\penalty1000 3\times 4
+\penalty1000 7 =\penalty-100 34 \equiv 6 \pmod{7}$ ou, en utilisant
directement le tableau ci-dessus, $\equiv 5 + 3 + 0 +\penalty0 2 + 0 +
4 +\penalty0 5 + 6 + 3 +\penalty0 3 + 4 + 4 +\penalty0 4 + 5 + 0
=\penalty-100 48 \equiv 6 \pmod{7}$.  Mais d'autre part $3^{31}$ est,
modulo $7$, congru à ($10^{31}$ donc à) $3$ puisque $31 \equiv 1 \pmod
6$ (ou si on veut, $3^{31} \equiv 3^{5\times 6 + 1} \equiv 3 \pmod{7}$
puisque $3^6 \equiv 1 \pmod{7}$).  Comme $6 \not\equiv 3$, le nombre
proposé n'est pas la valeur correcte de $3^{31}$.
\end{corrige}

%
%
%

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

%
%
%

\exercice

\textit{(Les nombres $101$ et $401$ sont premiers.)}

(1) Que vaut $\varphi(40\,501)$ ?

(2) Quel est l'inverse de $3$ dans $\mathbb{Z}/40\,000\mathbb{Z}$ ?
On note $s$ un entier naturel qui le représente.

(Il n'est pas nécessaire d'avoir trouvé la valeur numérique de $s$
pour pouvoir répondre aux questions suivantes.)

(3) Montrer l'affirmation suivante : si $n$ est premier avec
$40\,501$, alors $(n^3)^s \equiv n \pmod{40\,501}$.

(4) Que vaut $8^s$ modulo $40\,501$ ?

\begin{corrige}
(1) On a $40\,501 = 101\times 401$ donc $\varphi(40\,501) = 100\times
  400 = 40\,000$.

(2) Cherchons une relation de Bézout entre $3$ et $40\,000$ : on a
  $40\,000 = 13\,333 \times 3 + 1$ donc $1 = 40\,000 - 13\,333\times
  3$.  Ceci montre que $3$ est inversible d'inverse $-13\,333 \equiv
  26\,667 \pmod{40\,000}$ dans $\mathbb{Z}/40\,000\mathbb{Z}$.  Disons
  donc $s = 26\,667$.

(3) Si $n$ est premier avec $40\,501$, on sait que
  $n^{\varphi(40\,501)} \equiv 1 \pmod{40\,501}$ (théorème d'Euler),
  c'est-à-dire $n^{40\,000} \equiv 1 \pmod{40\,501}$, et bien sûr
  $n^{40\,000\,k} \equiv 1 \pmod{40\,501}$ pour tout naturel $k$.  Or
  $3s \equiv 1 \pmod{40\,000}$, c'est-à-dire $3s = 40\,000\,k + 1$
  pour un certain $k$ (en l'occurrence $k=2$ avec notre choix $s =
  26\,667$, mais peu importe).  On a donc $(n^3)^s = n^{3s} =
  n^{40\,000\,k + 1} = n^{40\,000\,k}\cdot n^1 \equiv n
  \pmod{40\,501}$.

(4) En prenant $n=2$ dans la question précédente, on a montré $8^s
  \equiv 2 \pmod{40\,501}$.
\end{corrige}

%
%
%

\exercice

(A) (1) Montrer que le polynôme $t^2 + t - 1 \in \mathbb{F}_3[t]$ est
irréductible.  (2) En déduire des tables d'opération du corps
$\mathbb{F}_9$ à $9$ éléments.  (3) Quels en sont les éléments
primitifs ?

\begin{corrige}
(A) (1) On peut par exemple remarquer que le polynôme $f = t^2 + t - 1
  \penalty0 \in \mathbb{F}_3[t]$ n'a pas de racine dans $\mathbb{F}_3$ (car
  $f(0) = -1$, $f(1) = 1$ et $f(-1) = -1$), ce qui interdit qu'il
  possède une factorisation non-triviale (car si $f = f_1 f_2$ avec
  $f_1,f_2$ de degré $<2$, ils seront chacun de degré $1$, donc ils
  auront nécessairement des racines).  On peut aussi préférer
  appliquer le critère de Rabin : d'une part (a) $f$ divise $t^9 - t$
  car $t^2 \equiv -t + 1 \pmod{f}$ donc $t^3 \equiv -t^2 + t \equiv -t
  - 1 \pmod{f}$, et ainsi $t^9 \equiv -t^3 - 1 \equiv t \pmod{f}$ (ce
  n'est qu'une façon de mener le calcul, on pouvait aussi préférer
  calculer la division euclidienne de $t^9 - t$ par $f$) ; d'autre
  part, (b) $f$ est premier avec $t^3 - t$ car $t^3 - t \equiv t - 1
  \pmod{f}$ (reste de la division de $t^3 - t$ par $f$) et $f \equiv 1
  \pmod{t-1}$ (reste de la division de $f$ par $t-1$), donc
  l'algorithme d'Euclide a montré que $f$ et $t^3 - t$ sont premiers
  entre eux : ainsi, le critère de Rabin assure que $f$ est
  irréductible.

\leavevmode\hphantom{(A)} (2) Puisque $f = t^2 + t - 1$ est
irréductible, on sait que $\mathbb{F}_3[t]/(f)$ sera un corps a
$3^{\deg f} = 9$ éléments.  En représentant les éléments de
$\mathbb{F}_9$ par des polynômes de degré $<2$ en $t$ vus comme des
classes de congruence modulo $f$ (de sorte que les $9$ éléments sont :
$0$, $1$, $-1$, $\bar t$, $\bar t+1$, $\bar t-1$, $-\bar t$, $-\bar
t+1$, $-\bar t-1$), on obtient les tables d'opérations suivantes :

\begin{center}
\tiny
\begin{tabular}{c|ccccccccc}
$+$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\\hline
$0$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\
$1$&$1$&$-1$&$0$&$\bar t+1$&$\bar t-1$&$\bar t$&$-\bar t+1$&$-\bar t-1$&$-\bar t$\\
$-1$&$-1$&$0$&$1$&$\bar t-1$&$\bar t$&$\bar t+1$&$-\bar t-1$&$-\bar t$&$-\bar t+1$\\
$\bar t+0$&$\bar t+0$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$&$0$&$1$&$-1$\\
$\bar t+1$&$\bar t+1$&$\bar t-1$&$\bar t+0$&$-\bar t+1$&$-\bar t-1$&$-\bar t$&$1$&$-1$&$0$\\
$\bar t-1$&$\bar t-1$&$\bar t+0$&$\bar t+1$&$-\bar t-1$&$-\bar t$&$-\bar t+1$&$-1$&$0$&$1$\\
$-\bar t+0$&$-\bar t$&$-\bar t+1$&$-\bar t-1$&$0$&$1$&$-1$&$\bar t+0$&$\bar t+1$&$\bar t-1$\\
$-\bar t+1$&$-\bar t+1$&$-\bar t-1$&$-\bar t$&$1$&$-1$&$0$&$\bar t+1$&$\bar t-1$&$\bar t+0$\\
$-\bar t-1$&$-\bar t-1$&$-\bar t$&$-\bar t+1$&$-1$&$0$&$1$&$\bar t-1$&$\bar t+0$&$\bar t+1$\\
\end{tabular}
\end{center}

\begin{center}
\tiny
\begin{tabular}{c|ccccccccc}
$\times$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\\hline
$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$&$0$\\
$1$&$0$&$1$&$-1$&$\bar t$&$\bar t+1$&$\bar t-1$&$-\bar t$&$-\bar t+1$&$-\bar t-1$\\
$-1$&$0$&$-1$&$1$&$-\bar t$&$-\bar t-1$&$-\bar t+1$&$\bar t$&$\bar t-1$&$\bar t+1$\\
$\bar t$&$0$&$\bar t$&$-\bar t$&$-\bar t+1$&$1$&$\bar t+1$&$\bar t-1$&$-\bar t-1$&$-1$\\
$\bar t+1$&$0$&$\bar t+1$&$-\bar t-1$&$1$&$\bar t-1$&$-\bar t$&$-1$&$\bar t$&$-\bar t+1$\\
$\bar t-1$&$0$&$\bar t-1$&$-\bar t+1$&$\bar t+1$&$-\bar t$&$-1$&$-\bar t-1$&$1$&$\bar t$\\
$-\bar t$&$0$&$-\bar t$&$\bar t$&$\bar t-1$&$-1$&$-\bar t-1$&$-\bar t+1$&$\bar t+1$&$1$\\
$-\bar t+1$&$0$&$-\bar t+1$&$\bar t-1$&$-\bar t-1$&$\bar t$&$1$&$\bar t+1$&$-1$&$-\bar t$\\
$-\bar t-1$&$0$&$-\bar t-1$&$\bar t+1$&$-1$&$-\bar t+1$&$\bar t$&$1$&$-\bar t$&$\bar t-1$\\
\end{tabular}
\end{center}

\leavevmode\hphantom{(A)} (3) Les ordres multiplicatifs possibles d'un
élément non nul dans $\mathbb{F}_9$ sont les diviseurs de $8$ (car $8$
est l'ordre du groupe multiplicatif $\mathbb{F}_9^\times$),
c'est-à-dire $1$, $2$, $4$ ou $8$.  On peut calculer les puissances
successives de $\bar t$ grâce à la table de multiplication : ce sont

\begin{center}
\begin{tabular}{c|c|c|c|c|c|c|c|c}
$i$&$0$&$1$&$2$&$3$&$4$&$5$&$6$&$7$\\\hline
$\bar t^i$&$1$&$\bar t$&$-\bar t+1$&$-\bar t-1$&$-1$&$-\bar t$&$-\bar t-1$&$\bar t+1$\\
\end{tabular}
\end{center}

\noindent Le fait (qu'on trouve ensuite) que $\bar t^8 = 1$ était
prévu par le petit théorème de Fermat généralisé.  Comme on a trouvé
$8$ puissances de $\bar t$ distinctes (c'est-à-dire qu'on n'est pas
retombé sur $1$ avant ce que le petit théorème de Fermat impose),
l'élément $\bar t$ est primitif.  La table ci-dessus est alors la
donnée d'un isomorphisme $i \mapsto \bar t^i$ entre le groupe additif
$\mathbb{Z}/8\mathbb{Z}$ et le groupe multiplicatif
$\mathbb{F}_9^\times$ (tous deux étant cycliques d'ordre $8$).  Les
générateurs de $\mathbb{F}_9^\times$ sont alors les $\varphi(8) = 4$
éléments qui correspondent à un générateur de
$\mathbb{Z}/8\mathbb{Z}$ par cet isomorphisme : comme les générateurs
du groupe additif $\mathbb{Z}/8\mathbb{Z}$ sont $1,3,5,7$ (ce sont les
nombres premiers avec $8$ modulo $8$, c'est-à-dire les
nombres impairs), les générateurs de $\mathbb{F}_9^\times$, autrement
dit les éléments primitifs de $\mathbb{F}_9$, sont $\bar t$, $-\bar
t-1$, $-\bar t$ et $\bar t+1$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(B) (1) Donner une racine, puis la décomposition en facteurs
irréductibles, de $t^2 + t \in \mathbb{F}_3[t]$.  (2) Que peut-on
dire de $\mathbb{F}_3[t]/(t^2 + t)$ ?  (Plusieurs réponses
possibles.)

\begin{corrige}
(B) (1) Le polynôme $f = t^2 + t \in \mathbb{F}_3[t]$ s'annule en $0$
  et en $-1$ : ce sont les deux racines de $f$, et on a donc $f =
  t(t+1)$, qui est la décomposition en facteurs irréductibles de ce
  polynôme.

\leavevmode\hphantom{(B)} (2) On peut dire que puisque $f = t^2 + t$
n'est pas irréductible, l'anneau $\mathbb{F}_3[t]/(f)$ n'est pas un
corps : et d'ailleurs ni $\bar t$ ni $\bar t + 1$ n'est inversible
dans cet anneau puisque leur produit est $\bar t^2 + \bar t = 0$ (ce
n'est pas un anneau intègre).  On peut aussi être plus précis :
puisque $f = t(t+1)$, le théorème chinois assure que
$\mathbb{F}_3[t]/(f) \cong \mathbb{F}_3[t]/(t) \times
\mathbb{F}_3[t]/(t+1)$ (où $\cong$ signifie « isomorphe »),
c'est-à-dire en fait $\mathbb{F}_3[t]/(f) \cong \mathbb{F}_3 \times
\mathbb{F}_3$ avec un isomorphisme $\mathbb{F}_3[t]/(f) \to
\mathbb{F}_3 \times \mathbb{F}_3$ qui envoie la classe dans
$\mathbb{F}_3[t]/(f)$ d'un polynôme $u \in \mathbb{F}_3[t]$ sur le
couple $(u(0), u(-1))$ formé des valeurs en $0$ et $-1$ de $u$ ; le
fait qu'on ait $\bar t \cdot (\bar t + 1) = 0$ se traduit,
\textit{via} cet isomorphism, en $(0,-1)\cdot (1,0) = (0,0)$.
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(C) (1) Montrer que le polynôme $t^5 + t^2 + 1 \in \mathbb{F}_2[t]$
est irréductible.  (2) Quels sont \textit{a priori} les ordres
multiplicatifs possibles de l'élément $\bar t$ (représenté par le
polynôme $t$) dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?  (3) L'élément
$\bar t$ est-il primitif dans $\mathbb{F}_2[t]/(t^5 + t^2 + 1)$ ?

\begin{corrige}
(C) (1) Le plus simple est d'appliquer le critère de Rabin : pour
  montrer que $f = t^5 + t^2 + 1 \in \mathbb{F}_2[t]$ est
  irréductible, il s'agit de vérifier que (a) $f$ divise $t^{32} - t$,
  et (b) $f$ est premier avec $t^2 - t$.  Pour ce qui est de (a), on a
  $t^5 \equiv t^2 + 1 \pmod{f}$ et on peut utiliser cette relation
  pour calculer les puissances suivantes de $t$ modulo $f$ : $t^6
  \equiv t^3 + t \pmod{f}$ (en multipliant par $t$) et $t^8 \equiv t^5
  + t^3 \equiv t^3 + t^2 + 1 \pmod{f}$ (en multipliant encore), donc
  (en élevant au carré, c'est-à-dire en appliquant le morphisme de
  Forbenius), $t^{16} \equiv t^6 + t^4 + 1 \equiv t^4 + t^3 + t + 1
  \pmod{f}$ (car on a vu $t^6 \equiv t^3 + t$), et en élevant de
  nouveau au carré, $t^{32} \equiv t^8 + t^6 + t^2 + 1 \equiv (t^3 +
  t^2 + 1) + (t^3 + t) + t^2 + 1 = t \pmod{f}$, ce qui prouve
  bien que $f$ divise $t^{32} - t$.  On pouvait aussi, bien entendu,
  poser la division euclidienne (mais elle est un peu
  fastidieuse\footnote{On trouve $t^{32} + t = (t^{27} + t^{24} +
    t^{22} + t^{21} + t^{18} + t^{17} + t^{16} + t^{15} + t^{14} +
    t^{10} + t^9 + t^7 + t^6 + t^5 + t^3 + t)(t^2+t)$.}).  Pour ce qui
  est de (b), la division euclidienne de $f$ par $t^2 + t$ est $f =
  (t^3 + t^2 + t)(t^2 + t) + 1$, et comme le reste est $1$, c'est le
  pgcd souhaité et $f$ et $t^2 - t$ sont premiers entre eux.

\leavevmode\hphantom{(C)} (2) Puisque $f = t^5 + t^2 + 1$ est
irréductible, le quotient $\mathbb{F}_2[t]/(f)$ est un corps, ayant
$2^{\deg f} = 32$ éléments, qu'on peut aussi noter $\mathbb{F}_{32}$.
Le groupe multiplicatif $\mathbb{F}_{32}^\times$ de ses éléments non
nuls a $31$ éléments.  Comme $31$ est premier, ses seuls diviseurs
sont $1$ et $31$, donc les seuls ordres multiplicatifs possibles d'un
élément non nul de $\mathbb{F}_{32}$ sont $1$ et $31$.

\leavevmode\hphantom{(C)} (3) On vient de voir que l'ordre
multiplicatif de $\bar t$ ne peut être que $1$ ou $31$.  Manifestement
ce n'est pas $1$ car $\bar t \neq 1$ : il s'ensuit que c'est $31$, et
$\bar t$ (comme \emph{tout} élément de $\mathbb{F}_{32}$ autre que $0$
et $1$) est primitif.  (On pouvait aussi se fatiguer à énumérer les
$31$ puissances $\bar t^i$ pour $i$ allant de $0$ à $30$, et vérifier
qu'elles sont bien toutes distinctes.)
\end{corrige}

\ifcorrige\medbreak\else\relax\fi

(D) (1) Justifier brièvement l'égalité suivante dans
$\mathbb{F}_2[t]$ : on a $t^{19}+1 = {(t+1)} \penalty0\,
{(t^{18}+t^{17}+t^{16} + \cdots + t^3+t^2+t+1)}$.  On appellera
$\Phi_{19}$ le second facteur ($t^{18}+\cdots+t+1$).  On \emph{admet}
que $\Phi_{19}$ est irréductible dans $\mathbb{F}_2[t]$.

\leavevmode\hphantom{(D)} (2) Quel est l'ordre multiplicatif de
l'élément $\bar t$ (représenté par $t$) dans
$\mathbb{F}_2[t]/(t^{19}+1)$ ?  Dans $\mathbb{F}_2[t]/(\Phi_{19})$ ?
Quel est le nombre d'éléments de $\mathbb{F}_2[t]/(\Phi_{19})$ (on ne
demande pas de l'écrire en décimal) ?  Est-ce un corps ?  L'élément
$\bar t$ est-il primitif (on parle toujours
dans $\mathbb{F}_2[t]/(\Phi_{19})$) ?  Question subsidiaire, plus
difficile : quelle est la décomposition en facteurs irréductibles du
polynôme $\Phi_{19}(X) = X^{18} + X^{17} + \cdots + X + 1$ vu comme
polynôme (en la nouvelle indéterminée $X$)
sur $\mathbb{F}_2[t]/(\Phi_{19})$ ?  (On pourra par exemple chercher
une racine, puis une façon d'en produire de nouvelles.)

\begin{corrige}
(D) (1) On a ${(t+1)} \penalty0\, {(t^{18}+t^{17} + \cdots + t^2+t+1)}
  = (t^{19}+t^{18} + \cdots + t^3+t^2+t) + (t^{18}+t^{17} + \cdots +
  t^2+t+1)$, et en regroupant par puissances de $t$ tous les termes
  de $t^{18} + t^{18}$ à $t+t$ s'annulent, et il ne reste que $t^{19}
  + 1$.

\leavevmode\hphantom{(D)} (2) Dans $\mathbb{F}_2[t]/(t^{19}+1)$, on a
$\bar t^{19} = 1$ puisque $t^{19} \equiv 1 \pmod{t^{19}+1}$, et si
$0<i<19$ alors $\bar t^i \neq 1$ puisque $t^i$ a pour reste lui-même
(il est de degré $<19$) par la division euclidienne par $t^{19}+1$.
Donc l'ordre multiplicatif de $\bar t$ est exactement $19$.  Dans
$\mathbb{F}_2[t]/(\Phi_{19})$, l'ordre de $\bar t$ est toujours $19$ :
il y a plusieurs façons de justifier ce fait, par exemple :
manifestement on a toujours $\bar t^{19} = 1$ (en effet, si $t^{19}
\equiv 1 \pmod{t^{19}+1}$, on a aussi $t^{19} \equiv 1
\pmod{\Phi_{19}}$ puisque $\Phi_{19}$ divise $t^{19} + 1$), et si
$i<18$ on a $\bar t^i \neq 1$ pour les mêmes raisons de degré, et
enfin $\bar t^{18} = \bar t^{17} + \bar t^{16} + \cdots + \bar t + 1
\neq 1$.  On peut aussi dire : comme $\Phi_{19}(1) = 1 \neq 0$, le
polynôme $\Phi_{19}$ n'est pas multiplie de $t+1$, donc il est premier
avec lui (comme $t+1$ est irréductible), donc
$\mathbb{F}_2[t]/(t^{19}+1) \cong \mathbb{F}_2[t]/(t+1) \times
\mathbb{F}_2[t]/(\Phi_{19})$ par le théorème chinois, et comme $\bar
t$ vaut $1$ dans $\mathbb{F}_2[t]/(t+1)$, son ordre est le même modulo
$t^{19}+1$ et modulo $\Phi_{19}$.

\leavevmode\hphantom{(D) (2)} Le nombre d'éléments de
$\mathbb{F}_2[t]/(\Phi_{19})$ est $2^{\deg\Phi_{19}} = 2^{18} =
262\,144$.  Puisque $\Phi_{19}$ est irréductible (comme on l'a admis),
c'est un corps (c'est une représentation du corps
$\mathbb{F}_{2^{18}}$ à $2^{18}$ éléments).  L'élément $\bar t$ étant
d'ordre $19$, il est d'ordre strictement plus petit que $2^{18}-1$,
donc cet élément n'est pas primitif.

\leavevmode\hphantom{(D) (2)} Question subsidiaire : cherchons à
factoriser $\Phi_{19}$ dans $\mathbb{F}_{2^{18}} =
\mathbb{F}_2[t]/(\Phi_{19})$.  Pour commencer, on a $\Phi_{19}(\bar t)
= \bar t^{18} + \bar t^{17} + \cdots + \bar t^2 + \bar t + 1 = 0$,
donc $\Phi_{19}$ a $\bar t$ pour racine.  Par ailleurs, si $\theta$
est une racine de $\Phi_{19}$, alors en appliquant le morphisme de
Frobenius, on voit que $\Phi_{19}(\theta^2) = \Phi_{19}(\theta)^2 = 0$
puisque $\Phi_{19}$ est à coefficients dans $\mathbb{F}_2$ (ou, si on
veut, $(\theta^{18} + \cdots + \theta + 1)^2 = \theta^{36} + \cdots +
\theta^2 + 1$).  Ceci montre que $\bar t^2$, $\bar t^4$, $\bar t^8$,
$\bar t^{16}$ sont aussi des racines de $\Phi_{19}$, ainsi que $\bar
t^{32} = \bar t^{13}$ (en rappelant que $\bar t$ est d'ordre $19$),
$\bar t^{64} = \bar t^{26}$, et ainsi de suite jusqu'à $\bar
t^{2^{17}} = \bar t^{10}$ (ensuite on retombe sur $\bar t^{2^{18}} =
\bar t$) ; on vérifie\footnote{En fait, c'est nécessairement le cas,
  parce que $\Phi_{19}$ ne peut pas avoir de racine multiple, mais
  c'est une justification un peu savante.} que toutes ces puissances
de $\bar t$ sont distinctes, c'est-à-dire, en fait, que $2$ est
primitif modulo $19$ : donc finalement les racines de $\Phi_{19}(X)$
dans $\mathbb{F}_{2^{18}} = \mathbb{F}_2[t]/(\Phi_{19}(t))$ sont tous
les $\bar t^i$ pour $i$ allant de $1$ à $18$, et on a $\Phi_{19}(X) =
(X-\bar t)(X-\bar t^2)(X-\bar t^3)\cdots (X-\bar t^{18})$.  On pouvait
aussi affirmer directement que $\bar t^i$ est une racine de
$\Phi_{19}$ pour tout $i \not\equiv 0 \pmod{19}$, car alors $\bar
t^{19i} = 1$ donc $\bar t^i$ est racine de $X^{19} + 1$, et par
ailleurs $\bar t^i \neq 1$ (si $i \not\equiv 0 \pmod{19}$) donc $\bar
t^i$ n'est pas racine de $X+1$, et du coup $\bar t^i$ est racine du
polynôme $\Phi_{19}(X) = \frac{X^{19}+1}{X+1}$.
\end{corrige}

%
%
%
\end{document}