summaryrefslogtreecommitdiffstats
path: root/controle-20081202.tex
blob: cd52eafaae4b046dc90304a86802e8b001708a81 (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
%% 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{\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{2 décembre 2008}
\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, les questions se suivent normalement dans
un ordre logique, et il est vivement recommandé de les traiter dans
cet ordre.

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ée.

L'usage des calculatrices électroniques est interdites.  (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

Les deux questions suivantes sont indépendantes.

(1) Montrer que $a^{31} \equiv a \pmod{341}$ pour tout $a \in
\mathbb{Z}$ (note : on a $341 = 11\times 31$).

(2) Pourquoi a-t-on $a^{32} \equiv 1 \pmod{128}$ pour tout $a$ impair
(note : $128 = 2^7$) ?

\begin{corrige}
(1) Comme $11$ et $31$ sont premiers entre eux, le théorème chinois affirme
  $\mathbb{Z}/341\mathbb{Z} \cong (\mathbb{Z}/11\mathbb{Z}) \times
  (\mathbb{Z}/31\mathbb{Z})$, donc il suffit de prouver $a^{31} \equiv
  a \pmod{31}$ et $a^{31} \equiv a \pmod{11}$ pour tout $a
  \in\mathbb{Z}$.  Or on a $a^{31} \equiv a \pmod{31}$ d'après le
  petit théorème de Fermat ; s'agissant de la relation modulo $11$, on
  a $a^{10} \equiv 1 \pmod{11}$ si $11$ ne divise pas $a$ (théorème
  d'Euler), donc $a^{30} = (a^{10})^3 \equiv 1 \pmod{11}$ donc $a^{31}
  \equiv a \pmod{11}$, et ceci est aussi vrai lorsque $a \equiv 0
  \pmod{11}$, donc dans tous les cas $a^{31} \equiv a \pmod{11}$.

(2) Le théorème d'Euler ne suffit pas, car $\varphi(128) = 64$ donc il
  donne seulement $a^{64} \equiv 1 \pmod{128}$ lorsque $a$ est impair
  (ce qui équivaut à premier à $128$).  En revanche, on sait (cours)
  que $(\mathbb{Z}/128\mathbb{Z})^\times =
  (\mathbb{Z}/2^7\mathbb{Z})^\times$ n'a pas d'éléments primitifs : il
  est produit d'un groupe cyclique d'ordre $2$ (engendré par $-1$) et
  d'un groupe cyclique d'ordre $2^5 = 32$ (engendré par $5$).  Si on
  note ces deux groupes multiplicativement, on a $a^{32} = a$ dans
  chacun d'entre eux par le théorème de Lagrange, donc c'est le cas
  dans $(\mathbb{Z}/128\mathbb{Z})^\times$.
\end{corrige}

%
%
%

\exercice

Le calendrier religieux maya (ou Tzolkin) est la combinaison de deux
cycles indépendant, l'un de $13$ jours numérotés de 1 à 13, l'autre de
$20$ jours portant des noms de dieux (dans l'ordre : « Ahau »,
« Imix », « Ik », « Akbal », « Kan », « Chicchan », « Cimi »,
« Manik », « Lamat », « Muluc », « Oc », « Chuen », « Eb », « Ben »,
« Ix », « Men », « Cib », « Caban », « Etznab » et « Caunac »).

Ces deux cycles sont complètement indépendants, c'est-à-dire que si un
jour est numéroté « 11 Ahau », le lendemain sera « 12 Imix », puis
« 13 Ik », puis « 1 Akbal », « 2 Kan » et ainsi de suite jusqu'à
« 4 Caunac » auquel suit « 5 Ahau », etc.  Il n'existe aucune
irrégularité.

(1) Quelle est le nombre de jours d'un cycle du Tzolkin ?  Autrement
dit, au bout de combien de jours après un jour donné retombe-t-on pour
la première fois sur un jour ayant le même numéro et le même nom ?

(2) Sachant que le 2 décembre 2008 est dénommé « 6 Ahau », déterminer
quand aura lieu le prochain jour « 10 Oc » au calendrier religieux
maya.

(3) Les Mayas utilisaient également un calendrier civil (ou Haab) de
$365$ jours exactement\footnote{Ce calendrier était lui-même organisé
  en mois, mais cela ne nous importe pas ici.}, qui se répétait lui
aussi sans irrégularité, et complètement indépendamment du calendrier
religieux Tzolkin.  Quelle est la longueur approximative en années
d'un cycle complet des deux calendriers ?  Autrement dit, combien
d'années faut-il attendre approximativement, à partir d'un jour donné,
pour retrouver pour la première fois un jour ayant la même
dénomination dans les deux calendriers (Tzolkin et Haab) à la fois ?

\begin{corrige}
(1) Le cycle complet du Tzolkin est le plus petit nombre multiple à la
  fois de $13$ (à cause du cycle de $13$ jours) et de $20$ (à cause du
  cycle de $20$ jours), c'est-à-dire le ppcm de $13$ et de $20$.
  Comme $13$ et $20$ sont premiers entre eux, c'est $13\times 20 =
  260$.

(2) Si le prochain jour « 10 Oc » a lieu $n$ jours après le
  2 décembre 2008 (6 Ahau), alors $n \equiv 4 \pmod{13}$ puisque dans
  le cycle de $13$ jours on est passé de $6$ à $10$, et $n \equiv 10
  \pmod{20}$ puisqu'on est $10$ dieux plus loin dans le cycle de
  $20$ jours.  On a la relation de Bézout $2\times 20 - 3\times 13 =
  1$, donc $n$ est congru à $(4 \times 2) \times 20 - (10 \times 3)
  \times 13$ modulo $260$ : dans cette expression, il suffit de
  calculer $10\times 3$ modulo $20$ (c'est $10$), on trouve donc
  $8\times 20 - 10\times 13 = 160-130 = 30$ (on vérifie $30 \equiv 4
  \pmod{13}$ et $30 \equiv 10 \pmod{20}$) : le prochain « 10 Oc » a
  donc lieu $30$ jours après le 2 décembre 2008 (c'est-à-dire le
  1er janvier 2009).

(3) Le cycle complet du calendrier (Tzolkin+Haab) est le plus petit
  nombre multiple à la fois de $260$ (à cause du Tzolkin) et de $365$
  (à cause du Haab), c'est-à-dire le ppcm de $260 = 2^2\times 5 \times
  13$ et de $365 = 5 \times 73$ : c'est donc $2^2\times 5 \times 13
  \times 73$, c'est-à-dire $2^2\times 13\times 365$ jours, ou encore
  environ $2^2\times 13 = 52$ ans.
\end{corrige}

%
%
%

\exercice

Soit $n = 2^{100}$ et $N = 2^n = 2^{2^{100}}$.

(1) Quel est le reste de la division euclidienne de $n$ par $3$ et par
$5$ ?

% Réponses : 1, 1

(2) Quel est le reste de la division euclidienne de $n$ par $6$,
par $10$ et par $4$ ?

% Réponses : 4, 6, 0

(3) Quel est le reste de la division euclidienne de $N$ par $9$,
par $11$ et par $10$ ?

% Réponses : 7, 9, 6

(4) Quel est le reste de la division euclidienne de $N$ par $99$ ?
Par $990$ ?

% Réponses : 97, 196

\begin{corrige}
(1) Le théorème d'Euler (ou une vérification naïve immédiate) assure
  que $2^2 \equiv 1 \pmod{3}$.  Par conséquent, $2^{100} = (2^2)^{50}
  \equiv 1^{50} = 1 \pmod{3}$.  De même, modulo $5$, on a (toujours
  par Euler ou vérification naïve) $2^4 \equiv 1 \pmod {5}$ donc
  $2^{100} = (2^5)^{25} \equiv 1^{25} = 1 \pmod{5}$.

(2) Le théorème chinois assure que la classe de congruence de $n$
  modulo $6$ dépend de celles de $n$ modulo $2$ et $3$.  La question
  précédente a déterminé la classe de $n$ modulo $3$ (c'est $1$), et
  on a visiblement $n = 2^{100} \equiv 0 \pmod{2}$ (manifestement,
  $2^{100}$ est pair...).  Pour reconstituer $n$ modulo $6$, on
  cherche donc un nombre congru à $1$ modulo $3$ et à $0$ modulo $2$ :
  on peut chercher une relation de Bézout ($3-2=1$), mais il est plus
  simple d'examiner rapidement les différentes classes possibles
  entre $0$ et $5$ : visiblement $4$ convient, donc $n \equiv 4
  \pmod{6}$.

De même, pour déterminer la classe de $n$ modulo $10$, le théorème
chinois assure qu'elle ne dépend que de $n$ modulo $2$ et $5$.  Or on
a vu $n \equiv 0 \pmod{2}$ et $n \equiv 1 \pmod{5}$.  On voit
rapidement que $6$ est congru aux mêmes quantités, donc $n \equiv 6
\pmod{10}$.

Enfin, il est clair que $2^{100}$ est multiple de $4$ (i.e., congru
à $0$ modulo $4$).

(3) Le théorème d'Euler assure que $2^6 \equiv 1 \pmod{9}$ (on a
$\varphi(9) = \frac{2}{3}\times 9 = 6$).  Par conséquent, $2^{6k} =
(2^6)^k \equiv 1^{k} = 1 \pmod{9}$ pour tout $k \in \mathbb{N}$.  Or
on a vu à la question précédente que $n = 2^{100}$ peut s'écrire sous
la forme $6k + 4$ : on a donc $2^n = 2^{6k+4} \equiv 2^4 \equiv 7
\pmod{9}$.

Modulo $11$, le raisonnement est analogue : le théorème d'Euler (ou
Fermat) assure que $2^{10} \equiv 1 \pmod{11}$.  Par conséquent,
$2^{10k} = (2^{10})^k \equiv 1^k = 1 \pmod{11}$ pour tout $k \in
\mathbb{N}$.  Or on a vu que $n = 2^{100}$ peut s'écrire sous la forme
$10k+6$ : on a donc $2^n = 2^{10k+6} \equiv 2^6 \equiv 9 \pmod{11}$.

Modulo $10$, on ne peut pas appliquer le même raisonnement ($2$ n'est
pas premier à $10$ !), mais on peut appliquer celui des questions
(1) et (2) : on a vu $n \equiv 0 \pmod{4}$, c'est-à-dire qu'on peut
écrire $n = 4k$ (avec $k = 2^{98}$ mais peu importe), donc $2^n =
(2^4)^k \equiv 1^k = 1 \pmod{5}$, et comme $2^n \equiv 0 \pmod{2}$, on
a $2^n \equiv 6 \pmod{10}$ (exactement comme on l'a fait en (2)).

(4) Il s'agit enfin d'appliquer le théorème chinois de façon effective
pour reconstituer la classe de $N$ modulo $99$ puis $990$ à partir de
ses classes modulo $9$, $11$ et $10$, déjà calculées (soit $N \equiv 7
\pmod{9}$, $N \equiv 9 \pmod{11}$ et $N \equiv 6 \pmod{10}$).

Trouvons une relation de Bézout entre $9$ et $11$ (qui sont bien
premiers entre eux !).  Pour cela, on peut appliquer l'algorithme
d'Euclide étendu, qui termine en deux divisions : $11 = 1\times 9 + 2$
puis $9 = 4\times 2 + 1$, donc $1 = 1\times 9 - 4\times 2$ et ($2 = 11
- 1\times 9$ donc) $1 = 5\times 9 - 4\times 11$ (on pouvait aussi
trouver rapidement cette relation en cherchant dans les petits
multiples de $9$ et $11$ lesquels deux sont consécutifs).  On sait
donc (cours) que $N \equiv 9\times 5\times 9 - 7\times 4\times 11
\pmod{99}$ : pour faire ce calcul plus simplement à la main, on peut
réduire $9\times 5$ modulo $11$ et $7\times 4$ modulo $9$, ce qui fait
respectivement $1$ et $1$, donc $N \equiv 1\times 9 - 1\times 11 = -2
\equiv 97 \pmod{99}$.

Enfin, reconstruisons $N$ modulo $990$ à partir de $N \equiv 6
\pmod{10}$ et $N \equiv 97 \pmod{99}$.  Une relation de Bézout entre
$99$ et $10$ est évidente : c'est $10\times 10 - 1\times 99 = 1$.  Par
conséquent, $N \equiv 97\times 10\times 10 - 6\times 1\times 99
\pmod{990}$.  De nouveau, pour simplifier les calculs, on peut se
contenter de calculer $97\times 10 \equiv (-2)\times 10 = -20$
modulo $99$ et $-6\times 1 \equiv 4 \pmod{10}$, donc on a $N \equiv
-20\times 0 + 4\times 99 = 196 \pmod{990}$.
\end{corrige}

%
%
%

\exercice

Une conjecture affirme que pour tout entier $n$ il existe $n' \neq n$
tel que $\varphi(n') = \varphi(n)$ (où $\varphi$ désigne la fonction
indicatrice d'Euler).  On va voir qu'on peut montrer cette conjecture
au moins pour les petites valeurs de $n$.

(1a) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$.

(1b) Si $n$ est pair mais non multiple de $4$, montrer que
$\varphi(\frac{1}{2}n) = \varphi(n)$.

(1c) Si $n$ est multiple de $4$ mais non de $12$, montrer que
$\varphi(\frac{3}{2}n) = \varphi(n)$.

(1d) Si $n$ est multiple de $12$ mais non de $36$, montrer
que $\varphi(\frac{2}{3}n) = \varphi(n)$.

(1e) Si $n$ est multiple de $36$ mais non de $7\times 36 = 252$,
montrer que $\varphi(\frac{7}{6}n) = \varphi(n)$.

(1f) Si $n$ est multiple de $7\times 36 = 252$ mais non de $7^2\times
36 = 1764$, montrer que $\varphi(\frac{6}{7}n) = \varphi(n)$.

(2) En continuant selon la même logique, montrer que la conjecture
énoncée plus haut est valable lorsque $n$ n'est pas multiple de
$(6\times 7 \times 43)^2$.

(3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$
ni de $13$, montrer que $\varphi(\frac{13}{18}n) = \varphi(n)$.

(4) Sachant que $(6\times 7 \times 43)^2 \geq 3\times 10^6$, jusqu'à
combien les questions précédentes permettent-elles d'affirmer la
véracité de la conjecture ?

\begin{corrige}
Rappelons du cours que si $u$ et $v$ sont premiers entre eux, on a
\[
\varphi(uv) = \varphi(u)\,\varphi(v)\tag{*}
\]
(c'est une conséquence immédiate du théorème chinois
$(\mathbb{Z}/uv\mathbb{Z})^\times \cong
(\mathbb{Z}/u\mathbb{Z})^\times \times
(\mathbb{Z}/v\mathbb{Z})^\times$ en prenant les cardinaux).  \textit{A
  contrario}, si $u$ est divisible par chaque nombre premier
divisant $v$ (par exemple si $u|v$), on a
\[
\varphi(uv) = u \, \varphi(v)\tag{\textdagger}
\]
puisque $\varphi(v) = v\prod_{p|v}(1-\frac{1}{p})$ et $\varphi(uv) =
uv\prod_{p|uv}(1-\frac{1}{p})$, le produit portant sur le même
ensemble de nombres premiers $p$.

(1a) Si $n$ est impair, c'est-à-dire si $2$ et $n$ sont premiers entre
eux, alors $\varphi(2n) = \varphi(2)\,\varphi(n) = \varphi(n)$
d'après (*) (remarquer $\varphi(2)=1$).

(1b) Si $n$ est pair mais non multiple de $4$, le nombre
$\frac{1}{2}n$ est un entier impair, donc de nouveau $\varphi(n) =
\varphi(2\,\frac{1}{2}n) = \varphi(2)\,\varphi(\frac{1}{2}n) =
\varphi(\frac{1}{2}n)$ d'après (*).

(1c) Si $n$ est multiple de $4$ mais non de $12$, le nombre
$\frac{1}{2}n$ est un entier pair mais non multiple de $3$ (donc
premier à lui), donc d'une part $\varphi(\frac{3}{2}n) =
\varphi(3\,\frac{1}{2}n) = \varphi(3)\,\varphi(\frac{1}{2}n) =
2\varphi(\frac{1}{2}n)$ d'après (*) (remarquer $\varphi(3)=2$) et
d'autre part $\varphi(n) = \varphi(2\,\frac{1}{2}n) =
2\varphi(\frac{1}{2}n)$ d'après (\textdagger).  En rassemblant ces
deux égalités, on a $\varphi(\frac{3}{2}n) = \varphi(n)$.

(1d) Si $n$ est multiple de $12$ mais non de $36$, le nombre
$\frac{1}{3}n$ est un entier pair mais non multiple de $3$, donc d'une
part $\varphi(n) = \varphi(3\,\frac{1}{3}n) =
\varphi(3)\,\varphi(\frac{1}{3}n) = 2\varphi(\frac{1}{3}n)$
d'après (*) et d'autre part $\varphi(\frac{2}{3}n) =
\varphi(2\,\frac{1}{3}n) = 2\varphi(\frac{1}{3}n)$
d'après (\textdagger).  En rassemblant ces deux égalités, on a
$\varphi(\frac{2}{3}n) = \varphi(n)$.

(1e) Si $n$ est multiple de $36$ mais non de $252$, le nombre
$\frac{1}{6}n$ est un entier multiple de $6$ mais non multiple de $7$,
donc d'une part $\varphi(\frac{7}{6}n) = \varphi(7\,\frac{1}{6}n) =
\varphi(7)\,\varphi(\frac{1}{6}n) = 6\varphi(\frac{1}{6}n)$
d'après (*) (remarquer $\varphi(7)=6$) et d'autre part $\varphi(n) =
\varphi(6\,\frac{1}{6}n) = 6\varphi(\frac{1}{6}n)$
d'après (\textdagger).  En rassemblant ces deux égalités, on a
$\varphi(\frac{7}{6}n) = \varphi(n)$.

(1f) Si $n$ est multiple de $252$ mais non de $1764$, le nombre
$\frac{1}{7}n$ est un entier multiple de $6$ mais non multiple de $7$,
donc d'une part $\varphi(n) = \varphi(7\,\frac{1}{7}n) =
\varphi(7)\,\varphi(\frac{1}{7}n) = 6\varphi(\frac{1}{7}n)$
d'après (*) et d'autre part $\varphi(\frac{6}{7}n) =
\varphi(6\,\frac{1}{7}n) = 6\varphi(\frac{1}{7}n)$
d'après (\textdagger).  En rassemblant ces deux égalités, on a
$\varphi(\frac{6}{7}n) = \varphi(n)$.

(2) De façon exactement analogue à (1c) et (1e), si $n$ est multiple
de $6^2\times 7^2 = 1764$ mais non de $6^2\times 7^2\times 43$, on
montre que $\varphi(\frac{43}{42}n) = \varphi(n)$.  De façon
exactement analogue à (1d) et (1f), si $n$ est multiple de $6^2\times
7^2\times 43$ mais non de $6^2\times 7^2\times 43^2$, on montre que
$\varphi(\frac{42}{43}n) = \varphi(n)$.

Appelons $n$ un entier qui ne vérifie pas la conjecture, s'il existe.
D'après (1a), $n$ doit être pair (car les entiers impairs vérifient la
conjecture).  D'après (1b), il doit donc être multiple de $4$.
D'après (1c), il doit alors être multiple de $12$.  D'après (1d), il
doit alors être multiple de $36$.  D'après (1e), il doit alors être
multiple de $36\times 7 = 252$.  D'après (1f), il doit alors être
multiple de $36\times 7^2 = 1764$.  D'après le paragraphe précédent,
il doit alors être multiple de $6^2\times 7^2\times 43$, puis de
$6^2\times 7^2\times 43^2$.

(On ne peut plus ensuite continuer ce petit jeu de façon aussi
mécanique, puisque $6\times 7\times 43 + 1 = 1807$ n'est plus
premier.)

(3) Si $n$ est multiple de $(6\times 7 \times 43)^2$ mais ni de $27$
ni de $13$, le nombre $\frac{1}{18}n$ est un entier multiple de $2$
mais non multiple de $3$ ni de $7$, donc d'une part
$\varphi(\frac{13}{18}n) = \varphi(13\,\frac{1}{18}n) =
\varphi(13)\,\varphi(\frac{1}{18}n) = 12\varphi(\frac{1}{18}n)$
d'après (*) et d'autre part $\varphi(n) = \varphi(9\times 2 \times
\frac{1}{18}n) \buildrel\textrm{(*)}\over=
\varphi(9)\varphi(2\,\frac{1}{18}n) = 6 \varphi(2\,\frac{1}{18}n)
\buildrel\textrm{(\textdagger)}\over= 6\times 2\times
\varphi(\frac{1}{18}n) = 12\varphi(\frac{1}{18}n)$.  En rassemblant
ces deux égalités, on a $\varphi(\frac{13}{18}n) = \varphi(n)$.

(4) Si $n$ ne vérifie pas la conjecture, on sait déjà qu'il doit être
multiple de $6^2\times 7^2\times 43^2$, et la question (3) montre
qu'il doit de plus l'être de $27$ (donc de $2^2\times 3^3\times
7^2\times 43^2$) ou bien de $13$ (donc de $2^2\times 3^2\times
7^2\times 13\times 43^2$).  Il doit donc au moins être égal à
$2^2\times 3^3\times 7^2\times 43^2 \geq 9\times 10^6$.  On a donc
montré que la conjecture était vraie au moins pour les neuf millions
de premiers entiers naturels.
\end{corrige}

%
%
%

\exercice

Cet exercice décrit le principe l'algorithme de factorisation
« $p-1$ » de Pollard.

\emph{Définition :} On dit qu'un entier naturel $m$ est
     « $B$-friable » (pour $B$ un entier naturel) lorsque tout facteur
     premier $\ell$ de $m$ est $\leq B$.  (Par exemple, $720$ est
     $5$-friable.)

(1) Soit $p$ un nombre premier tel que $p-1$ soit $B$-friable (pour
une certaine borne $B$).  Soient $\ell_1,\ldots,\ell_k$ les nombres
premiers $\leq B$.  Partant de $a \in
(\mathbb{Z}/p\mathbb{Z})^\times$, on effectue les opérations
suivantes : pour $i$ allant de $1$ à $k$, on remplace $a$ par
$a^{\ell_i^{r_i}}$ (ce calcul étant fait dans
$\mathbb{Z}/p\mathbb{Z}$), où $r_i$ est un entier supérieur ou égal à
$\log(p)/\log(\ell_i)$.  Quel est le résultat obtenu (autrement dit,
que vaut $a$ après ces différentes opérations) ?  \emph{Indication :}
montrer qu'on a élevé $a$ à une puissance d'exposant multiple
de $p-1$.

\smallskip

On suppose maintenant que $N$ est un entier non premier à factoriser,
et on espère qu'un de ses facteurs premiers $p$ est tel que $p-1$ soit
$B$-friable avec $B$ assez petit.  (Naturellement, on ne sait pas ce
que vaut $p$ : on cherche justement à le calculer ou, du moins, à
trouver une factorisation non triviale $N = d d'$ avec $d,d'>1$.)

L'algorithme $p-1$ de Pollard effectue le calcul suivant, en partant
d'un nombre $N$ à factoriser et d'une borne $B$ de friabilité
(typiquement de l'ordre de $10^6$) :
\begin{itemize}
\item tirer au hasard un entier $a$ entre $2$ et $N-2$ ;
\item calculer $\pgcd(a,N)$ : s'il est $>1$, terminer : ($*$) on a
  trouvé une factorisation non triviale de $N$ ;
\item énumérer les nombres premiers $\ell_1,\ldots,\ell_k$ inférieurs
  ou égaux à $B$ ;
\item pour $i$ allant de $1$ à $k$ :
\begin{itemize}
\item soit $r \geq \log(N)/\log(\ell_i)$ entier,
\item faire $a \leftarrow a^{\ell_i^r}$ dans $\mathbb{Z}/N\mathbb{Z}$ ;
\end{itemize}
\item calculer $d = \pgcd(a-1,N)$ ;
\item si $1<d<N$, terminer : ($*$) on a trouvé une factorisation non
  triviale de $N$ ;
\item si $d=1$, terminer avec l'erreur suivante : ($\dagger$) il
  n'existe aucun facteur $p$ de $N$ tel que $p-1$ soit $B$-friable (on
  peut essayer d'augmenter $B$ et de recommencer) ;
\item si $d=N$, terminer avec l'erreur suivante : ($\ddagger$) on n'a
  pas eu de chance (on peut recommencer pour un $a$ différent) ou bien
  tous les facteurs $p$ de $N$ sont tels que $p-1$ soit $B$-friable
  (on peut recommancer avec un $B$ plus petit).
\end{itemize}

\smallskip

(2a) Expliquer les affirmations ($*$) « on a trouvé une factorisation
  non triviale » de l'algorithme.

(2b) Expliquer l'affirmation ($\dagger$) « il n'existe aucun facteur
  $p$ de $N$ tel que $p-1$ soit $B$-friable ».  \emph{Indication :}
utiliser la question (1).

(2c) Proposer un exemple de situation pouvant conduire au dernier
cas ($\ddagger$).

%
%
%

\exercice

Soit $p$ un nombre premier congru à $5$ modulo $6$.

(1) Y a-t-il des éléments d'ordre $3$ dans $\mathbb{F}_p^\times$ ?
Résoudre l'équation $z^3 = 1$ dans $\mathbb{F}_p$.

(2) Montrer que l'application $\mathbb{F}_p \to \mathbb{F}_p$ définie
par $x \mapsto x^3$ est une bijection (c'est-à-dire que chaque valeur
de la cible est atteinte une et une seule fois).

(3) Si $a \in \mathbb{F}_p^\times$, à quoi est isomorphe
$\mathbb{F}_p[t] / (t^3-a)$ ?

\begin{corrige}
(1) D'après le théorème de Lagrange, l'ordre d'un élément de
  $\mathbb{F}_p^\times$ doit diviser l'ordre de ce groupe,
  c'est-à-dire $p-1$ : donc s'il existait un élément d'ordre $3$, on
  aurait $3|(p-1)$, c'est-à-dire $p\equiv 1\pmod{3}$, or ceci
  contredit $p \equiv 5\pmod{6}$.

L'équation $z^3=1$ dans $\mathbb{F}_p$ au moins la solution $z=1$.  Si
elle avait une autre solution, celle-ci serait évidemment non nulle,
donc dans $\mathbb{F}_p^\times$, dont elle serait un élément
d'ordre $3$ (d'après l'équation elle-même), et on vient de voir que
cela n'existe pas.  La seule solution de $z^3=1$ dans $\mathbb{F}_p$
(avec $p$ premier congru à $5$ modulo $6$) est donc $z=1$.

(2) Tout d'abord, la valeur $0$ n'est atteinte par $h\colon x\mapsto
x^3$ que pour $x=0$, car le cube d'un élément non nul est forcément
non nul (un produit d'éléments non nuls d'un corps est non nul...).
On peut donc écarter cette valeur et se concentrer sur $x\mapsto x^3$
dans $\mathbb{F}_p^\times$.  Or si $x^3 = y^3$ avec $x,y \in
\mathbb{F}_p^\times$, alors on a $(x^{-1}y)^3 = 1$ (en notant $x^{-1}$
l'inverse de $x$), donc $x^{-1}y = 1$ d'après la question précédente,
c'est-à-dire $x = y$.  On a donc montré que $h(x)=h(y)$ entraîne $x=y$
(la fonction $h$ est injective, si l'on veut) : chaque valeur de la
cible ne peut être atteinte qu'au plus une fois.  Mais comme la source
et la cible ont le même nombre d'éléments, chaque valeur de la cible
est atteinte exactement une fois.

(3) La question précédente montre que (sous l'hypothèse que $p$
premier congru à $5$ modulo $6$, bien sûr !) tout élément $a \in
\mathbb{F}_p^\times$ est un cube, donc peut s'écrire $a = b^3$, et de
plus, il n'y a qu'un $b$ possible.  Le polynôme $t^3 - a \in
\mathbb{F}_p[t]$ possède donc la racine $b$, donc le facteur $t-b$,
mais il n'a pas d'autre racine.  Le facteur restant $\frac{t^3-a}{t-b}
= t^2 + bt + b^2$ n'a donc aucune racine dans $\mathbb{F}_p$ : il ne
peut donc pas se factoriser (car les facteurs auraient degré $1$
et $1$), donc il est irréductible.  La décomposition $t^3 - a =
(t-b)(t^2+bt+b^2)$ est donc la décomposition en facteurs irréductibles
de $t^3-a$.  On a donc l'isomorphisme chinois $\mathbb{F}_p[t] /
(t^3-a) \cong (\mathbb{F}_p[t]/(t-b)) \times
(\mathbb{F}_p[t]/(t^2+bt+b^2))$.  Le premier facteur est isomorphe à
$\mathbb{F}_p$ et le second à $\mathbb{F}_{p^2}$.  Bref,
$\mathbb{F}_p[t] / (t^3-a) \cong \mathbb{F}_p \times
\mathbb{F}_{p^2}$.
\end{corrige}

%
%
%

\exercice

Montrer que tout $x \in \mathbb{F}_{32}^\times$ est primitif [erreur
  dans l'énoncé : il fallait ajouter la précision « sauf $x=1$ »].
Combien d'éléments de $\mathbb{F}_{64}^\times$ sont primitifs ?

\begin{corrige}
D'après le cours, on sait que $\mathbb{F}_{q}^\times$ est un groupe
cyclique (d'ordre $q-1$) pour toute puissance $q$ d'un nombre premier
(notamment $32 = 2^5$ et $64 = 2^6$).  Également d'après le cours, le
nombre de générateurs d'un groupe cyclique (appelés éléments primitifs
lorsqu'il s'agit comme ici du groupe multiplicatif d'un corps fini)
est $\varphi(n)$ où $n$ est l'ordre de ce groupe.  Le nombre
d'éléments primitifs dans $\mathbb{F}_{32}^\times$ est donc
$\varphi(32-1) = \varphi(31) = 30$, c'est-à-dire tous sauf
($0$ et) $1$, et le nombre d'éments primitifs dans
$\mathbb{F}_{64}^\times$ vaut $\varphi(64-1) = \varphi(63) =
\frac{1}{2}\times\frac{6}{7}\times 63 = 36$.
\end{corrige}

%
%
%

\exercice

Le polynôme $t^2 + 1 \in \mathbb{F}_3[t]$ est-il irréductible ?
Est-il primitif ?

\begin{corrige}
Pour tester l'irréductibilité de $t^2 + 1 \in \mathbb{F}_3[t]$, on
peut se contenter de vérifier qu'il n'a pas de racine (soit : $0^2+1
\neq 0$ et $1^2+1\neq 0$ et $2^2+1\neq 0$ dans $\mathbb{F}_3$),
puisque s'il se factorisait les facteurs auraient degré $1$ et $1$
donc correspondraient à des racines.  Mais on peut également préférer
appliquer mécaniquement le test de Rabin : on vérifie que $t^2+1$
divise $t^9-t \in \mathbb{F}_3[t]$ (de fait, $t^9-t = (t^7-t^5+t^3-t)
(t^2+1)$) et qu'il est premier avec $t^3-t$ (de fait, $t^3-t =
t(t^2+1) + t$ et $t^2+1 = t\times t + 1$).  Ce polynôme est bien
irréductible.

Maintenant qu'on sait que $t^2+1 \in \mathbb{F}_3[t]$ est
irréductible, on a une représentation du corps à $9$ éléments :
$\mathbb{F}_9 \cong \mathbb{F}_3[t]/(t^2+1)$.  La question est de
savoir si l'élément $\bar t$ de ce corps est primitif.  Or $\bar t^2 =
-1$ donc $\bar t^4 = 1$, donc cet élément est d'ordre $4$, qui est
plus petit que l'ordre $9-1=8$ du groupe multiplicatif
$\mathbb{F}_9^\times$ : l'élément $\bar t$ n'est pas primitif (plus
explicitement, les seuls éléments de $\mathbb{F}_9 \cong
\mathbb{F}_3[t]/(t^2+1)$ qui sont des puissances de $\bar t$ sont $\pm
1$ et $\pm t$).  Cela signifie (par définition) que le polynôme $t^2+1
\in \mathbb{F}_3[t]$ n'est pas primitif.
\end{corrige}

%
%
%
\end{document}