\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}%ATTENTION codage en utf8 !
\usepackage{fourier}
\usepackage[scaled=0.875]{helvet}
\renewcommand{\ttdefault}{lmtt}
\usepackage{amsmath,amssymb,makeidx,stmaryrd}
\usepackage[normalem]{ulem}
\usepackage{fancybox}
\usepackage{tabularx}
\usepackage{ulem}
\usepackage{dcolumn}
\usepackage{textcomp}
\usepackage{stmaryrd}
\usepackage{lscape}
\newcommand{\euro}{\eurologo{}}
\usepackage[dvips]{color}
\usepackage{pstricks,pst-plot,pst-text,pst-tree}
\usepackage[left=3.5cm, right=3.5cm, top=2cm, bottom=3cm]{geometry}
\newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\theenumi}{\textbf{\arabic{enumi}}}
\renewcommand{\labelenumi}{\textbf{\theenumi.}}
\renewcommand{\theenumii}{\textbf{\alph{enumii}}}
\renewcommand{\labelenumii}{\textbf{\theenumii.}}
\def\Oij{$\left(\text{O},~\vect{\imath},~\vect{\jmath}\right)$}
\def\Oijk{$\left(\text{O},~\vect{\imath},~\vect{\jmath},~\vect{k}\right)$}
\def\Ouv{$\left(\text{O},~\vect{u},~\vect{v}\right)$}
\usepackage{fancyhdr}
\usepackage{hyperref}
\hypersetup{%
pdfauthor = {APMEP},
pdfsubject = {CAPES 2015 },
pdftitle = {Épreuve 2 avril  2015},
allbordercolors = white,
pdfstartview=FitH}
\usepackage[french]{babel}
\usepackage[np]{numprint}
\begin{document}
\setlength\parindent{0mm}
\rhead{\textbf{A. P{}. M. E. P{}.}}
\lhead{\small Épreuve 2}
\lfoot{\small{CAPES externe 2015}}
\rfoot{\small{}}
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}

\begin{center}

{\Large \textbf{CAPES externe session 2015 Épreuve 2}}

\vspace{0,5cm}

{\Large \textbf{Problème \no 1}}
\end{center}

\vspace{0,5cm}

\emph{Notations}

On note $\N$ l'ensemble des entiers naturels, $\N*$ l'ensemble des entiers naturels non nuls et $\Z$ l'ensemble des entiers relatifs.

\medskip

Soient $p$ et $q$ deux entiers relatifs tels que $p \leqslant q$, on note $\llbracket p,~q\rrbracket$ l'ensemble des entiers relatifs $k$ tels que $p \leqslant k \leqslant q$.

\medskip

\textbf{Préambule}

\medskip

Ce problème a pour objet l'étude de deux méthodes de chiffrement,

\medskip

À chaque lettre de l'alphabet est associé Un unique entier compris entré 0 et 25 de la façon suivante :

à la lettre A est associé 0, à la lettre B est associé 1, \ldots , à la lettre Z est associé 25. Cet entier est appelé rang de la lettre.

\bigskip

\textbf{Partie A. - Un chiffrement monographique}

\medskip

L'objectif de cette partie est de démontrer les théorèmes de Bézout, puis de Gauss, et de mettre en œuvre ces théorèmes dans le chiffrement proposé.

\medskip

\textbf{I.} Soient $a$ et $b$ des entiers relatifs non nuls.

\begin{enumerate}
\item Montrer que s'il existe des entiers relatifs $u$ et $v$ tels que $au + bu = 1$, alors $a$ et $b$ sont premiers entre eux.
\item On veut à présent prouver que la réciproque de cette propriété est vraie. On suppose
que $a$ et $b$ sont premiers entre eux et on considère l'ensemble $\mathcal{E}$ des entiers relatifs de la forme $au + bu$ où $u$ et $v$ sont des entiers relatifs.
	\begin{enumerate}
		\item Montrer que l'ensemble $\mathcal{E} \cap \N^{*}$   admet un plus petit élément, que l'on notera $n_0$.
		\item Démontrer que le reste de la division euclidienne de $a$ (respectivement $b$) par $n_0$ vaut $0$.
		\item Conclure.
	\end{enumerate}
\item Énoncer le théorème ainsi démontré.
\end{enumerate}

\textbf{II.} À l'aide du théorème précédent, démontrer que, pour tous les entiers relatifs non nuls $a,\: b$ et $c$, si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

\textbf{III.} Chiffrement lettre à lettre

\begin{enumerate}
\item Un exemple. -- Dans cette question, on décide de coder chaque lettre d'un mot par un
nombre $y$ défini comme suit : \emph{si $x$ est le rang de la lettre à coder, $y$ est le reste de la division euclidienne de $58x$ par $369$}.
	\begin{enumerate}
		\item Coder le mot GAUSS.
		\item Proposer une activité de classe sur tableur permettant, à partir du codage des 26
lettres de l'alphabet de décoder le mot de 6 lettres qui se cache derrière la suite de
nombres :

\[290\quad 232\quad 248\quad 327\quad 0\quad 364\]

(Dans cette question, le décodage effectif n'est pas demandé; il le sera à la question
\textbf{III. 3. c.})
	\end{enumerate}
\item Principe général du chiffrement lettre à lettre. -- On se donne un couple d'entiers naturels $(n,~e)$ vérifiant les conditions suivantes :
	
\setlength\parindent{5mm}
\begin{itemize}
\item[$\bullet~~$] L'entier $n$ est supérieur ou égal à 26.
\item[$\bullet~~$] Les entiers $n$ et $e$ sont premiers entre eux.
\end{itemize}
\setlength\parindent{0mm} 
 
Chaque lettre est alors codée de la façon suivante : \emph{si $x$ est le rang de la lettre à coder, $y$ est le reste de la division euclidienne de $ex$ par $n$}. 
	\begin{enumerate}
		\item Démontrer qu'il existe un entier naturel $f$ tel que $fe \equiv 1\:\: (\text{mod}\: n)$.
		\item Démontrer que la connaissance de $f$ permet de retrouver $x$ à partir de $y$. On dit que $f$ est une clé de décodage associée à la clé de codage $(n,~e)$.
	\end{enumerate}
\item Un procédé de construction d'une clé de codage et d'une clé de décodage associée :
	
\setlength\parindent{5mm}
\begin{itemize}
\item[$\bullet~~$]On choisit quatre entiers naturels $a,\: b,\: c,$ et $d$ supérieurs ou égaux à 3.
\item[$\bullet~~$]On pose : $M = ab -1,\: e = cM + a,\: f = dM + b$ et $n = \dfrac{ef - 1}{M}$.
\end{itemize}
\setlength\parindent{0mm}

	\begin{enumerate}
		\item Vérifier que $(n,~e)$ est une clé de codage et que $f$ est une clé de décodage associée.
		\item Calculer $n,\: e$, et $f$ lorsque $a = 3,\: b = 4,\: c = 5$ et $d = 6$.
		\item Un mot de 6 lettres a été codé à l'aide de la clé définie à la question précédente :

\[290\quad 232\quad 248\quad 327\quad 0\quad 364\]

Décoder ce mot.
	\end{enumerate}
\item Ensemble des clés de décodage associées à une clé de codage donnée. --

On revient au cas général où $n$ est un entier naturel supérieur ou égal à 26 et e un entier naturel
premier avec n et on se propose de déterminer l'ensemble des couples $(u,~v)$ d'entiers
relatifs tels que $nu + ev = 1$.

L'algorithme d'Euclide, qui permet de déterminer le PGCD de deux entiers naturels non
nuls, assure l'existence d'un entier naturel $N$ strictement supérieur à 1 et de deux suites
finies $\left(r_k\right)_{k \in \llbracket 1,~N \rrbracket}$ et $\left(q_k\right)_{k \in \llbracket 1,~N \rrbracket}$ telles que :

