\documentclass[a4paper,11pt,french]{article}
\linespread{1}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Définitions de la feuille d'exercices

\newcommand{\typedoc}{Exercices sur les matrices et sur l'arithm\'etiques}          %%%%%%%%%%%%%%% 1ere ligne du titre de la feuille
\newcommand{\Ch}{ R\'evision pour le bac}		   %%%%%%%%%%%%%%%% 2eme ligne et en haut à droite après	
\newcommand{\ch}{R\'evisions}               %%%%%%%%%%%%%%% En haut à gauche (numero chapitre)
\newcommand{\Cl}{T$^\text{ale}$S}
\newcommand{\Annee}{2013-2014}

\newcommand{\serie}{Scientifique}
\newcommand{\num}{0}	
\newcommand{\tps}{2h}	



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%		Packages
%\usepackage[french,lined,boxed,commentsnumbered]{algorithm2e}

\input macrodwicky.tex
\geometry{verbose,letterpaper,tmargin=1.8cm,bmargin=1.8cm,lmargin=1.5cm,rmargin=1.5cm}
\renewcommand{\arraystretch}{1.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Début
\begin{document}


\DocDav

\vspace{1cm}

\section{Arithmétique et Matrice}
 \subsection*{Chiffrement de Hill}
\textbf{Le principe :}


On choisit quatre entiers $a$, $b$, $c$ et $d$ constituant la \textbf{clé} du chiffrement. Les lettres de l'alphabet sont codées de $0$ à $25$ grâce au tableau suivant :
A chaque lettre de l'alphabet, on associe, gr\^ace au tableau ci-dessous, un nombre entier $m$ compris entre $0$ et $25$.

\begin{tabularx}{\linewidth}{|*{13}{>{\centering \arraybackslash}X|}}\hline
A	&B&C &D&E &F&G  &H&I&J& K &L &M \\ \hline
0	&1 	&2	&3 	&4 	&5 	&6 	&7	&8 	&9 	&10 	&11 	&12\\ \hline \hline 
N	&O	&P	&Q	&R &S	& T	&U 	&V 	&W 	&X 		&Y		&Z\\ \hline 
13	&14	&15	&16	&17 &18 &19 &20	&21	&22	&23 	&24		&25\\ \hline
\end{tabularx}

 A un bloc de deux lettres correspondent un couple $(x;y)$ d'entiers compris entre $0$ et $25$. On calcule les codes du message chiffré en associant au couple $(x;y)$ le couple $(x';y')$ tel que :
$$ \left\{\begin{array}{cccc}
x'& \equiv & ax+by &(26)\\
y'&\equiv & cx+dy&(26)
\end{array}\right.$$

On souhaite chiffrer le mot DREAM.

On partage le mot en blocs de $2$ lettres : DR- EA - MA (le dernier bloc est complété au hasard).

Choisissons $a=5$, $b=7$, $c=2$ et $d=3$, le système de chiffrement est donc :
$$ \left\{\begin{array}{cccc}
x'& \equiv & 7x+3y &(26)\\
y'&\equiv & 5x+8y&(26)
\end{array}\right.$$

\begin{enumerate}
\item Chiffrer le mot DREAM.
\item On considère la matrice $A=\begin{pmatrix}
7 & 3\\
5 & 8
\end{pmatrix}$.
\begin{enumerate}
\item Montrer que la matrice $A$ est inversible puis déterminer $B$ telle que $A^{-1}=\dfrac{1}{41}B$.
\item Montrer qu'il existe un unique entier $m$ compris entre $0$ et 
$25$ tel que $41m\equiv 1[26]$.
\\
Déterminer $m$.
\item Montrer que la matrice $mB$ est une matrice vérifiant :
$$ mB\times \begin{pmatrix}
x'\\
y'
\end{pmatrix}\equiv \begin{pmatrix}
x\\
y
\end{pmatrix} [26]$$
(\textit{Cette congruence sur les matrices colonnes signifie la congruence des coefficients de chaque ligne.)}
\item Déterminer alors quatre entiers $A$, $B$, $C$ et $D$ compris entre $0$ et $25$ tels que :
$$\begin{pmatrix}
A & B\\
C & D
\end{pmatrix} \times \begin{pmatrix}
x'\\
y'
\end{pmatrix}\equiv \begin{pmatrix}
x\\
y
\end{pmatrix} [26]$$
\item En déduire un algorithme de décodage de ce chiffrement de  Hill et déchiffrer le message :
$$ \og XZEQGCXWCO\fg$$
\end{enumerate}
\item Dans le chiffrement précédent, quelle condition particulière sur $41$ et $26$ permet de répondre à la question $2 .(b)$
\item On souhaite adopter le chiffrement de Hill donné par le procédé :
$$\left\{\begin{array}{cccc}
x'& \equiv & 6x+2y &(26)\\
y'&\equiv & 7x+3y&(26)
\end{array}\right. $$
Soit $A$ la matrice associé à ce chiffrement.
Calculer le PGCD de $det A$ et de $26$.
\item Comparer les produits $\begin{pmatrix}
6 & 2\\
7 & 3
\end{pmatrix}\times \begin{pmatrix}
x +13\\
y+13\\
\end{pmatrix}$ avec $\begin{pmatrix}
6 & 2\\
7 & 3
\end{pmatrix}\times \begin{pmatrix}
x \\
y\\
\end{pmatrix}$. Le procédé de codage est-il satisfaisant ? Justifier.
\end{enumerate}

\subsection*{Antilles Guyanne 2013}
\begin{exoi}
\partieBac{}

\medskip
 
On considère l'algorithme suivant :

\begin{center}
\begin{tabular}{|l|}\hline
A et X sont des nombres entiers\\
Saisir un entier positif A\\
Affecter à X la valeur de A\\ 
Tant que X supérieur ou égal à 26\\
\hspace{1.25cm}Affecter à X la valeur X - 26\\
Fin du tant que\\ 
Afficher X\\ \hline
\end{tabular}
\end{center}
 
\begin{enumerate}
\item Qu'affiche cet algorithme quand on saisit le nombre 3 ? 
\item Qu'affiche cet algorithme quand on saisit le nombre 55 ? 
\item Pour un nombre entier saisi quelconque, que représente le résultat fourni par cet algorithme?
\end{enumerate}

\bigskip
 
\partieBac{}
\medskip
 
On veut coder un bloc de deux lettres selon la procédure suivante (détaillée en quatre étapes) :

\medskip
 
$\bullet~~$\textbf{Étape 1} : chaque lettre du bloc est remplacée par un entier en utilisant le tableau ci-dessous: 

\medskip
\begin{tabularx}{\linewidth}{|*{13}{>{\centering \arraybackslash}X|}}\hline
A	&B	&C	&D	&E	&F	&G	&H	&I	&J	&K	&L	&M\\\hline
0	&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12\\\hline \hline
N	&O	&P	&Q	&R	&S	&T	&U	&V	&W	&X	&Y	&Z \\ \hline 
13	&14	&15	&16	&17	&18	&19	&20	&21	&22	&23	&24	&25\\\hline 
\end{tabularx}
\medskip

\index{matrice}

On obtient une matrice colonne $\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}$ où $x_{1}$ correspond à la première lettre du mot et $x_{2}$ correspond à la deuxième lettre du mot.
 
$\bullet~~$\textbf{Étape 2} : $\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}$ est transformé en $\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}$ tel que 

\[\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix} = \begin{pmatrix}3&1\\5&2\end{pmatrix}\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}\]

La matrice $C = \begin{pmatrix}3&1\\5&2\end{pmatrix}$ est appelée la matrice de codage.
 
$\bullet~~$\textbf{Étape 3} : $\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}$ est transformé en $\begin{pmatrix}z_{1}\\z_{2}\end{pmatrix}$ tel que
 
\[\left\{\begin{array}{l c l c l c l l}
z_{1}& \equiv& y_{1}\: (26)& \text{avec}\:\: 0 &\leqslant& z_{1}&\leqslant& 25\\
z_{2}& \equiv& y_{2}\: (26)& \text{avec}\:\: 0 &\leqslant& z_{2}&\leqslant& 25
\end{array}\right.\] 

$\bullet~~$\textbf{Étape 4} : $\begin{pmatrix}z_{1}\\z_{2}\end{pmatrix}$ est transformé en un bloc de deux lettres en utilisant le tableau de correspondance donné dans l'étape 1.

\begin{center}
\begin{tabular}{|l} 
\textbf{Exemple} : \\
RE $\to \begin{pmatrix}17\\4\end{pmatrix}\to \begin{pmatrix}55\\93\end{pmatrix} \to \begin{pmatrix}3\\15\end{pmatrix}\to $ DP\\
Le bloc RE est donc codé en DP\\
\end{tabular}
\end{center}
 
 \begin{enumerate}
\item Justifier le passage de $\begin{pmatrix}17\\4\end{pmatrix}$ à $\begin{pmatrix}55\\93\end{pmatrix}$ puis à  $\begin{pmatrix}3\\15\end{pmatrix}$.
\item Soient $x_{1},\:x_{2},\:x'_{1},\:x'_{2}$ quatre nombres entiers compris entre 0 et 25 tels que $\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}$ et $\begin{pmatrix}x'_{1}\\x'_{2}\end{pmatrix}$ sont transformés lors du procédé de codage en $\begin{pmatrix}z_{1}\\z_{2}\end{pmatrix}$. 	
	\begin{enumerate}
		\item Montrer que $\left\{\begin{array}{l c l}
		3x_{1}+ x_{2} & \equiv& 3x'_{1} + x'_{2}  \quad (26)\\
5x_{1}+ 2x_{2}&\equiv&5x'_{1} + 2x'_{2} \quad (26).
\end{array}\right.$ 
		\item En déduire que $x_{1} \equiv  x'_{1}\quad  (26)$ et $x_{2} \equiv  x'_{2} \quad (26)$ puis que $x_{1} = x'_{1}$ et $x_{2} = x'_{2}$.
	\end{enumerate} 
\item On souhaite trouver une méthode de décodage pour le bloc DP : 
	\begin{enumerate}
		\item Vérifier que la matrice $C' = \begin{pmatrix}2&- 1\\- 5&3\end{pmatrix}$ est la matrice inverse de $C$. 
		\item Calculer $\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}$ tels que $\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix} = \begin{pmatrix}2&- 1\\- 5&3\end{pmatrix}\begin{pmatrix}3\\15\end{pmatrix}$. 
		\item Calculer $\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}$ 	tels que $\left\{\begin{array}{l c l}
x_{1}&\equiv &y_{1}\quad (26)\:\: \text{avec}\:0 \leqslant x_{1} \leqslant 25\\
x_{2}&\equiv &y_{2}\quad (26)\:\: \text{avec}\:0 \leqslant x_{2} \leqslant 25\\
\end{array}\right.$ 
		\item Quel procédé général de décodage peut-on conjecturer ?
	\end{enumerate} 
\item Dans cette question nous allons généraliser ce procédé de décodage.
 
On considère un bloc de deux lettres et on appelle $z_{1}$ et $z_{2}$ les deux entiers compris entre 0 et 25 associés à ces lettres à l'étape 3. On cherche à trouver deux entiers $x_{1}$ et $x_{2}$ compris 
entre 0 et 25 qui donnent la matrice colonne $\begin{pmatrix}z_{1}\\z_{2}\end{pmatrix}$ par les étapes 2 et 3 du procédé de codage.
 
Soient $y'_{1}$ et $y'_{2}$ tels que $\begin{pmatrix}y'_{1}\\y_{2}\end{pmatrix} = C' \begin{pmatrix}z_{1}\\z_{2}\end{pmatrix}$ où $C'	=  \begin{pmatrix}2&- 1\\- 5&3\end{pmatrix}$.

Soient $x_{1}$ et $x_{2}$, les nombres entiers tels que $\left\{\begin{array}{l c l}
x_{1}&\equiv & y'_{1} \quad (26) \: \text{avec}\:0 \leqslant x_{1}\leqslant 25\\  
x_{2}&\equiv &y'_{2} \quad (26) \: \text{avec}\:0 \leqslant x_{2}\leqslant 25  
\end{array}\right.$

Montrer que $\left\{\begin{array}{l c l}
3x_{1}+ x_{2} & \equiv& z_{1}  \quad (26)\\
5x_{1}+ 2x_{2}&\equiv&z_{2} \quad (26).
\end{array}\right.$.
 
Conclure. 
\item Décoder QC. 
\end{enumerate}
\end{exoi}
\pagebreak
\section{Matrice}

\begin{exoi}
\begin{enumerate}
\item Soit $A=\begin{pmatrix}
2 & 3 \\
4 & 5
\end{pmatrix}$ et $B=\begin{pmatrix}
-2,5 & 1,5\\
2 & -1
\end{pmatrix}$. Montrer que $B$ est la matrice inverse de $A$.
\item Soit $M=\begin{pmatrix}
3 & 3\\
4 & 6
\end{pmatrix}$ et $N=\begin{pmatrix}
1 \\ 1
\end{pmatrix}$.
\\
Déterminer la matrice colonne $X$ vérifiant $MX=X+N$
\end{enumerate}
\end{exoi}

\begin{exoi}
Soit la matrice carrée $A=\begin{pmatrix}
5 & 1\\
3 & 4
\end{pmatrix}$
\begin{enumerate}
\item Montrer que $A$ est une matrice inversible.
\item Déterminer la matrice inverse de $A$.
\item Vérifier votre résultat à l'aide de la calculatrice.
\end{enumerate}
\end{exoi}


\begin{exoi}
Soit la matrice $A=\begin{pmatrix}
6,25 & -9\\
4,5 & -6,5
\end{pmatrix}$
\begin{enumerate}
\item Vérifier que la matrice $A$ est égale au produit des matrices $P\times D\times P^{-1}$ où $D$ désigne la matrice diagonale $D=\begin{pmatrix}
0,25 & 0 \\
0 & -0,5
\end{pmatrix}$ et où $P$ désigne la matrice inversible $P=\begin{pmatrix}
3 & 4\\
2 & 3
\end{pmatrix}$
\item En déduire les coefficients de la matrice $A^n$ pour tout $n\geq 0$.
\end{enumerate}
\end{exoi}

\begin{exoi}
Soit $A = \begin{pmatrix}
1& 2 & 2\\
2 & 1 & 2\\
2 & 2 & 1
\end{pmatrix}$
On souhaite calculer $A^n$ pour $n$ entier naturel.
\begin{enumerate}
\item Calculer les premières puissances de $A$ à l'aide d'un logiciel ou d'une calculatrice. Quelle forme particulière remarque-t-on pour ces matrices ?
\item \begin{enumerate}
\item Écrire $A$ sous la forme $2B -I_3$, où $I_3$ est la matrice identité d'ordre $3$ et $B$ une matrice à préciser.
\item Montrer que $B^2 = 3B$.
\item En déduire $A^2$ en fonction de $B$ et $I_3$, puis $A^3$.
\end{enumerate}
\item Démontrer par récurrence que pour tout $n$ de $\N^*$ on a :
$$ A^n=(-1)^n I_3+\dfrac{1}{3}\left(5^n-(-1)^n\right)B$$.
\item Écrire $A_n$ avec tous ces coefficients en fonction de $n$ pour $n\in \N^*$.
\end{enumerate}
\end{exoi}
\pagebreak
\begin{exoi}
Un complexe industriel est constitué d'une centrale électrique au fioul et d'une raffinerie de pétrole.
La centrale utilise pour 1 $\euro$ d'électricité produite : 
\begin{itemize}
\item $0.10 \euro$ de sa propre consommation d'électricité ;
\item $0.40\euro$ de fioul produit par la raffinerie.
\end{itemize} 
La raffinerie utilise pour 1 $\euro$ de fioul produit :
\begin{itemize}
\item $0,30\euro $ d'électricité produite par la centrale ;
\item $0,20\euro $ de sa propre production de fioul.
\end{itemize}

Ces consommations internes empêchent de vendre la totalité des productions d'électricité et de fioul.

\Cadre[But]{L'objectif de l'exercice est d'évaluer les productions totales d'électricité et de fioul pour satisfaire une commande
de $72000 \euro$ d'électricité et de $24000 \euro$ de fioul.}


\begin{enumerate}
\item Notons respectivement $p_e$ et $p_f$ les productions totales (en euros) d'électricité et de fioul. On obtient la matrice
colonne des productions $\begin{pmatrix}
p_e\\
p_f
\end{pmatrix}$.

On note $c_e$ et $c_f$  respectivement les consommations internes (en euros) d'électricité et de fioul. 
On obtient la matrice colonne des consommations internes 
$\begin{pmatrix}
c_e\\
c_f
\end{pmatrix}$.

Vérifier que $C=LP$ avec $L\begin{pmatrix}
0.1 & 0.3\\
0.4 & 0.2
\end{pmatrix}$
\item Supposons que la production totale est de $80000\euro$ d'électricité et de $50000\euro$ de fioul.
\begin{enumerate}
\item En utilisant la question 1., calculer la matrice des consommations internes.
\item Déduisez-en les productions nettes, c'est-à-dire disponibles pour la vente.
\item Cet exemple permet-il de répondre à la question initiale posée dans l'énoncé ?
\end{enumerate}
\item Il s'agit désormais de répondre à la question posée. Notons $I_2=\begin{pmatrix}
1 & 0\\
0 & 1
\end{pmatrix}$
\begin{enumerate}
\item La matrice associée à la production nette visée est notée $N$ et donc $N =\begin{pmatrix}
72000\\
24000
\end{pmatrix}$.

Justifier que la matrice $P$ répondant à la question initiale posée vérifie l'égalité $(I_2-L)P = N$.
\item Vérifiez que $I_2-L=\begin{pmatrix}
0.9 & -0.3\\
-0.4 & 0.8
\end{pmatrix}$.

On note $A=\dfrac{1}{6} \begin{pmatrix}
8 & 3\\
4 & 9
\end{pmatrix} $. Calculer $A(I_2-L)$. Que représente la matrice $A$ pour la matrice $(I_2-L)$ ?
\item En déduire la matrice $P$ cherchée.
\end{enumerate}
\end{enumerate}
\end{exoi}

\pagebreak


\begin{exoi}\hfill \textbf{Pondichéry 2014}\\
Chaque jeune parent utilise chaque mois une seule marque de petits pots pour bébé. Trois marques X, Y et Z se partagent le marché. Soit $n$ un entier naturel.
 
\begin{tabular}{l l}
On note :& $X_{n}$ l'évènement \og la marque X est utilisée le mois $n$ \fg,\\ 
&$Y_{n}$ l'évènement \og la marque Y est utilisée le mois $n$ \fg,\\ 
&$Z_{n}$ l'évènement \og la marque Z est utilisée le mois $n$ \fg.
\end{tabular}
 
Les probabilités des évènements $X_{n}, Y_{n}, Z_{n}$ sont notées respectivement $x_{n}, y_{n}z_{n}$.
 
La campagne publicitaire de chaque marque fait évoluer la répartition.

Un acheteur de la marque X le mois $n$, a le mois suivant :

\setlength\parindent{8mm}
\begin{description}
\item[ ] 50\,\% de chance de rester fidèle à cette marque,
\item[ ] 40\,\% de chance d'acheter la marque Y, 
\item[ ] 10\,\% de chance d'acheter la marque Z.
\end{description}
\setlength\parindent{0mm}
 
Un acheteur de la marque Y le mois $n$, a le mois suivant :
 
\setlength\parindent{8mm}
\begin{description}
\item[ ]30\,\% de chance de rester fidèle à cette marque,
\item[ ]50\,\% de chance d'acheter la marque X, 
\item[ ]20\,\% de chance d'acheter la marque Z.
\end{description}
\setlength\parindent{0mm}
 
Un acheteur de la marque Z le mois $n$, a le mois suivant : 

\setlength\parindent{8mm}
\begin{description}
\item[ ]70\,\% de chance de rester fidèle à cette marque,
\item[ ]10\,\% de chance d'acheter la marque X, 
\item[ ]20\,\% de chance d'acheter la marque Y.
\end{description}
\setlength\parindent{0mm}

\medskip
 
\begin{enumerate}
\item 
	\begin{enumerate}
		\item Exprimer $x_{n+1}$ en fonction de $x_{n}, y_{n}$ et $z_{n}$.
		 
On admet que : 

$y_{n+1} = 0,4x_{n} + 0,3y_{n} + 0,2z_{n}$ et que $z_{n+1} = 0,1x_{n} + 0,2y_{n} + 0,7 z_{n}$.
		\item Exprimer $z_{n}$ en fonction de $x_{n}$ et $y_{n}$. En déduire l'expression de $x_{n+1}$ et $y_{n+1}$ en fonction de $x_{n}$ et $y_{n}$.
	\end{enumerate} 
\item On définit la suite $\left(U_{n}\right)$ par $U_{n} = \begin{pmatrix}x_{n}\\y_{n}\end{pmatrix}$ pour tout entier naturel $n$. 

On admet que, pour tout entier naturel $n,\: U_{n+1} = A \times U_{n} + B$ où $A = \begin{pmatrix}0,4&0,4\\0,2&0,1\end{pmatrix}$	et $B = \begin{pmatrix}0,1\\0,2\end{pmatrix}$.

Au début de l'étude statistique (mois de janvier 2014 : $n = 0$), on estime que $U_{0} = \begin{pmatrix}0,5\\0,3\end{pmatrix}$. 

On considère l'algorithme suivant :

\begin{center}
\begin{tabularx}{0.85\linewidth}{|m{4cm}|X|}\hline 
Variables& $n$ et $i$ des entiers naturels.\\
		&$A$, $B$ et $U$ des matrices\\ \hline   
Entrée et initialisation&Demander la valeur de $n$ \\   
		&$i$ prend la valeur $0$\\ 
		&$A$ prend la valeur $\begin{pmatrix}0,4&0,4\\0,2&0,1\end{pmatrix}$\\ 
		&$B$ prend la valeur $\begin{pmatrix}0,1\\0,2\end{pmatrix}$\\ 
		&U prend la valeur $\begin{pmatrix}0,5\\0,3\end{pmatrix}$\\ \hline 
Traitement &Tant que $i < n$\\ 
		&\hspace{0,4cm}$U$ prend la valeur $A \times U + B$\\ 
		&\hspace{0,4cm}$i$ prend la valeur $i + 1$\\
		&Fin de Tant que \\ \hline 
Sortie 	&Afficher $U$\\ \hline
\end{tabularx}
\end{center}  

	\begin{enumerate}
		\item Donner les résultats affichés par cet algorithme pour $n = 1$ puis pour 
		
		$n = 3$. 
		\item Quelle est la probabilité d'utiliser la marque X au mois d'avril ? 

Dans la suite de l'exercice, on cherche à déterminer une expression de $U_{n}$ en fonction de $n$. 

On note $I$ la matrice $\begin{pmatrix}1&0\\0&1\end{pmatrix}$ et $N$ la matrice $I - A$.
	\end{enumerate} 
\item On désigne par $C$ une matrice colonne à deux lignes. 
	\begin{enumerate}
		\item Démontrer que $C = A \times C + B$ équivaut à $N \times C = B$.  
		\item On admet que $N$ est une matrice inversible et que $N^{-1} = \begin{pmatrix}\frac{45}{23}&\frac{20}{23}\\\frac{10}{23}&\frac{30}{23}\end{pmatrix}$. 

En déduire que $C = \begin{pmatrix}\frac{17}{46}\\\frac{7}{23}\end{pmatrix}$.
	\end{enumerate}
\item On note $V_{n}$ la matrice telle que $V_{n} = U_{n} - C$ pour tout entier naturel $n$. 
	\begin{enumerate}
		\item Montrer que, pour tout entier naturel $n,\: V_{n+1} = A \times  V_{n}$. 
		\item On admet que $U_{n} = A^n \times \left(U_{0} - C\right) + C$.
		 
Quelles sont les probabilités d'utiliser les marques X, Y et Z au mois de mai ? 
	\end{enumerate}
\end{enumerate}
\end{exoi}
\pagebreak
\begin{exoi}\hfill \textbf{Amérique du sud 2013}\\
Le gestionnaire d'un site web, composé de trois pages web numérotées de 1 à 3 et reliées entre elles par des liens hypertextes, désire prévoir la fréquence de connexion sur chacune de ses pages web.\index{matrices}

\medskip
 
Des études statistiques lui ont permis de s'apercevoir que :
 
$\bullet~~$ Si un internaute est sur la page 1, alors il ira, soit sur la page  2 avec la probabilité $\dfrac{1}{4}$, soit sur la page  3 avec la probabilité $\dfrac{3}{4}$.

$\bullet~~$ Si un internaute est sur la page 2, alors, soit il ira sur la page  1 avec la probabilité $\dfrac{1}{2}$ soit il  
restera sur la page 2 avec la probabilité $\dfrac{1}{4}$, soit il ira sur la page  3 avec la probabilité $\dfrac{1}{4}$. 

$\bullet~~$ Si un internaute est sur la page  3, alors, soit il ira sur la page  1 avec la probabilité $\dfrac{1}{2}$, soit il  
ira sur la page  2 avec la probabilité $\dfrac{1}{4}$,soit il restera sur la page  3 avec la probabilité $\dfrac{1}{4}$. 

\medskip

Pour tout entier naturel $n$, on définit les évènements et les probabilités suivants : 

$A_{n}$ : \og Après la $n$-ième navigation, l'internaute est sur la page  1 \fg{} et on note $a_{n} = P\left(A_{n}\right)$.
 
$B_{n}$ : \og Après la $n$-ième navigation, l'internaute est sur la page  2 \fg{} et on note $b_{n} = P\left(B_{n}\right)$.
 
$C_{n}$ : \og Après la $n$-ième navigation, l'internaute est sur la page  3 \fg{} et on note $c_{n} = P\left(C_{n}\right)$.

\medskip
 
\begin{enumerate}
\item Montrer que, pour tout entier naturel $n$, on a $a_{n+1} = \dfrac{1}{2} b_{n} + \dfrac{1}{2}c_{n}$. 

On admet que, de m\^eme, $b_{n+1} = \dfrac{1}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}$ et $c_{n+1} = \dfrac{3}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}$. 

Ainsi : 
\renewcommand\arraystretch{1.8}
\[\left\{\begin{array}{l c l}
a_{n+1} &=& \dfrac{1}{2} b_{n} + \dfrac{1}{2}c_{n}\\
b_{n+1} &=& \dfrac{1}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}\\
c_{n+1} &=& \dfrac{3}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}
\end{array}\right.\]
\renewcommand\arraystretch{1}
 
\item Pour tout entier naturel $n$, on pose $U_{n} = \begin{pmatrix} a_{n}\\b_{n}\\c_{n}\end{pmatrix}$.
 
$U_{0} = \begin{pmatrix} a_{0}\\b_{0}\\c_{0}\end{pmatrix}$ représente la situation initiale, avec $a_{0} + b_{0} + c_{0} = 1$.
 
Montrer que, pour tout entier naturel $n,\: U_{n+1} = MU_{n}$ où $M$ est une matrice $3 \times 3$ que l'on précisera.
 
En déduire que, pour tout entier naturel $n, U_{n} = M^nU_{0}$. 
\item Montrer qu'il existe une seule matrice colonne $U =\begin{pmatrix}x\\y\\z\end{pmatrix}$ telle que : $x + y + z = 1$ et $MU = U$. 
\item Un logiciel de calcul formel a permis d'obtenir l'expression de $M^n,\: n$ étant un entier naturel non nul :

\[M^n = \begin{pmatrix}
\frac{1}{3} + \frac{\left( \frac{- 1}{2}\right)^n \times 2}{3}&\frac{1}{3} + \frac{\left( \frac{- 1}{2}\right)^n }{- 3}&\frac{1}{3} + \frac{\left(\frac{- 1}{2}\right)^n}{- 3}\\
\frac{1}{4}&\frac{1}{4}&\frac{1}{4}\\
\frac{5}{12} + \frac{\left(-\left(\frac{- 1}{2}\right)^n\right) \times 2}{3}&\frac{5}{12} + \frac{-\left(\frac{- 1}{2}\right)^n}{-3}&\frac{5}{12} + \frac{-\left(\frac{- 1}{2}\right)^n }{- 3}
\end{pmatrix}\] 

Pour tout entier naturel $n$ non nul, exprimer $a_{n}, \: b_{n}$ et $c_{n}$ en fonction de $n$. En déduire que les suites $\left(a_{n}\right), \: \left(b_{n}\right)$ et $\left(c_{n}\right)$ convergent vers des limites que l'on précisera. 
\item Interpréter les résultats obtenus et donner une estimation des pourcentages de fréquentation du site à long terme. 
\end{enumerate}
\end{exoi}

\begin{exoi} \hfill \textbf{Métropole 2013}\\
On étudie la population d'une région imaginaire. Le 1$^{er}$ janvier 2013, cette région comptait {250000}~habitants dont 70\,\% résidaient à la campagne et 30\,\% en ville.
 
L'examen des données statistiques recueillies au cours de plusieurs années amène à choisir de modéliser l'évolution de la population pour les années à venir de la façon suivante : 

\setlength\parindent{8mm}
\begin{itemize}
\item[$\bullet~~$] l'effectif de la population est globalement constant,
\item[$\bullet~~$] chaque année, 5\,\% de ceux qui résident en ville décident d'aller s'installer à la campagne et 1\,\% de ceux qui résident à la campagne choisissent d'aller habiter en ville.
\end{itemize}
\setlength\parindent{0mm}

\bigskip
 
Pour tout entier naturel $n$, on note $v_{n}$ le nombre d'habitants de cette région qui résident en ville au 1$^{er}$~janvier de l'année $(2013 + n)$ et $c_{n}$ le nombre de ceux qui habitent à la campagne à la même date.

\medskip
 
\begin{enumerate}
\item Pour tout entier naturel $n$, exprimer $v_{n+1}$ et $c_{n+1}$ en fonction de $v_{n}$ et $c_{n}$.  
\item Soit la matrice\index{matrice} $A = \begin{pmatrix}0,95&0,01\\0,05& 0,99\end{pmatrix}$. 

On pose $X = \begin{pmatrix}a\\b\end{pmatrix}$ où $a,\: b$ sont deux réels fixés et $Y = AX$.
 
Déterminer, en fonction de $a$ et $b$, les réels $c$ et $d$ tels que $Y = \begin{pmatrix}c\\d\end{pmatrix}$.
\end{enumerate}
 
Les résultats précédents permettent d'écrire que pour tout entier naturel $n$, 

$X_{n+1} = AX_{n}$ où $X_{n} = \begin{pmatrix}v_{n}\\c_{n}\end{pmatrix}$. On peut donc en déduire que pour tout entier naturel $n,\: X_{n} = A^n X_{0}$. 

\medskip

\begin{enumerate}
\item[\textbf{3.}] Soient les matrices $P = \begin{pmatrix}1&- 1\\5&1\end{pmatrix}$ et $Q = \begin{pmatrix}1&1\\- 5&1\end{pmatrix}$. 
	\begin{enumerate}
		\item Calculer $PQ$ et $QP$. En déduire la matrice $P^{-1}$ en fonction de $Q$. 
		\item Vérifier que la matrice\index{matrice} $P^{-1}AP$ est une matrice diagonale $D$ que l'on précisera. 
		\item Démontrer que pour tout entier naturel $n$ supérieur ou égal à $1$, $A^n = P D^n P^{- 1}$.
	\end{enumerate} 
\item[\textbf{4.}] Les résultats des questions précédentes permettent d'établir que 
 
\[v_{n} = \dfrac{1}{6}\left(1 + 5 \times  0,94^n\right)v_{0} + \dfrac{1}{6}\left(1 - 0,94^n\right)c_{0}.\] 

Quelles informations peut-on en déduire pour la répartition de la population de cette région à long terme ? 
\end{enumerate}
\end{exoi}

\begin{exoi}\hfill \textbf{Polynésie 2013}\\
Un opérateur téléphonique A souhaite prévoir l'évolution de nombre de ses abonnés dans une grande ville par rapport à son principal concurrent B à partir de 2013.

En 2013, les opérateurs A et B ont chacun $300$ milliers d'abonnés.

\medskip

Pour tout entier naturel $n$, on note $a_n$ le nombre d'abonnés, en milliers, de l'opérateur A la $n$-ième année après 2013, et $b_n$ le nombre d'abonnés, en milliers, de l'opérateur B la $n$-ième année après 2013.

Ainsi, $a_0 = 300$ et $b_0 = 300$.

\medskip

Des observations réalisées les années précédentes conduisent à modéliser la situation par la relation suivante :

pour tout entier naturel $n$, 
$\begin{cases}
a_{n+1} = 0,7a_n + 0,2b_n + 60 \\
b_{n+1} = 0,1a_n + 0,6b_n + 70
\end{cases}$.

\medskip

On considère les matrices\index{matrice} $M = 
\begin{pmatrix}
  0,7 & 0,2 \\ 0,1 & 0,6
\end{pmatrix}$ et $P =
\begin{pmatrix}
  60 \\ 70
\end{pmatrix}$.

Pour tout entier naturel $n$, on note $U_n =
\begin{pmatrix}
  a_n \\ b_n
\end{pmatrix}$.

\begin{enumerate}
\item
  	\begin{enumerate}
  		\item Déterminer $U_1$.
  		\item Vérifier que, pour tout entier naturel $n$, $U_{n+1} = M \times U_n +P$.
  	\end{enumerate}
\item On note $I$ la matrice $
  	\begin{pmatrix}
    1 & 0 \\ 0 & 1
  	\end{pmatrix}$.
  	\begin{enumerate}
  		\item Calculer $(I - M)\times
\begin{pmatrix}
4 & 2 \\ 1 & 3
\end{pmatrix}$.
  		\item En déduire que la matrice $I - M$ est inversible et préciser son inverse.
  		\item Déterminer la matrice $U$ telle que $U = M \times U + P$.
  	\end{enumerate}
\item Pour tout entier naturel, on pose $V_n = U_n - U$.
  	\begin{enumerate}
  		\item Justifier que, pour tout entier naturel $n$, $V_{n+1} = M \times V_n$.
  		\item En déduire que, pour tout entier naturel $n$, $V_n = M^n \times V_0$.
  	\end{enumerate}
\item On admet que, pour tout entier naturel $n$, 

\renewcommand\arraystretch{1.8}
\[V_n =  \begin{pmatrix}
    \dfrac{-100}{3}\times 0,8^n - \dfrac{140}{3} \times 0,5^n \\
    \dfrac{-50}{3} \times 0,8^n + \dfrac{140}{3} \times 0,5^n 
  \end{pmatrix}\]
\renewcommand\arraystretch{1}

  	\begin{enumerate}
  		\item Pour tout entier naturel $n$, exprimer $U_n$ en fonction de $n$ et en déduire la limite de la suite\index{suite} $(a_n)$.
  		\item Estimer le nombre d'abonnés de l'opérateur A à long terme.
  	\end{enumerate}
\end{enumerate}
\end{exoi}
\pagebreak

\section{Arithmétique}
 \begin{exoi}
 \Cadre[Principe Général]{
\begin{enumerate}
\item Alice génère deux gros nombres premiers $p$ et $q$, ainsi qu'un gros nombre $d$ premier avec $\varphi(n)$.
\item Alice calcule $n=pq$ et cherche $e$ tel que $de\equiv 1 [\varphi(n)]$.
\item Alice diffuse $n$ et $e$, garde en mémoire $d$ et oublie $\varphi (n)$.
\item Bernard crypte un message $M$ par $M\longmapsto M^e [n]$ et envoie le résultat à Alice.
\item Alice décode alors le message crypté par $C\longmapsto C^d [n]$.
\end{enumerate}}
Le but du protocole est bien sûr qu'Alice retrouve le message d'origine. Démontrons que c'est bien le cas. Les transformations appliquées au message sont :
$$ M\longmapsto M^e [n]\longmapsto \left(M^e [n]\right)^d [n]$$
On veut donc montrer que $  \left(M^e [n]\right)^d [n]=M$ c'est-à-dire que :
$$ \left(M^e\right)^d \equiv M [n] \Longleftrightarrow M^{de}\equiv M [n]$$
\begin{enumerate}
\item Montrer qu'il existe un entier relatif $k$ tel que : $ de=1+k\varphi(n)$
En déduire que l'on souhaite démontrer que : $ M\times M^{k\varphi(n)}\equiv M [n]$
\item \textbf{On suppose que $M$ est premier avec $n$.}

 En utilisant le théorème 2 montrer que 
$$ M\times M^{k\varphi(n)}\equiv M [n]$$
\item \textbf{On suppose que $M$ n'est pas premier avec $n$.}
\begin{enumerate}
\item Donner la liste des diviseurs positifs de $n$.
\item En déduire que $M$ est un multiple de $p$ ou de $q$. \\
Dans le cas où $M$ est un multiple de $q$ on peut écrire que :
$$ M=p^\alpha m \qquad \text{ avec $\alpha $ un entier naturel et $m$ un entier non multiple de $p$ }$$
\item Montrer que $m$ est premier avec $n$.\\
En déduire que $m^{de}\equiv m [n]$.
\item Montrer que :
$$ M^{de}\equiv p^{\alpha de } \times m [n]$$
 \textit{Il nous reste à démontrer que $p^{\alpha de } \equiv p^{\alpha} (n)$}.
\item Montrer que $p^{\alpha de } \equiv p^{\alpha} (n)$ est un multiple de $p$.
\item Montrer que $$ p^{de}=p\times p^{k(p-1)(q-1)}$$
En déduire en utilisant le petit théorème de Fermat (ou le théorème 2, ce qui revient au même) que :
$$ p^{de}\equiv p [q]$$
\item En déduire  que $p^{\alpha de }-p^{\alpha}$ est un multiple de $q$.
\item En déduire, en utilisant Gauss que $p^{\alpha de }-p^{\alpha}$ est un multiple de $n$ puis conclure.
\end{enumerate}
\end{enumerate}
 \end{exoi}
 
 
 
 \pagebreak
 
 \begin{exoi}
{\Large \textbf{Nouvelle-Cal\'{e}donie mars 2007}}
\end{exoi}

Pour coder un message, on proc\`{e}de de la mani\`{e}re suivante : \`{a}
chacune des 26 lettres de l'alphabet, on commence par associer un entier $n$
de l'ensemble $\Omega =\{0~;~1~;~2~;~\ldots ~;~24~;~25\}$ selon le tableau
ci-dessous :

\noindent 
\begin{tabularx}{\linewidth}{|*{13}{>{\centering \arraybackslash}X|}}\hline
A	&B	&C	&D	&E	&F	&G	&H	&	I&J	&K	&L	&M\\ \hline
0	&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12\\ \hline\hline
N	&O	&P	&Q	&R	&S	&T	&U	&V	&W	&X	&Y	&Z\\ \hline
13	&14	&15	&16	&17	&18	&19	&20	&21	&22	&23	&24	&25\\ \hline
\end{tabularx}

\noindent $a$ et $b$ \'{e}tant deux entiers naturels donn\'{e}s, on associe 
\`{a} tout entier $n$ de $\Omega $ le reste de la division euclidienne de $%
(an+b)$ par 26 ; ce reste est alors associ\'{e} \`{a} la lettre
correspondante.

\emph{Exemple} : pour coder la lettre P avec $a=2$ et $b=3$, on proc\`{e}de
de la mani\`{e}re suivante :\newline

\'{e}tape 1 : on lui associe l'entier $n=15$.

\'{e}tape 2 : le reste de la division de $2\times 15+3=33$ par 26 est $7$.

\'{e}tape 3 : on associe $7$ \`{a} H. Donc P est cod\'{e} par la lettre H.

\begin{enumerate}
\item Que dire alors du codage obtenu lorsque l'on prend $a=0$ ?

\item Montrer que les lettres A et C sont cod\'{e}es par la m\^{e}me lettre
lorsque l'on choisit $a=13$.

\item \emph{Dans toute la suite de l'exercice}, on prend $a=5$ et $b=2$.

\begin{enumerate}
\item On consid\`{e}re deux lettres de l'alphabet associ\'{e}es
respectivement aux entiers $n$ et $p$. Montrer, que si $5n+2$ et $5p+2$ ont
le m\^{e}me reste dans la division par 26 alors $n-p$ est un multiple de $26$%
. En d\'{e}duire que $n=p$.

\item Coder le mot AMI.
\end{enumerate}

\item On se propose de d\'{e}coder l a lettre E.

Montrer que d\'{e}coder la lettre E revient \`{a} d\'{e}terminer l'\'{e}l%
\'{e}ment $n$ de $\Omega $ tel que $5n-26y=2$, o\`{u} $y$ est un entier.
\end{enumerate}

\begin{exoi}
\textbf{\Large France septembre 2005}

\begin{enumerate}
\item 
\begin{enumerate}
\item QCM : On consid\`{e}re dans l'ensemble des entiers relatifs l'\'{e}%
quation : 
\begin{equation*}
x^{2}-x+4\equiv 0\quad (~6)
\end{equation*}

A: toutes les solutions sont des entiers pairs.

B : il n'y a aucune solution.

C : les solutions v\'{e}rifient $x\equiv 2\quad (~6)$.

D : les solutions v\'{e}rifient $x\equiv 2\quad (~6)$ ou $%
x\equiv 5\quad (~6)$.

\item On consid\`{e}re les deux nombres $n=1789$ et $p=1789^{2005}$. On a
alors :

A : $n\equiv 4\quad (~17)$ et $p\equiv 0\quad (
~17) $.

B : $p$ est un nombre premier.

C : $p\equiv 4\quad (~17)$.

D : $p\equiv 1\quad (~17)$.
\end{enumerate}
\end{enumerate}
\end{exoi}

\begin{exoi}
\begin{enumerate}
\item \textbf{R.O.C} : On rappelle que :

 $m$ est un entier naturel non nul. $a \equiv b (m)$ équivaut à $a-b=km$, $k\in \Z$.
\\
 Démontrer que si $a\equiv b(m)$ et si $a'\equiv b'(m)$, alors 
 $$ a+a' \equiv b+b' (m)\qquad \text{et} aa'\equiv bb' (m)$$
 \item \textbf{Application} : $x$ et $y$ sont deux entiers relatifs. On se propose de résoudre le système :
 $$  \left\{\begin{array}{cccc}
3x+y& \equiv & 1&(6)\\
x-y&\equiv & 3&(6)
\end{array}\right.$$
\begin{enumerate}
\item \begin{enumerate}
\item Démontrer que $4x \equiv 4 (m)$.
\item Déduisez-en, à l'aide d'un tableau donnant les restes modulo $6$ que $4x\equiv 4 (6)\Longleftrightarrow x\equiv 1 (6)$ ou $x\equiv 4 (6)$.
\end{enumerate}
\item En tenant-compte de $y\equiv x-3(6)$, déduisez-en les couples $(x; y)$ solutions du système.
\end{enumerate}
\end{enumerate}
\end{exoi}

\begin{exoi}\hfill \textbf{Pondichéry 2012}\\
 
\textbf{Partie A \quad	Restitution organisée de connaissance}

\medskip
 
Soit $a,\: b,\: c,\: d$ des entiers relatifs et $n$ un entier naturel non nul. 

Montrer que si $a \equiv b \pmod n$ et $c \equiv d \pmod n$ alors $ac \equiv bd \pmod n$. 

\bigskip

\textbf{Partie B \quad Inverse de 23 modulo 26}

\medskip
 
On considère l'équation 

\[(E) \::\quad  23x - 26y = 1,\]

où $x$ et $y$ désignent deux entiers relatifs.

\medskip
 
\begin{enumerate}
\item Vérifier que le couple $(-9~;~-8)$ est solution de l'équation $(E)$. 
\item Résoudre alors l'équation $(E)$. 
\item En déduire un entier $a$ tel que $0 \leqslant a \leqslant 25$ et $23a \equiv 1 \pmod {26}$.
\end{enumerate}

\bigskip

\textbf{Partie C \quad Chiffrement de Hill}

\medskip
 
On veut coder un mot de deux lettres selon la procédure suivante :

\medskip
 
\fbox{
\begin{minipage}{\textwidth}
\textbf{Étape 1} Chaque lettre du mot est remplacée par un entier en utilisant le tableau ci-dessous :

\medskip
 
\begin{tabularx}{\linewidth}{|*{26}{>{\centering\arraybackslash \scriptsize}X|}}\hline
A&B&C&D&E&F&G&H&I&J&K&L&M&N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\ \hline
0&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\\ \hline
\end{tabularx}

\medskip

On obtient un couple d'entiers $\left(x_{1}~;~x_{2}\right)$ où $x_{1}$ correspond à la première lettre du mot et $x_{2}$ correspond à la deuxième lettre du mot.
 
\textbf{Étape 2} $\left(x_{1}~;~x_{2}\right)$ est transformé en $\left(y_{1}~;~y_{2}\right)$ tel que :

\[\left(S_{1}\right)\:\: \left\{\begin{array}{l c l l}
y_{1} &\equiv& 11x_{1} + 3x_{2} &\pmod {26}\\ 
y_{2} &\equiv& 	7x_{1} + 4x_{2} &\pmod {26}
\end{array}\right.\quad  	\text{avec}\: 0 \leqslant  y_{1} \leqslant 25\:\: \text{et}\:\: 0 \leqslant y_{2} \leqslant 25.\]

\textbf{Étape 3} $\left(y_{1}~;~y_{2}\right)$ est transformé en un mot de deux lettres en utilisant le tableau de correspondance donné dans l'étape 1.
\end{minipage}}

\medskip
 
Exemple : $\underbrace{\text{TE}}_{{\text{mot en clair}}}\stackrel{\text{étape} 1}{\Longrightarrow}   
(19,4) \stackrel{\text{étape}\: 2}{\Longrightarrow} (13,19) \stackrel{\text{étape}\: 3}{\Longrightarrow}
\underbrace{\text{NT}}_{{\text{mot codé}}}$

\medskip
 
\begin{enumerate}
\item Coder le mot ST. 
\item On veut maintenant déterminer la procédure de décodage: 
	\begin{enumerate}
		\item Montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{1}\right)$, vérifie les équations du système :

\[\left(S_{2}\right)\:\: \left\{\begin{array}{l c l l}
23x_{1} &\equiv& 4y_{1} + 23y_{2} &\pmod {26}\\ 
23x_{2}&\equiv& 19y_{1} + 11y_{2} &\pmod {26}
\end{array}\right.\]

		\item À l'aide de la partie B, montrer que tout couple $\left(x_{1}~;~x_{2}\right)$ vérifiant les équations du système $\left(S_{2}\right)$, vérifie les équations du système
		 
\[\left(S_{3}\right)\:\: \left\{\begin{array}{l c l l}
x_{1}&\equiv& 	16y_{1} + y_{2} &\pmod {26}\\
x_{2}&\equiv& 11y_{1} + 5y_{2} &\pmod {26}
\end{array}\right.\]
  
		\item Montrer que tout couple $\left(x_{1}~;~x_{2}\right)$  vérifiant les équations du système $\left(S_{3}\right)$, vérifie les équations du système $\left(S_{1}\right)$ 
		\item Décoder le mot \textbf{YJ}. 
	\end{enumerate}
\end{enumerate} 
\end{exoi}


\begin{exoi}\hfill (\textbf{Antilles-Guyanne 2012})\\
\textbf{Les trois questions sont indépendantes.} 

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Vérifier que le couple (4~;~6) est une solution de l'équation 
		
		\[(\text{E})\qquad 11x - 5y = 14.\]
		 
		\item Déterminer tous les couples d'entiers relatifs (x~;~y) vérifiant l'équation (E).
	\end{enumerate} 
\item 
	\begin{enumerate}
		\item Démontrer que, pour tout entier naturel $n$, 

\[2^{3n} \equiv 1\quad  \mod 7.\]
 
		\item Déterminer le reste de la division euclidienne de ${2011}^{{2012}}$ par 7.
	\end{enumerate}		 
  
\item 

\item On considère l'algorithme suivant où $\text{Ent}\left (\dfrac{\text{A}}{\text{N}}\right)$ désigne la partie entière de $\dfrac{\text{A}}{\text{N}}$.

\medskip

\begin{center} 
\fbox{
\begin{minipage}{0.75\textwidth} 
A et N sont des entiers naturels\\ 
Saisir A\\ 
N prend la valeur 1\\ 
Tant que N $\leqslant  \sqrt{\text{A}}$\\ 
\phantom{aaaaaaaaa} Si $\dfrac{\text{A}}{\text{N}} -  \text{Ent}\left (\dfrac{\text{A}}{\text{N}}\right) = 0$ alors Afficher N et $\dfrac{\text{A}}{\text{N}}$\\
\phantom{aaaaaaaaa}Fin si\\ 
N prend la valeur N + 1\\ 
Fin Tant que.
\end{minipage}}
\end{center}

\medskip
 
Quels résultats affiche cet algorithme pour A = 12 ?

Que donne cet algorithme dans le cas général? 

\end{enumerate}


\end{exoi}

\pagebreak

\begin{exoi}\hfill \textbf{Polynésie 2012}\\
\partieBac{}
\medskip

On considère l'équation (E) : $25x -108y =1$ où $x$ et $y$ sont des entiers relatifs.
\begin{enumerate}
\item Vérifier que le couple $(13~;~3)$ est solution de cette équation.
\item Déterminer l'ensemble des couples d'entiers relatifs solutions de l'équation (E).
\end{enumerate}

\bigskip

\partieBac{}
\medskip

Dans cette partie, $a$ désigne un entier naturel et les nombres $c$ et $g$ sont des entiers naturels vérifiant la relation $25g -108c =1$.

On rappelle le petit théorème de Fermat : 

Si $p$ est un nombre premier et $a$ un entier non divisible par $p$, alors $a^{ p-1}$ est congru à 1 modulo $p$ que l'on note $a^{ p-1}\equiv 1~[p]$.

\medskip

\begin{enumerate}
\item  Soit $x$ un entier naturel.

Démontrer que si $x\equiv a~[7]$ et $x\equiv a~[19]$, alors $x\equiv a~[133]$.
\item 
	\begin{enumerate}
		\item On suppose que $a$ n'est pas un multiple de 7.
		
Démontrer que $a^6\equiv 1~[7]$ puis que $a^{108}\equiv 1~[7]$.

En déduire que $\left(a^{25}\right)^g\equiv a~[7]$.
		\item On suppose que a est un multiple de 7.
		
Démontrer que $\left(a^{25}\right)^g\equiv a~[7]$.
		\item  On admet que pour tout entier naturel $a$, $\left(a^{25}\right)^g\equiv a~[19]$.
		
Démontrer que $\left(a^{25}\right)^g\equiv a~[133]$.
	\end{enumerate}
\end{enumerate}

\bigskip

\partieBac{}
\medskip

On note A l'ensemble des entiers naturels $a$ tels que : $1\leqslant a\leqslant 26$.

Un message, constitué d'entiers appartenant à A, est codé puis décodé.

La phase de codage consiste à associer, à chaque entier $a$ de A, l'entier $r$ tel que $a^{25}\equiv r~[133]$ avec $0\leqslant r< 133$.

La phase de décodage consiste à associer à $r$ , l'entier $r_1$ tel que $r^{13}\equiv r_1~[133]$ avec $0\leqslant r_1 < 133$.

\medskip

\begin{enumerate}
\item Justifier que $r_1\equiv a~[133]$.
\item Un message codé conduit à la suite des deux entiers suivants : $128 \qquad 59$.

Décoder ce message.
\end{enumerate}
\end{exoi}

% \begin{exoi}\textbf{Un exercice où la matrice de transition à une somme égale à 1 sur les lignes...}\\
% \partieBac{}
% Les scientifiques estiment qu'un seul individu est à l'origine de la maladie sur les 100 personnes que compte la population et que, d'une semaine à la suivante, un individu change d'état suivant le processus suivant :
%\setlength\parindent{6mm} 
%\begin{itemize}
%\item parmi les individus sains, la proportion de ceux qui deviennent porteurs sains est égale à $\dfrac{1}{3}$ et la proportion de ceux qui deviennent malades est égale à $\dfrac{1}{3}$, 
%\item parmi les individus porteurs sains, la proportion de ceux qui deviennent malades est égale à $\dfrac{1}{2}$.
%\end{itemize}
%\setlength\parindent{0mm} 
%La situation peut être représentée par un graphe probabiliste comme ci-dessous.
%\begin{center}
%\psset{unit=1cm}
%\begin{pspicture}(6,4)
%%\psgrid
%\cnodeput(3,3){S}{$S$}
%\cnodeput(1,1){I}{$I$}
%\cnodeput(5,1){M}{$M$}
%\nccircle{->}{S}{0.4cm}
%\nccircle[angleA=-180]{<-}{I}{0.4cm}
%\nccircle[angleA=-180]{->}{M}{0.4cm}
%\ncarc{<-}{I}{S}\rput(1.55,2.2){$\dfrac{1}{3}$}
%\ncarc{->}{S}{M}\rput(4.45,2.2){$\dfrac{1}{3}$}
%\ncarc{->}{I}{M}\rput(3,0.7){$\dfrac{1}{2}$}
%\rput(3.8,3.4){$\dfrac{1}{3}$}\rput(5.6,0.4){1} \rput(0.4,0.4){$\dfrac{1}{2}$}
%\end{pspicture}
%\end{center}
%On note $P_{n} = \left(s_{n}\quad i_{n}\quad m_{n}\right)$ la matrice ligne donnant l'état probabiliste au bout de $n$ semaines où $s_{n}, i_{n}$ et $m_{n}$désignent respectivement la probabilité que l'individu soit sain, porteur sain ou malade la $n$-ième semaine. 
%\\
%On a alors $P_{0} = (0,99\quad 0\quad 0,01)$
%% et pour tout entier naturel $n$, 
%%
%%\[\renewcommand\arraystretch{1.7}
%%\left\{\begin{array}{l c l}
%%s_{n+1}&=&\dfrac{1}{3}s_{n}\\
%%i_{n+1}&=&\dfrac{1}{3}s_{n} + \dfrac{1}{2}i_{n}\\
%%m_{n+1}&=&\dfrac{1}{3}s_{n} + \dfrac{1}{2}i_{n} + m_{n}
%%\end{array}\right.\]
%\begin{enumerate}
%\item Exprimer $s_{n+1}$, $i_{n+1}$ et $m_{n+1}$ en fonction de $s_n$, $i_n$ et $m_n$.
%\item Écrire la matrice $A$ appelée \emph{matrice de transition}, telle que pour tout entier naturel $n,\:$ $P_{n+1} = P_{n} \times A$.
%\item Démontrer par récurrence que pour tout entier naturel $n$ non nul, 
%$P_{n} = P_{0} \times A^n$.
%\item Déterminer l'état probabiliste $P_{4}$ au bout de quatre semaines. On pourra arrondir les valeurs à $10^{- 2}$.
% \\
%Quelle est la probabilité qu'un individu soit sain au bout de quatre semaines ? 
%\end{enumerate}
%\partieBac{}
%La maladie n'évolue en réalité pas selon le modèle précédent puisqu'au bout de 4 semaines de recherche, les scientifiques découvrent un vaccin qui permet d'enrayer l'endémie et traitent immédiatement l'ensemble de la population. L'évolution hebdomadaire de la maladie après vaccination est donnée par la matrice de transition : 
%\[
%\renewcommand\arraystretch{1.7} B = \begin{pmatrix}5/12&1/4 &1/3\\
%5/12&1/4 &1/3\\
%1/6&1/2&1/3
%\end{pmatrix}.\]
%On note $Q_{n}$ la matrice ligne donnant l'état probabiliste au bout de $n$ semaines après la mise en place de ces nouvelles mesures de vaccination. Ainsi, $Q_{n} = \left(S_{n}\quad I_{n}\quad M_{n}\right)$ où $S_{n},\: I_{n}$ et $M_{n}$ désignent respectivement la  probabilité que l'individu soit sain, porteur sain et malade la $n$-ième semaine après la vaccination. 
%\\
%Pour tout  entier naturel $n$, on a alors $Q_{n+1}  = Q_{n} \times B$.
%\\
%D'après la partie A, $Q_{0}  = P_{4}$. Pour la suite, on prend $Q_{0} = (0,01\quad  0,10\quad 0,89)$ où les coefficients ont été 
%arrondis à $10^{–2}$.
%\begin{enumerate}
%\item Exprimer $S_{n+1}, I_{n+1}$ et $M_{n+1}$ en fonction de $S_{n},\: I_{n}$ et $M_{n}$.
%\item Déterminer la constante réelle $k$ telle que $B^2  = kJ$ où $J$ est la matrice carrée d'ordre 3 dont tous les coefficients sont égaux à 1.
%\item Montrer que $B^3=B^2$ puis en déduire par récurrence que $B^n=B^2$ pour tout entier naturel $n$ supérieur ou égal à $2$.
%\item 
%	\begin{enumerate}		\item Démontrer que pour tout entier $n$ supérieur ou égal à 2, $Q_{n} = \left(\dfrac{1}{3}\quad \dfrac{1}{3}\quad \dfrac{1}{3}\right)$.
%		\item Interpréter ce résultat en terme d'évolution de la maladie. 
%	\\	
%Peut-on espérer éradiquer la maladie grâce au vaccin ?
%	\end{enumerate}
%\end{enumerate}
%\end{exoi}
%
%\begin{exoi}
%Le gestionnaire d'un site web, composé de trois pages web numérotées de 1 à 3 et reliées entre elles par des liens hypertextes, désire prévoir la fréquence de connexion sur chacune de ses pages web.\\
%Des études statistiques lui ont permis de s'apercevoir que :
% \\
%$\bullet~~$ Si un internaute est sur la page 1, alors il ira, soit sur la page 2 avec la probabilité $\dfrac{1}{4}$, soit sur la page 3 avec la probabilité $\dfrac{3}{4}$.
%\\
%$\bullet~~$ Si un internaute est sur la page 2, alors, soit il ira sur la page  1 avec la probabilité $\dfrac{1}{2}$ soit il  
%restera sur la page  2 avec la probabilité $\dfrac{1}{4}$, soit il ira sur la page  3 avec la probabilité $\dfrac{1}{4}$. 
%\\
%$\bullet~~$ Si un internaute est sur la page 3, alors, soit il ira sur la page  1 avec la probabilité $\dfrac{1}{2}$, soit il  
%ira sur la page  2 avec la probabilité $\dfrac{1}{4}$,soit il restera sur la page  3 avec la probabilité $\dfrac{1}{4}$. \\
%Pour tout entier naturel $n$, on définit les évènements et les probabilités suivants : \\
%$A_{n}$ : \og Après la $n$-ième navigation, l'internaute est sur la page  1 \fg{} et on note $a_{n} = P\left(A_{n}\right)$.
% \\
%$B_{n}$ : \og Après la $n$-ième navigation, l'internaute est sur la page  2 \fg{} et on note $b_{n} = P\left(B_{n}\right)$.
% \\
%$C_{n}$ : \og Après la $n$-ième navigation, l'internaute est sur la page  3 \fg{} et on note $c_{n} = P\left(C_{n}\right)$.
%\begin{enumerate}
%\item Montrer que, pour tout entier naturel $n$, on a $a_{n+1} = \dfrac{1}{2} b_{n} + \dfrac{1}{2}c_{n}$. 
%\\
%On admet que, de m\^eme, $b_{n+1} = \dfrac{1}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}$ et $c_{n+1} = \dfrac{3}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}$. 
%%\\
%%Ainsi : 
%%\renewcommand\arraystretch{1.8}
%%\[\left\{\begin{array}{l c l}
%%a_{n+1} &=& \dfrac{1}{2} b_{n} + \dfrac{1}{2}c_{n}\\
%%b_{n+1} &=& \dfrac{1}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}\\
%%c_{n+1} &=& \dfrac{3}{4}a_{n} + \dfrac{1}{4}b_{n} + \dfrac{1}{4}c_{n}
%%\end{array}\right.\]
%%\renewcommand\arraystretch{1}
%\item Pour tout entier naturel $n$, on pose $U_{n} = \begin{pmatrix} a_{n}\\b_{n}\\c_{n}\end{pmatrix}$. $U_{0} = \begin{pmatrix} a_{0}\\b_{0}\\c_{0}\end{pmatrix}$ représente la situation initiale, avec $a_{0} + b_{0} + c_{0} = 1$.
% \\
%Montrer que, pour tout entier naturel $n,\: U_{n+1} = MU_{n}$ où $M$ est une matrice $3 \times 3$ que l'on précisera.
% \\
%En déduire que, pour tout entier naturel $n, U_{n} = M^nU_{0}$. 
%\item Montrer qu'il existe une seule matrice colonne $U =\begin{pmatrix}x\\y\\z\end{pmatrix}$ telle que : $x + y + z = 1$ et $MU = U$. 
%\item Un logiciel de calcul formel a permis d'obtenir l'expression de $M^n,\: n$ étant un entier naturel non nul :
%\[M^n = \begin{pmatrix}
%\frac{1}{3} + \frac{\left( \frac{- 1}{2}\right)^n \times 2}{3}&\frac{1}{3} + \frac{\left( \frac{- 1}{2}\right)^n }{- 3}&\frac{1}{3} + \frac{\left(\frac{- 1}{2}\right)^n}{- 3}\\
%\frac{1}{4}&\frac{1}{4}&\frac{1}{4}\\
%\frac{5}{12} + \frac{\left(-\left(\frac{- 1}{2}\right)^n\right) \times 2}{3}&\frac{5}{12} + \frac{-\left(\frac{- 1}{2}\right)^n}{-3}&\frac{5}{12} + \frac{-\left(\frac{- 1}{2}\right)^n }{- 3}
%\end{pmatrix}\] 
%Pour tout entier naturel $n$ non nul, exprimer $a_{n}, \: b_{n}$ et $c_{n}$ en fonction de $n$. En déduire que les suites $\left(a_{n}\right), \: \left(b_{n}\right)$ et $\left(c_{n}\right)$ convergent vers des limites que l'on précisera. 
%\item Interpréter les résultats obtenus et donner une estimation des pourcentages de fréquentation du site à long terme. 
%\end{enumerate}
%\end{exoi}
%  
%%  
%% \begin{exoi}
%% Un logiciel permet de transformer un élément rectangulaire d'une photographie. Ainsi, le rectangle initial OEFG est transformé en un rectangle OE$'$F$'$G$'$, appelé image de OEFG.
%%\begin{center}
%%\psset{unit=1cm}
%%\begin{pspicture}(7.5,6.5)
%%\pspolygon(3.3,0.8)(7,4.8)(5.4,6.25)(1.75,2.2)
%%\pspolygon(3.3,0.8)(5.1,2.75)(2.1,5.6)(0.3,3.5)
%%\uput[dr](5.1,2.8){E} \uput[u](2.1,5.6){F} \uput[ul](0.3,3.5){G} 
%%\uput[d](3.3,0.8){O} \uput[dr](7,4.8){E$'$} \uput[u](5.4,6.25){F$'$} 
%%\uput[dl](1.75,2.2){G$'$}
%%\rput(3,0.12){Figure 1} 
%%\end{pspicture}
%%\end{center} 
%%L'objet de cet exercice est d'étudier le rectangle obtenu après plusieurs transformations successives.
%%\\
%%\partieBac{} 
%%Le plan est rapporté à un repère orthonormé \Oij. Les points E, F et G ont pour coordonnées respectives (2~;~2), $(-1~;~5)$ et $(-3~;~3)$.
%% \\
%%La transformation du logiciel associe à tout point $M(x~;~y)$ du plan le point $M'(x'~;~y')$, image du point $M$ tel que: 
%%\begin{multicols}{2}
%%\renewcommand\arraystretch{1.8}
%%\[\left\{\begin{array}{l c l}
%%x'&=&\dfrac{5}{4}x + \dfrac{3}{4}y\\
%%y'&=&\dfrac{3}{4}x + \dfrac{5}{4}y
%%\end{array}\right.\]
%%\renewcommand\arraystretch{1}
%%\begin{center}
%%\psset{unit=1cm}
%%\begin{pspicture}(-4,-2)(3,5.5)
%%\psaxes[linewidth=1.5pt,Dx=10,Dy=10]{->}(0,0)(-4,-1)(3,5.5)
%%\pspolygon(0,0)(2,2)(-1,5)(-3,3)
%%\uput[dl](0,0){O} \uput[ur](2,2){E} \uput[u](-1,5){F} \uput[l](-3,3){G}
%%\rput(-1,-1.5){Figure 2} 
%%\end{pspicture}
%%\end{center}
%%\end{multicols}
%%\begin{enumerate}
%%\item 
%%	\begin{enumerate}
%%		\item Calculer les coordonnées des points E$'$, F$'$ et G$'$, images des points E, F et G par cette transformation. 
%%		\item Comparer les longueurs OE et OE$'$ d'une part, OG et OG$'$ d'autre part.
%%	\\	 
%%Donner la matrice carrée d'ordre 2, notée $A$, telle que: $\begin{pmatrix}x'\\y' \end{pmatrix}= A \begin{pmatrix}x\\y \end{pmatrix}$.
%%	\end{enumerate}
%%\end{enumerate}
%%\partieBac{}
%%Dans cette partie, on étudie les coordonnées des images successives du sommet F du rectangle OEFG lorsqu'on applique plusieurs fois la transformation du logiciel.
%%\begin{enumerate}
%%\item On considère l'algorithme\index{algorithme} suivant destiné à afficher les coordonnées de ces images successives.
%% \\
%%Une erreur a été commise. Modifier cet algorithme pour qu'il permette d'afficher ces coordonnées.
%%\begin{center}
%%\begin{tabular}{|c|l|}\hline 
%%Entrée &Saisir un entier naturel non nul $N$\\ \hline 
%%\multirow{2}{2cm}{Initialisation }&Affecter à $x$ la valeur $- 1$\\ 
%%&Affecter à $y$ la valeur 5\\ \hline 
%%\multirow{6}{2cm}{Traitement}&POUR $i$ allant de 1 à $N$\\ 
%%&Affecter à $a$ la valeur $\frac{5}{4} x + \frac{3}{4}y$\\ 
%%&Affecter à $b$ la valeur $\frac{3}{4}x + \frac{5}{4}y$\\ 
%%&Affecter à $x$ la valeur $a$\\ 
%%&Affecter à $y$ la valeur $b$\\ 
%%&FIN POUR\\ \hline 
%%Sortie &Afficher $x$, afficher $y$\\ \hline
%%\end{tabular}
%%\end{center} 
%%\item On a obtenu le tableau suivant :
%%\[\begin{array}{|*{8}{c|}} \hline
%%i &1 &2 &3 &4 &5 &10 &15\\ \hline 
%%x &2,5 &7,25 &15,625 &{31,8125} &{63,9063} &{2047,9971} &{65535,9999}\\ \hline 
%%y &5,5 &8,75 &16,375 &{32,1875} &{64,0938} &{2048,0029} &{65536,0001}\\ \hline
%%\end{array}\]
%%Conjecturer le comportement de la suite des images successives du point F. 
%%\end{enumerate}
%%\partieBac{}
%%Dans cette partie, on étudie les coordonnées des images successives du sommet E du rectangle OEFG. On définit la suite des points $E_{n}\left(x_{n}~;~y_{n}\right)$ du plan par $E_{0} =$ E et la relation de récurrence :
%%\[\begin{pmatrix}x_{n+1}\\y_{n+1}\end{pmatrix} = A\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix},\] 
%%où $\left(x_{n+1}~;~y_{n+1}\right)$ désignent les coordonnées du point $E_{n+1}$. Ainsi $x_{0} = 2$ et $y_{0} = 2$. 
%%\begin{enumerate}
%%\item On admet que, pour tout entier $n \geqslant 1$, la matrice\index{matrice} $A^n$ peut s'écrire sous la forme : $A^{n} = \begin{pmatrix}\alpha_{n}&\beta_{n}\\\beta_{n}&\alpha_{n}\end{pmatrix}$. 
%%Démontrer par récurrence que, pour tout entier naturel $n \geqslant 1$, on a : $\alpha_{n} = 2^{n-1}  + \dfrac{1}{2^{n+1}} \quad \text{et}\quad  \beta_{n} = 2^{n-1}  - \dfrac{1}{2^{n+1}}.$
%%\item 
%%	\begin{enumerate}
%%		\item Démontrer que, pour tout entier naturel $n$, le point $E_{n}$ est situé sur la droite d'équation $y = x$.
%%	\\	 
%%On rappelle que, pour tout entier naturel $n$, les coordonnées $\left(x_{n}~;~y_{n}\right)$ du point $E_{n}$ vérifient :
%%$\begin{pmatrix}x_{n}\\y_{n}\end{pmatrix} = A^n \begin{pmatrix}2\\2\end{pmatrix}.$
%%		\item Démontrer que la longueur O$E_{n}$ tend vers $+ \infty$ quand $n$ tend vers $+ \infty$.
%%	\end{enumerate}
%%\end{enumerate}
%% \end{exoi}
\end{document}