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
|
%% 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}}
%
%
%
\begin{document}
\title{INFMDI720\\Contrôle de connaissance\\{\normalsize Rappels mathématiques pour la cryptographie}}
\author{}
\date{2 décembre 2008}
\maketitle
\pretolerance=10000
\tolerance=8000
\vskip1truein\relax
\textbf{Consignes :}
L'usage de tous les documents (notes de cours manuscrites ou
imprimées, livres) est autorisée. L'usage des calculatrices
électroniques n'est pas autorisée.
\newpage
%
%
%
\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 ?
%
%
%
\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
%
%
%
\exercice
Montrer que $a^{31} \equiv a \pmod{341}$ pour tout $a \in \mathbb{Z}$
(note : on a $341 = 11\times 31$).
%
%
%
\exercice
Montrer que tout $x \in \mathbb{F}_{32}^\times$ est primitif. Combien
d'éléments de $\mathbb{F}_{64}^\times$ sont primitifs ?
%
%
%
\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$.
(1) Si $n$ est impair, montrer que $\varphi(2n) = \varphi(n)$.
(2) Si $n$ est pair mais non multiple de $4$, montrer que
$\varphi(\frac{1}{2}n) = \varphi(n)$.
(3) Si $n$ est multiple de $4$ mais non de $12$, montrer que
$\varphi(\frac{3}{2}n) = \varphi(n)$.
(4) Si $n$ est multiple de $12$ mais non de $36$, montrer
que $\varphi(\frac{2}{3}n) = \varphi(n)$.
(5) Si $n$ est multiple de $36$ mais non de $7\times 36$, montrer
que $\varphi(\frac{7}{6}n) = \varphi(n)$.
(6) Si $n$ est multiple de $7\times 36$ mais non de $7^2\times 36$,
montrer que $\varphi(\frac{6}{7}n) = \varphi(n)$.
(7) Montrer la vérité de la conjecture énoncée plus haut lorsque $n <
(6\times 7 \times 43)^2$.
%
%
%
\end{document}
|