\setlength\parindent{5mm}
\begin{itemize}
\item[$\bullet~~$]La suite $\left(r_k\right)_{k \in \llbracket 1,~N \rrbracket}$ est strictement décroissante.
\item[$\bullet~~$]$r_0 = n,\: r_1 = e$  et  $r_{N+1} = 0$.
\item[$\bullet~~$]$\forall k \in  \llbracket 1,~N\rrbracket,\: r_{k-1} = r_kq_k + r_{k+1}$.
\end{itemize}
\setlength\parindent{0mm}

	\begin{enumerate}
		\item Que vaut $r_N$ ?
		\item Démontrer qu'il existe deux suites d'entiers relatifs $\left(u_k\right)_{k \in \llbracket 0,~N \rrbracket}$ et $\left(v_k\right)_{k \in \llbracket 0,~N \rrbracket}$ vérifiant,
pour tout $k \in \llbracket 0,~N \rrbracket$,

\[r_k = nu_k +ev_k.\]

		\item En déduire une clé de décodage associée à la clé de codage $(n,~e)$.
		\item On met en oeuvre cette méthode à l'aide d'un tableur à partir de la clé de codage (369,~58) :
		\begin{center}
\begin{tabularx}{0.8\linewidth}{|c|*{4}{>{\centering \arraybackslash}X|}}\hline
&A&B&C&D\\ \hline
1&$r$&$q$&$u$&$v$\\ \hline
2&369&&1 &0\\ \hline
3&58&6&0&1\\ \hline
		4&21&2&1&$- 6$\\ \hline
		5&16&1&$- 2$&13\\ \hline
\end{tabularx}
\end{center}

Quelle formule a-t-on saisie dans la cellule C4 pour que, tirée en bas et à droite, elle
permette de déterminer les valeurs des termes des deux suites $\left(u_k\right)$ et $\left(v_k\right)$ ?

		\item Déterminer un couple $(u,~v)$ d'entiers relatifs tels que 369u + 58v = l et une clé de décodage associée à la clé de codage (369,~58).
		\item Déterminer l'ensemble des couples $(u,~ v)$ d'entiers relatifs tels que 

$369u + 58v = 1$ et l'ensemble des clés de décodage associées à la clé de codage (369,~58).
	\end{enumerate}
\end{enumerate}

\bigskip

\textbf{Partie B. - Chiffrement de Hill}

\medskip

L'objectif de cette partie est de retrouver quelques résultats sur les matrices carrées d'ordre 2 à coefficients réels, puis de les appliquer au chiffrement de Hill.

\medskip

La matrice nulle d'ordre 2 est notée $O_2$ et la matrice unité d'ordre 2 est notée $I_2$.

\medskip

Pour tout entier naturel n non nul, si P et Q sont deux matrices carrées d'ordre 2 dont les coefficients respectifs $p_{i,~j}$ et $q_{i,~j}$ appartiennent à $\Z$, on dit qu'elles sont congrues modulo $n$ et on note
$P \equiv Q (\text{mod}\: n)$ lorsque
\[\forall (i,~j) \in \{1,~2\}, \quad p_{i,~j} \equiv q_{i,~j} (\text{mod}\: n).\]

De même, on dit que les vecteurs colonnes à coefficients dans $Z$

