\input{/users/davidwallard/documents/lycee/latex_class/latex_classperso/maclassperso}
\usepackage{tabularx}
\usepackage{dashbox}

\begin{document}

\entete{TS  Spé Maths}{DEVOIR MAISON N$^0$3}{}

\exercice
\textbf{ Test de Fermet et les nombres de Carmichaël}

\textbf{Partie A: Observation:}\\
On s'intéresse aux restes des nombres $a^n-a$ dans leur division euclidienne par $n$, entier naturel supérieur ou égal à 2.
\begin{enumerate}
\item Calculer ces restes pour $a=5$ et $n=2$; $a=5$ et $n=8$.
\item On a automatisé ce calcul sur un tableur et obtenu les résultats ci-dessous pour les entiers $a$ de 0 à 12 et les entiers $n$ de 2 à 13.\\

\includegraphics[scale=0.8]{img.eps}\\

\begin{enumerate}
\item Contrôler les résultats trouvés à la question 1.
\item Certaines lignes sont composées uniquement de 0.\\
Quelles sont les valeurs de $n$ concernées?\\
Emettre une conjecture.\\

\end{enumerate}

\end{enumerate}
\textbf{Partie B: Un test de primalité}\\
On rappelle la thérorème de Fermat: \textit{Si $p$ est premier alors pour tout entier $a$, $a^p\equiv a\, (p)$}

\begin{enumerate}
\item \textbf{Les nombres de Poulet}
\begin{enumerate}
\item Soit $p=341=11\times 31$. Calculer $2^{11}$ et justifier que $2^{11}\equiv 2\; (341)$.
\item Ecrire la division euclidienne de 31 par 11 et justifier que $2^{31}\equiv 2\; (341)$. En déduire que $2^{241}\equiv 2\; (341)$.
\item La réciproque du théorème de Fermat est-elle vraie?\\[0.3cm]
Il existe donc des entiers tels que $2^p\equiv 2\; (p)$ et qui ne sont pas premiers. Ces nombres sont appelés pseudopremiers de base 2 ou nombres de Poulet (de Paul Poulet 1887-1946).
\end{enumerate}

\item \textbf{Les nombres de Carmickaël}
\begin{enumerate}
\item Vérifier que $561=3\times 11\times 17$ est pseudopremier de base 2, c'est à dire que $2^{561}\equiv 2\; (561)$.
\item Vérifier que $561$ est aussi pseudopremier de base 3, c'est à dire que $3^{561}\equiv 3\; (561)$.
\item On souhaite créer un algorithme pour tester si $a^{561}\equiv a(561)$ pour $a$ allant de 2 à 560.
\begin{center}
\fbox{
\begin{minipage}{10cm}
\textbf{Initialisation:} $n$ prend la valeur 561; $t$ prend la valeur 0\\
\textbf{Traitement :}\\
\hspace*{1.5cm} Pour $a$ de 2 jusqu'à $n-1$ Faire\\

\hspace*{2cm}\dbox{
\begin{minipage}{7.5cm}
 $r$ prend la valeur reste$(a,n)$; $m$ prend la valeur $r$;\\
Pour $k$ de 2 jusqu'à $n$ Faire\\
\hspace*{0.5cm} $r$ prend la valeur reste$(m\times r;n)$\\
 FinPour
 \end{minipage}}\\
 
\hspace*{2cm} Si $m\not= r$ alors\\
\hspace*{2.5cm} Afficher ("pas pseudopremier pour " a);\\
\hspace*{2cm} $t$ prend la valeur 1;\\
\hspace*{2cm} FinSi\\
\hspace*{1.5cm} FinPour\\
\hspace*{1.5cm} Si $t=0$ alors\\
\hspace*{2cm} Afficher("pseudopremier");\\
\hspace*{1.5cm} FinSi
\end{minipage}
}\\[0.5cm]

\end{center}


Pour une valeur de $a$ donnée, expliquer ce que fait la partie de l'algorithme entourée en pointillé.\\
A quelle condition la variable $t$ contiendra-t-elle la valeur 1 à la fin de l'algorithme?\\
L'affichage obtenu à la fin de l'algorithme est "pseudopremier". Que cela signifie-t-il pour 561?
\item Proposer une définition d'un nombre pseudopremier, aussi appelé nombre de Carmichaël.
\end{enumerate}

\newpage

\end{enumerate}
\textbf{Eléments de correction:}\\
\textbf{Partie A:}\\
\begin{enumerate}
\item $5^2-5=20$ donc $r=0$.\\
$5^2\equiv 0\; (8)$ , donc $\left(5^2\right)^4-5\equiv -4\; (8)$, donc $5^8-5\equiv 4\; (8)$.\\
\item \begin{enumerate}
\item ok
\item Si $n$ est premier, les lignes sont composées de 0.\\
Si $p$ est premier $a^p-a\equiv 0\; (p)$.\\
\end{enumerate}
\end{enumerate}

\textbf{Partie B:}

\begin{enumerate}
\item \begin{enumerate}
\item $2^{11}=2048$ et $2048-2=2046=6\times 341$.\\
\item $31=11\times 2+9$, donc\\
$\begin{array}{rcl}
2^{31} &\equiv & (2^{11})^2\times 2^9\; (341)\\
&\equiv & 2^2\times 2^9\; (341)\\
&\equiv & 2^{11}\; (341)\\
&\equiv& 2\; (341)
\end{array}$\\

$2^{31}\equiv 2\; (341)\Rightarrow (3^{31})^{11}\equiv 2^{11}\; (341)\Rightarrow 2^{341}\equiv 2\; (341)$.


\item Non, car 341 n'est pas premier.
\end{enumerate}
\item \begin{enumerate}
\item D'après le théorème de Fermat, $2^2\equiv 1\; (3)$, donc $2^{561}\equiv \left(2^2\right)^{280}\times 2\;(3)$, donc $2^{561}\equiv 2\; (3)$.\\
De même, d'après Fermat $2^{10}\equiv 1\; (11)$, donc $2^{351}\equiv \left(2^{10}\right)^{35}\times 2\; (11)$, donc $2^{561}\equiv 2\; (11)$.\\
Et, $2^{16}\equiv 1\; (17)$, donc $2^{561}\equiv \left(2^{16}\right)^{35}\times 2\; (17)$, donc $2^{561}\equiv 2\; (17)$.\\
Par conséquent, 3, 11 et 17 divisent $2^{561}-2$, donc $3\times 11\times 17$ divise $2^{561}-2$ doù le résultat.\\
\item De même, on démontre que $3^{351}\equiv 3\; (3)$, $3^{561}\equiv 3\; (11)$ et $3^{561}\equiv 3\; (17)$ d'où le résultat.
\item la partie de l'agorithme permet de calculer le reste de la division euclidienne de $a^n$ par $n$.\\
$t$ contient $1$ s'il existe un entier $a$ tel que $a^n\equiv a\; (n)$.\\
Cela signfie que pour tout entier $a$ tel que $1<a<n$, $a^n\equiv a\; (n)$.\\
\item Un nombre est pseudo-premier s'il n'est pas premier et si pour tout $a$ (avec $1<a<n$) $a^n\equiv a\; (n)$.

\end{enumerate}
\end{enumerate}
\end{document}