+
+\begin{Exo}
+On considère l'algorithme suivant:
+on choisit deux nombres premiers $p$ et $q$
+distincts tels que
+$p \equiv 2 [3]$ et $s \equiv 2 [3]$.
+Soit $n = pq$.
+Alice veut envoyer un message à Bob.
+Comme dans RSA, son message est un nombre $m \in \ \{1, . . . , n - 1\}$
+tel que $m \land n = 1$
+Le message codé d'Alice est le résultat $a= m^3[n]$.
+Bob décode $a$ en calculant
+\[
+m' \equiv a^{d} [n] \textrm{ où $d=\dfrac{2(p-1)(q-1)+1}{3}$}
+\]
+Normalement $m$ doit être égal à $m'$.
+
+\begin{enumerate}
+\item Choisir $p=11$, $q=17$, $m=4$ puis construire le message codé ainsi que le message décodé.
+\item Montrer que $d$ est toujours un entier.
+\item Expliquer pourquoi $a$ et $m'$ ne sont pas divisibles par $n$.
+\item Montrer que Bob a bien décodé le message d’Alice.
+\end{enumerate}
+
+\end{Exo}
+
+
+\begin{Prop}[Petit théorème de Fermat]
+Si $p$ est un nombre premier et $a$ un entier
+alors $a^{p} \equiv a [p]$.
+\end{Prop}
+
+\begin{Proof}
+La preuve se fait par récurrence sur $a$.
+\begin{itemize}
+\item Pour $a=0$, c'est trivial.
+\item Supposons la formule établie pour $k=a$ et montrons qu'elle l'est aussi
+pour $k=a+1$.
+On remarque tout d'abord que pour chaque $k$, $0 < k < p$, le coefficient
+binomial $\binom{p}{k} = \dfrac{p!}{k!(p-k)!}$ est divisible par $p$, c.-à-d.
+$\binom{p}{k} \equiv 0 [p]$.
+On a alors successivement:
+\begin{eqnarray*}
+(k+1)^p &=& a^p +
+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\dots +\binom{p}{p-1}a^{1}+1\\
+&\equiv& a^p +1 [p]\textrm{ (d'après la remarque sur les coeff. binomiaux)}\\\
+&\equiv& a +1 [p]\textrm{ (par hypothèse de récurrence).}\\\
+\end{eqnarray*}
+\end{itemize}
+\end{Proof}
+
+\begin{Prop}[Corrolaire du petit théorème de Fermat]
+Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+alors $a^{p-1}-1$ est un multiple de $p$.
+\end{Prop}
+\begin{Proof}
+D'après le petit théorème de Fermat, $a^{p} \equiv a [p]$. Dit Autrement
+$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ est premier avec $a$ d'après les
+hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
+\end{Proof}
+
+
+\begin{Exo}[Sujet du bac S Liban 2005]
+% On rappelle le résultat suivant appelé le corollaire du
+% petit théorème de Fermat.
+
+% \emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
+% alors $a^{p-1}-1$ est un multiple de $p$.}
+\begin{enumerate}
+\item On considère l’équation $(E)$ : $109x-226y=1$ où $x$ et $y$
+ sont des entiers relatifs.
+\begin{enumerate}
+\item Déterminer $109\land 226$.
+ Que peut-on en conclure pour l'équation $(E)$?
+\item Montrer que l'ensemble des solutions de $(E)$
+ est l'ensemble des couples de la forme
+ $(141+226k ;68+109k)$, où $k$ appartient à $\Z$.
+ En déduire qu'il existe un unique entier naturel non nul $d$
+ inférieur ou égal à 226 et un unique entier naturel non nul $e$ tels que
+ $109d =1+226 e$ (on précisera les valeurs des entiers $d$ et $e$).
+\end{enumerate}
+\item Démontrer que 227 est un nombre premier.
+\item On note $A=\{0,1,2,\dots,226\}$. On considère les deux fonctions
+ $f$ et $g$ de $A$ dans $A$ définies de la manière suivante:
+\begin{itemize}
+\item A tout entier $a\in A$, $f$ associe le reste de
+ la division euclidienne de $a^{109}$ par 227.
+\item A tout entier $a\in A$, $g$ associe le reste de la
+ division euclidienne de $a^{141}$ par 227.
+\end{itemize}
+\begin{enumerate}
+\item Vérifier que $g(f(0))=0$ .
+\item Montrer que, quel que soit l'entier non nul $a$ de $A$ , $a^{226}-1$ est multiple de 227.
+\item En déduire que, quel que soit l'entier non nul $a$ de $A$,
+$g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
+\end{enumerate}
+\end{enumerate}
+\end{Exo}
+
+
+
