\begin{Exo}[Sujet du bac S Liban 2005]
-On rappelle le résultat suivant appelé petit théorème de Fermat.
+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{itemize}
\item[\textbf{Existence.}]
Comme $a$ et $n$ sont premiers entre eux, d'après le théorème de Bézout,
-il exite $x$ et $y$ entiers tels que
+il existe $x$ et $y$ entiers tels que
+PREUVE A FINIR
+
+
\end{itemize}
\end{Proof}
+\begin{Exp}
+Trouvons les nombres $x$ tels que $7x+11$ soit multiple de 36. Dit autrement,
+résoudre l'équation $7x \equiv -11 [36]$.
+
+On cherche un \og inverse \fg{} de 7 c.-à-d. un nombre $t$, $1 < t < 35$
+tel que $7t \equiv 1 [36]$.
+Soit à résoudre $7t \equiv 1 [36]$ qui revient à trouver $t$ et $u$ tels
+que $7t -36u = 1$, soit encore les coefficient de Bézout relatifs à
+(7 et 36). On trouve successivement
+\begin{eqnarray*}
+36 & = & 7 \times 5 +1 \\
+7 & = & 7 \times 1 + 0 \\
+& \textrm{et donc}&\\
+1 & = & 36 - 7 \time 5
+\end{eqnarray*}
+et donc $t = -5$ (et $u=-1$).
+On en déduit $7x \equiv -11 [36]$ est équivalent à
+$(-5).7x \equiv (-5).-11 [36]$ soit encore
+$x \equiv 55 [36] \equiv 19 [36]$.
+\end{Exp}
+
+\begin{Exo}
+Trouver les entiers relatif $x$ tels que
+$261x +2$ soit multiple de 305.
+\end{Exo}
+
+
\begin{Exo}
\begin{enumerate}
\end{enumerate}
\end{Exo}
+
+
+
\begin{Exo}
On se place dans le contexte de cryptographie par RSA.
Démontrer que si la clé d'encryptage est $e < \varphi(n)$, alors
\end{eqnarray*}
\end{Proof}
+
+\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} = \frac{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{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èmede Fermat, $a^{p} \equiv a [p]$. Dit Autrement
+$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ ne divise pas $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}
+
\subsection{Puissance de grands nombres}
+\begin{Exp}
+Calculons $666^{999}[13]$.
+On a successivement:
+\begin{eqnarray*}
+666^{999} & \equiv & (13\times 51 + 3)^{999} [13]\\
+ & \equiv & 3^{999} [13]\\
+ & \equiv & 3^{12\times83 +3} [13] \\
+ & \equiv & 3^3 \time (3^{12})^{83} [13] \\
+ & \equiv & 3^3 \time (1)^{83} [13] \textrm{(car $3^{12}\equiv 1 [13]$ d'après le corollaire du petit théorème de Fermat)}\\
+ & \equiv & 27 [13]\\
+ & \equiv & 1 [13]
+\end{eqnarray*}
+\end{Exp}
+
\begin{Exo}
Montrer que l'entier naturel $n$ est premier si et seulement si
\end{Exo}
+
+
+\begin{Exo}
+Calculer $2^{500} [13]$ et $26^{1000} [17]$.
+\end{Exo}
+
+
\section{Génération de grands nombres premiers}
Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs premiers.
Depuis Euclide, on sait que $\Prem$ est de taille infinie.
\subsubsection{Tests probabilistes}
-\begin{Prop}[Petit théorème de Fermat]
+\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$, c'est-à-dire:
\begin{equation}
\end{equation}
\end{Prop}
-\begin{Proof}
-La preuve découle directement du théorème~\ref{th:Euler} d'Euleur.
-En effet on a successivement:
-\begin{eqnarray*}
- a^{p-1} & = & a^{\varphi(p)} \textrm{(comme p est premier)}\\
- & \equiv & 1 [p] \textrm{(théorème d'Euler)}
-\end{eqnarray*}
-\end{Proof}
\paragraph{Test de Fermat.}
Le petit théorème de Fermat est une implication et non pas une équivalence:
