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