blob: 0ed9d5c2cd46d7cfc881dc830eca75db470e645e (
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
|
%% 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{23 novembre 2010}
\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.
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) Quel entier entre $1500$ et $2500$ est congru à $36$ modulo $47$
et à $49$ modulo $53$ ?
(B) Quel est le plus petit entier naturel multiple de $9$ et de $11$
et congru à $6$ modulo $10$ ?
(C) Quels sont les entier entre $0$ et $100$ congrus à $6$ modulo $18$
et à $15$ modulo $27$ ?
(D) Quels sont les entier entre $0$ et $9000$ congrus à $18$
modulo $91$ et à $24$ modulo $105$ ?
%
%
%
\exercice
On a $561 = 3\times 11\times 17$.
(1) Montrer que $n^{561} \equiv n \pmod{3}$ pour tout entier $n$, et
de même $\mathop{\mathrm{mod}} 11$ et $\mathop{\mathrm{mod}} 17$.
(Indication : la réponse à cette question doit faire intervenir le
nombre $560$ et \emph{non pas} la factorisation de $561$ donnée
ci-dessus.)
(2) En déduire que $n^{561} \equiv n \pmod{561}$ pour tout entier $n$.
%
%
%
\end{document}
|