\[X = \begin{pmatrix}x\\y\end{pmatrix}\quad \text{et}\quad X' = \begin{pmatrix}x'\\y'\end{pmatrix}\]

sont congrus modulo $n$ et on note $X \equiv X' (\text{mod}\: n)$ lorsque $x \equiv x' (\text{mod} \:n)$ et $y \equiv y'(\text{mod}\: n)$.

Dans toute cette partie, la matrice $A$ est définie par
$A = \begin{pmatrix}a &b\\ c&d\end{pmatrix}$
où $a,\: b,\: c$ et $d$ désignent quatre réels.

\textbf{I. Questions de cours}

\begin{enumerate}
\item Donner la définition d'une matrice inversible et démontrer l'unicité de son inverse.
\item Établir que $A^2 - (a + d)A + (ad - bc)I_2 = O_2$.
\item Démontrer que la matrice $A$ est inversible si et seulement si $ad - bc \ne 0$.
\end{enumerate}

\textbf{II.} Dans cette question, on suppose que $a,\: b,\: c$ et $d$ sont des entiers relatifs.

\begin{enumerate}
\item Donner un exemple de matrice inversible à coefficients dans $\Z$, mais dont l'inverse n'a pas tous ses coefficients dans $\Z$.
\item Énoncer une condition suffisante pour que la matrice $A$ soit inversible et que son inverse $A^{-1}$ soit à coefficients dans $\Z$.
\item Quelle notion mathématique (qui ne figure pas dans les programmes de lycée) permet
de prouver que cette condition est nécessaire ? Proposer une démonstration du résultat.
\end{enumerate}

\textbf{III.} La méthode étudiée ci-après utilise un chiffrement par blocs de 2 lettres pour coder un mot comportant un nombre pair de lettres :

\setlength\parindent{5mm}
\begin{itemize}
\item[$\bullet~~$]On choisit quatre entiers naturels non nuls $a,\: b,\: c$ et $d$.
\item[$\bullet~~$]On note $x$ le rang de la première lettre du bloc et $y$ le rang de la deuxième lettre du bloc.

\item[$\bullet~~$]On définit les entiers $x'$ et $y'$ de la manière suivante :

\[(S)\quad \left\{\begin{array}{l c l}
x'& =&ax + by\\
y'& =&cx + dy
\end{array}\right.\]

\item[$\bullet~~$]Le rang de la première lettre du bloc codé est le reste modulo 26 de $x'$ ; le rang de la deuxième lettre du bloc codé est le reste modulo 26 de $y'$.
\end{itemize}
\setlength\parindent{0mm}

Un tel chiffrement est dit digraphique.

\medskip

\begin{enumerate}
\item Traduire le système (5) par une relation matricielle à l'aide de la matrice A qui est appelée matrice de codage.
\item On donne : $a = 4,\: b = 3,\: c = 5$ et $d = 4$.
	\begin{enumerate}
		\item Coder le mot BEZOUT.
		\item En détaillant les étapes, décoder le mot suivant :

\[S\quad F\quad X\quad M\quad O\quad J\]

	\end{enumerate}
\item On donne à présent a = 3, b = 2, c = 1 et d = 3. On souhaite décoder le mot suivant :
	
	\[A\quad K\quad X\quad O\quad U\quad E\quad V\quad H\quad D\quad  L\]
	
	\begin{enumerate}
		\item Démontrer qu'il existe un unique entier $u$ compris entre 0 et 2.5 tel que
		\[7u \equiv 1 \quad (\text{mod} \:26).\]

		\item On note $A$ la matrice de codage associée aux entiers $a,\: b,\: c$ et $d$. Déterminer une matrice $B$, à coefficients entiers relatifs, telle que $uBA \equiv I_2\:\: (\text{mod}\: 26)$.
		\item Décoder le mot en détaillant la démarche pour le premier bloc de deux lettres.
	\end{enumerate}
\item À quelle condition sur $a,\: b,\: c$ et $d$ peut-on décoder tout mot comportant un nombre pair de lettres ?
\end{enumerate}

\vfill

\begin{flushright}\textbf{Tournez la page S. V. P.}\end{flushright}

\newpage

\begin{center}
\textbf{\large Problème \no 2}
\end{center}

Notations

On note $\N$ l'ensemble des entiers naturels et $\N^{*}$ l'ensemble des entiers naturels non nuls.

\medskip

Soient $p$ et $q$ deux entiers relatifs tels que $p \leqslant q$, on note $\llbracket p,~ q\rrbracket$ l'ensemble des entiers relatifs $k$ tels que $p \leqslant  k \leqslant q$.

\medskip

\textbf{Partie A}

\medskip

Une urne contient des boules rouges et des boules noires. On désigne par $n$ un entier naturel non nul et on considère l'expérience aléatoire consistant à effectuer $n$ tirages avec remise. 

On attribue à chaque tirage d'une boule noire (échec) la valeur $0$ et à chaque tirage d'une boule rouge (succès) la valeur 1. On peut modéliser cette expérience à l'aide d'un arbre comportant $2^n$ chemins. Ces chemins sont des $n$-uplets dont chaque composante appartient à l'ensemble $\{0,~ 1\}$. Par exemple, si
$n = 4$, un des $2^4 = 16$ chemins est (0,~0,~1,~0).

\medskip

\textbf{I.} On suppose dans cette question que $n = 4$.

\medskip

\begin{enumerate}
\item Écrire la liste des 16 chemins.
\item Parmi ces chemins, combien y en a-t-il qui contiennent exactement 2 fois l'élément 1 ?
\item Parmi les chemins contenant exactement 2 fois l'élément l, combien yen a-t-il contenant
1 à la première place ? À la deuxième place ? À la troisième place ? À la quatrième
place ?
\end{enumerate}

\textbf{II.} On revient au cas général où $n \in \N^{*}$ et on se donne $k \in \llbracket 0,~ n\rrbracket$.

\emph{Dans les questions $II. 1, II. 2$ et $II. 3$, pour tout entier $p \in \llbracket 0,~ n\rrbracket$, l'entier $\binom{n}{p}$ est défini comme au lycée : il s'agit donc du nombre de chemins de l'arbre correspondant à $n$ tirages et réalisant exactement $p$ succès. En particulier ; on n'aura pas recours dans ces trois questions à l'expression
des coefficients binomiaux à l'aide de factorielles.}

\medskip

\begin{enumerate}
\item Démontrer que $\displaystyle\binom{n}{k} = \displaystyle\binom{n}{n - k}$.
\item On suppose dans cette question que $k \ne 0$. En exprimant de deux manières différentes
le nombre de $(n + 1)$-uplets contenant $k$ fois l'élément 1, démontrer que

\[\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}.\]

\item Pour $1 \leqslant  k \leqslant n$, on se propose de démontrer l'égalité

\[k\binom{n}{k} = n\binom{n-1}{k-1}.\]

On considère une matrice $A$ à $n$ colonnes dont chacune des $\binom{n}{k}$ lignes est l'un des chemins conduisant à $k$ succès et $n - k$ échecs.
	\begin{enumerate}
		\item Calculer la somme des éléments d'une ligne de la matrice.
		\item Soit $j \in  \llbracket 1,~n\rrbracket$. Que représente la somme des éléments de la $j$-ème colonne de la matrice $A$ ?
		\item Conclure.
	\end{enumerate}
\item Dans l'enseignement supérieur, on définit, pour tout entier $p \in  \llbracket 0,~n\rrbracket$, l'entier $\binom{n}{p}$ comme étant le nombre de parties à $p$ éléments d'un ensemble à $n$ éléments.
	\begin{enumerate}
		\item Justifier la cohérence de cette définition avec celle qui est donnée au lycée. 
		\item Démontrer que $\displaystyle\binom{n}{k} = \dfrac{n!}{k!(n - k)!}$.
		\item Retrouver par le calcul les résultats des questions \textbf{II. 2} et \textbf{II. 3}.
	\end{enumerate}
\end{enumerate}

\textbf{III.} On note $\theta$ la proportion de boules rouges dans l'urne et $X$ la variable aléatoire égale au nombre de boules rouges (succès) obtenues à l'issue des $n$ tirages.

Identifier la loi de $X$ et, en utilisant la question \textbf{II. 3} ainsi que la formule du binôme, calculer son espérance.

\textbf{Partie B}

\medskip

Un point se déplace sur un axe gradué. Il se trouve au départ à l'origine et son déplacement à
chaque étape est déterminé par le résultat du lancer d'une pièce équilibrée :

\setlength\parindent{5mm}
\begin{itemize}
\item[$\bullet~~$] Si on obtient pile, son abscisse augmente de 1.
\item[$\bullet~~$] Si on obtient face, son abscisse diminue de 1.
\end{itemize}
\setlength\parindent{0mm}

On note $D_n$ le nombre de fois où la pièce est tombée sur pile au cours des $n$ premiers lancers et $X_n$ l'abscisse du point à l'issue du $n$-ième lancer.

\medskip

\textbf{I.}

\begin{enumerate}
\item Donner la loi de la variable aléatoire $X_n$.
\item Reconnaître la loi de la variable aléatoire $D_n$.
\item Exprimer $X_n$ à l'aide de $D_n$.
\item Calculer l'espérance de $X_n$. Interpréter le résultat.
\end{enumerate}

\textbf{II.}
 
\begin{enumerate}
\item Que vaut la probabilité $P\left(X_n = 0\right)$ lorsque $n$ est impair?
\item Calculer la probabilité $P\left(X_{2n} = 0\right)$.
\end{enumerate}

\textbf{III.}
 
\begin{enumerate}
\item L'algorithme suivant utilise une fonction \texttt{alea}() qui renvoie à chaque appel un nombre aléatoire selon la loi uniforme sur l'intervalle [0~;~1] :
\begin{center}

\begin{tabular}{>{\texttt}l}
 entrer($n$)\\
$x \leftrightarrow 0$\\
pour $k$ allant de $1$ à $n$\\
\hspace{1cm}si \texttt{alea}() $> 0,5$ alors\\
\hspace{1.7cm} $x\leftrightarrow x+1$\\
\hspace{1cm}sinon\\
\hspace{1.7cm} $x\leftrightarrow x - 1$\\
\hspace{1cm}finsi\\
finpour\\
retourner$(x)$\\

\end{tabular}
\end{center}

À quoi correspond la valeur renvoyée par cet algorithme ?
\item Écrire un deuxième algorithme, obtenu en modifiant l'algorithme donné, de façon à ce
qu'il renvoie le nombre de passages à l'origine à l'issue de $n$ lancers.
\item Écrire un troisième algorithme, obtenu en modifiant l'algorithme donné, de façon à ce
qu'il renvoie la fréquence d'apparition de l'événement $X_n = 0$ au cours de la répétition
de \np{1000} séries de $n$ lancers.
\item Comment un professeur peut-il exploiter ces algorithmes devant une classe ?
\end{enumerate}

\textbf{IV.} Soit $n \in  \N^{*}$. Dans cette question, on s'intéresse à la position du point à l'issue de $2n$ lancers et au nombre de passages à l'origine entre le premier et le $2n$-ième lancer.

\medskip

\begin{enumerate}
\item Expliquer pourquoi, à l'issue de ces $2n$ lancers, l'abscisse du point ne peut être qu'un
entier relatif pair compris entre $-2n$ et $2n$.
\item Soit $k \in \llbracket 0~;~\rrbracket$. Calculer la probabilité qu'à l'issue de ces $2n$ lancers, l'abscisse du point soit égale à $2k$.
\item On note $C_n$ la variable aléatoire égale au nombre de passages à l'origine entre le premier et le $2n$-ième lancer.

Calculer l'espérance E$\left(C_n\right)$ de la variable aléatoire $C_n$ et montrer par récurrence sur $n$ que, pour tout entier $n \geqslant 1$,

\[\text{E}\left(C_n\right) = \dfrac{2n + 1}{4^n}\binom{2n}{n}  - 1.\]

On pourra utiliser la variable aléatoire $\Omega_k$ égale à 1 si l'abscisse du point à l'issue du $k$-ième lancer est nulle et égale à $0$ sinon.
\end{enumerate}
\end{document}