\documentclass[a4paper,11pt]{article}

\input macrodwicky.tex
\geometry{verbose,letterpaper,hmargin=2cm,vmargin=2cm}
\usepackage{calligra}



\newcommand{\ch}{Chapitre 3}
\newcommand{\Ch}{Arithmétiques et  \linebreak[2]  problèmes de codage, partie 2}	
\newcommand{\Cl}{TS-spé}	
\newcommand{\Annee}{2013-2014}	
\newcommand{\Profs}{D.Zancanaro}

\definecolor{trustcolor}{rgb}{0.71,0.14,0.07}

\newcommand{\Couleur}{trustcolor}


\begin{document}

\pagestyle{empty}
\calligra
\begin{pspicture}(-1,-3)(3,1)
   \psset{linewidth=0.2}
   %\psline[linecolor=dablue](-1,0)(3,0)
   \rput(7,0){\psdiabox*[fillcolor=\Couleur]{\bfseries\huge\textsc{\textcolor{white!20}{2013-2014}}}}
  {\color{\Couleur}{\rput(-2,-2){\rule{5cm}{3pt}} }}
  \rput(7,-2){\bfseries\Huge\textsc{\textbf{Les cours du Lycée J.Durand}}}
  {\color{\Couleur}{\rput(16,-2){\rule{5cm}{3pt}} }}
    {\color{\Couleur}{\rput(-2,-8.5){\rule{2cm}{150pt}} }}
 {\color{\Couleur}{\rput(-2.2,-16.2){\rule{2cm}{80pt}} }}
\end{pspicture}
\rm
\vfill
\hfill \huge{ \textbf{Mathématiques}} \hspace*{3cm} \newline

\hfill \huge{ \textbf{Terminale S}} \hspace*{3cm} \newline

\hfill \huge{ \textbf{Enseignement de spécialité}} \hspace*{3cm} \newline

\vfill

\hfill \Large{ \textbf{Rédaction :}} \hspace*{3cm} \newline

\hfill \Large{ David Zancanaro \hspace*{3cm} \newline


\vfill


\hfill \large{ \textbf{Réalisé à l'aide de : }\hspace*{3cm} \newline

\hfill \large{ \LaTeX \hspace*{3cm} 

\definecolor{BlanchedAlmond}{rgb}{1,0.92,0.80}


\pagebreak


\tableofcontents
\pagebreak



\fancypagestyle{styleLyc}{%
\fancyhf{} 
\fancyhead{\href{http://www.wicky-math.fr.nf}{wicky-math.fr.nf}}
	\fancyfoot[LE,LO]{{\scriptsize\textsl{ \Profs \\ Lycée \LyDav }}}
	\fancyfoot[C]{\scriptsize\textsl{\Cl \\ \Annee}}
\fancyfoot[LE,RO]{\bfseries\thepage / \pageref{LastPage}}
}
\pagestyle{styleLyc}

\lhead{\Ch}
\rhead{\ch}
\setcounter{NumLecon}{2}


\TITRE{ascii.eps}{0.4}

\section{Nombres premiers}

\subsection{Généralité}
 Rappelons que :
 
\begin{defi}On dit qu'un entier naturel $p$ est premier s'il poss\`ede exactement 2 diviseurs positifs : 1 et lui-m\^eme.\end{defi}



\Expls{
\begin{itemize}
 \item 0 n'est pas premier car il admet une infinit\'e de diviseurs
 \item 1 n'est pas premier car il n'admet qu'\textit{un seul} diviseur : lui-m\^eme.
 \item 2 est le seul nombre premier pair (les autres sont divisibles au moins par 1, eux-m\^emes et 2).
 \item 3, 5, 7, 11, 13 sont des nombres premiers.
 \item 6 n'est pas un nombre premier, car il est divisible par 1, 6, 2 et 3.
\end{itemize}
}



\begin{theo}Soit $n\in \N$ sup\'erieur ou \'egal \`a 2. Alors :
\begin{itemize}
\item $n$ admet au moins un diviseur premier
\item  Si $n$ n'est pas premier, alors il admet au moins un diviseur premier $p$ tel que $p \leq \sqrt{n}$. 
\end{itemize}
\end{theo}

\Dem{
\begin{itemize}
\item Si $n$ est premier, alors il s'admet lui-m\^eme comme diviseur premier. \\
Sinon, $n$ admet au moins un diviseur propre c'est-à-dire un diviseur $p$ tel que $1<p<n$. Considérons l'ensemble $E$ des diviseurs propres de $n$, cet ensemble est fini, non vide et contient au maximum $n-2$ éléments compris entre $1$ et $n$. Il admet donc un plus petit élément, disons $p_0$.\\
Si $p_0$ n'est pas un nombre premier, alors il admet au moins un diviseur $d$ tel que $1<d<p_0$. Cependant si $d$ divise $p_0$ qui divise $n$ alors $d$ divise $n$. C'est-à-dire $d$ est un diviseur propre de $n$ strictement inférieur au plus petit diviseur propre de $n$, ce qui est absurde...
\\
Par conséquent $p_0$ est premier ce qui prouve que $n$ admet un diviseur premier.
\item  Puisque $n$ n'est pas premier, il admet un diviseur premier, notons le $p$. Puisque $p|n$ il existe un entier naturel $k$ tel que $n=pk$. 
Si $p\leq \sqrt{n}$ alors le théorème est démontré.
\\Si $p>\sqrt{n}$ alors $k<\sqrt{n}$ car dans le cas contraire on aurait :
$$ pk>\sqrt{n}\times \sqrt{n}=n$$
Si $k$ est un nombre premier alors le théorème est démontré.
\\
Si $k$ n'est pas un nombre premier alors il admet au moins un diviseur premier $p_0<k<\sqrt{n}$, ce nombre $p_0$ divise $k$ qui divise $n$, donc $p_0$ est un nombre premier inférieur ou égal à $\sqrt{n}$ qui divise $n$, ce qui prouve le théorème.
\end{itemize}
}

\begin{coro}Soit $n\in \N$ sup\'erieur ou \'egal \`a 2. Alors si $n$ n'admet aucun diviseur inf\'erieur ou \'egal \`a sa racine carr\'e, alors $n$ est premier\end{coro}

\Dem{C'est la contrapos\'ee du th\'eor\`eme.}


\begin{exoi}
$317$ est-il un nombre premier ? Répondre sans utiliser de calculatrice.
\end{exoi}

\begin{exoi}
Montrer que si $p$ est premier si $p$ divise $a^2$ alors $p$ divise $a$.
\footnote{\textit{Lemme d'euclide} : Si un nombre premier $p$ divise le produit $ab$ alors il divise $a$ ou il divise $b$.
}
\end{exoi}

\subsection{Infinité des nombres premiers}
\begin{theo}Il existe une infinit\'e de nombres premiers.\end{theo}

\Dem{Supposons qu'il existe un nombre fini $n$ de nombres premiers, not\'es $p_1$, $p_2$, $\dots$, $p_n$. On pose $N=p_1\times p_2 \times \dots \times p_n + 1$. \newline
Puisque $N<p_n$, $N$  n'est pas premier, donc il admet un certain diviseur premier $k$. Nous connaissons l'ensemble des nombres premiers donc $k$ est un des $p_i$ c'est-à-dire il existe $i$ entre $1$ et $n$ tel que $k=p_i$.
\\
De plus $k | p_1p_2 \dots p_n$ et $k|N$ donc $k|1$ (la diff\'erence). Donc $k=1$ ce qui est absurde puisque $k$ est un nombre premier.
Par cons\'equent il est absurde de supposer qu'il existe un nombre fini de nombres premiers.\\
On en conclut qu'il existe une infinité de nombres premiers. }


\subsection{D\'ecomposition en nombres premiers}

\begin{theo}
Tout entier naturel $n\geq 2$ peut s'écrire comme le produit de nombres premiers c'est-à-dire il existe $k$ nombres premiers $p_1<p_2<\dots <p_k$ et $k$ entiers naturels $\alpha_1$, $\alpha_2$, $\dots$, $\alpha_k$ tels que :
$$ n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \dots \times p_k^{\alpha_k} $$
Une telle décomposition est unique.\end{theo}

\begin{exoi}
Décomposer $9510$ en produit de facteurs premiers puis en déduire l'ensemble des diviseurs positifs de $9510$.
\end{exoi}

\begin{exoi}
On considère la suite $(u_n)$ définie pour tout entier naturel $n$ par $u_n=\overline{11\dots 1}$, nombre qui s'écrit avec $n$ fois le chiffre $1$.
\begin{enumerate}
\item Quels sont les nombres premiers parmi $u_2$, $u_3$, $\dots$, $u_6$ ?
\item Montrer que si $n$ est multiple de $3$, alors $u_n$ admet $111$ comme diviseur et n'est donc pas premier.
\item
\begin{enumerate}
 \item Montrer que, pour tout entier naturel $n$ on a :
$$ u_n=\dfrac{10^n-1}{9}$$
\item Montrer que pour tout $x\in \R$ on a :
$$ x^n-1=(1+x+x^2+\dots +x^{n-1}(x-1)$$
\item En déduire que, si $n$ n'est pas premier alors $u_n$ n'est pas premier. 
\\
\textit{Indication} : On montrera que $u_n$ est un multiple de $u_p$ où $p$ est un diviseur de $n$. 
 \end{enumerate} 
\end{enumerate}
\end{exoi}

\begin{exoi}
Soit $p$ un nombre premier et  l'équation $(E): x^2-y^2=p$.
\begin{enumerate}
\item Démontrer si $x$ et $y$ sont des entiers naturels solutions de $(E)$, alors ils sont consécutifs.
\item En déduire tous les couples d'entiers naturels solutions de $(E)$.
\item Déterminer tous les couples d'entiers naturels solutions de $(E'):x^2-y^2=p^2$.
\end{enumerate}
\end{exoi}

\Dem{
\textit{Existence} :\\
Si $n$ est un nombre premier alors le théorème est valable trivialement.\\
Sinon, si $n$ n'est pas un nombre premier il existe au moins un nombre premier $p$ qui divise $n$. Notons $p_1$ le plus petit d'entre eux. On peut donc écrire $n=p_1\times n_1$ avec $n_1<n$. On réitère le même raisonnement avec $n_1$ qui, s'il n'est pas premier admet au moins diviseur premier $p$. En notant $p_2$ le plus petit d'entre eux ($p_2$ est alors aussi un diviseur de $n$ donc $p_1\leq p_2$). On obtient alors :$$n=p_1p_2n_2$$ 
avec $1\leq n_2 < n_1 < n$. Si $n_2=1$ alors $n_1$ est premier et le r\'esultat est d\'emontr\'e. Sinon on r\'eit\`ere le raisonnement tant que le quotient est diff\'erent de 1.\\
La liste des quotients est une liste d\'ecroissante d'entiers naturels, elle admet donc un plus petit \'el\'ement $n_k$ et est finie. On a alors $n=p_1p_2 \dots p_k$\newline
Comme certains $p_i$ peuvent être égaux il existe des entiers naturels
$\alpha_1$, $\alpha_2$, $\dots$, $\alpha_k$ tels que :
$$ n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \dots \times p_k^{\alpha_k} $$
\textit{Unicit\'e} : Supposons que $n$ admettent deux décompositions en facteurs premiers différentes, cela peut se traduire de deux manières :
\begin{itemize}
 \item soit  les nombres premiers intervenant dans les deux décompositions ne sont pas tous identiques.
 \item soit  les nombres premiers intervenant dans les deux décompositions sont identiques et ce sont les puissances qui diffèrent.
 \end{itemize} 
 Dans le premier cas, supposons donc que $n$ se décompose en utilisant le nombre premier $p$ d'une part et sans l'utiliser d'autre part. $p$ est donc un diviseur de $n$. $n$ admet une décomposition en facteurs premiers ne faisant pas intervenir $p$ de la forme :
$$ n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \dots \times p_k^{\alpha_k}$$
$p$ divise par exemple le produit $p_1\times k$ avec $k=p_1^{\alpha_1-1}\times p_2^{\alpha_2}\times \dots \times p_k^{\alpha_k}$ donc d'après le lemme d'euclide il divise soit $p_1$ soit $k$. En réitérant ce raisonnement il vient que $p$ divise un nombre premier différent de lui-même ce qui est absurde.
\\
Dans le second cas, seule les puissances diffèrent. $n$ admet donc deux décompositions de la forme :
$$ n=p^\alpha \times k=p^\beta \times k'\qquad \text{avec } \alpha < \beta$$
Ainsi :
$$ \dfrac{n}{p^\alpha}=k=p^{\beta-\alpha}k'$$
$p$ divise $p^{\beta-\alpha}k'$ donc $p$ divise $k$ qui est un produit de nombre premiers tous différents de $p$, on est ramené au premier cas.
\\
Par conséquent un nombre ne peut pas admettre deux décompositions en produit de facteurs premiers différentes.
}

\Expls{ 
On utilise les crit\`eres de divisibilit\'e.
$105=3\times 5\times 7 \quad ; \quad 83 160 = 2^3 \times 3^3 \times 5 \times 7 \times 11$. 
}


\begin{theo}
Soit $n$ un entier naturel sup\'erieur ou \'egal \`a 2 se d\'ecomposant en produit de facteurs premiers sous la forme $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. \newline
Les diviseurs positifs de $n$ sont les nombres de la forme $p_1^{\beta_1}p_2^{\beta_2}\dots p_k^{\beta_k}$, avec $0\leq \beta_i \leq \alpha_i$ pour tout $1 \leq i \leq k$.
\end{theo}

\Dem{Il est clair que les nombres de cette forme divisent $n$ car $\alpha_i-\beta_i \geq 0$ pour tout $1 \leq i \leq k$.\newline
D\'emontrons maintenant que tout diviseur de $n$ est de cette forme.\newline
Soit $d$ un diviseur de $n$. Alors il existe un entier $d'$ tel que $n=d\times d'$. Le produit des d\'ecompositions en facteurs premiers de $d$ et $d'$ est une d\'ecomposition en produit de facteurs premiers de $n$. \newline
Comme elle est unique, c'est la m\^eme.\newline
Les seuls diviseurs premiers intervenant dans les d\'ecompositions de $d$ et $d'$ sont donc les $p_i$ et leur exposant ne peuvent \^etre qu'inf\'erieurs ou \'egaux aux $\alpha_i$.\newline
L'entier $d$ est donc forc\'ement de la forme indiqu\'ee.}

\begin{coro}Soit un entier $n \leq 2$ se d\'ecomposant en produit de facteurs premiers sous la forme $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. \newline
Alors, $n$ poss\`ede $(\alpha_1+1)\times (\alpha_2 + 1) \times \dots \times (\alpha_k+1)$ diviseurs positifs.\end{coro}

\Dem{D\'enombrement. Un arbre de probabilité permet assez rapidement de se convaincre.}

\begin{exoi}
\begin{enumerate}
\item Indiquer pour chacun des nombres suivants s'il est premier  : $481$, $483$, $485$, $487$.
\item Pour quelles valeurs du nombre entier $n$, le nombre suivant est-il premier ?
\begin{enumerate}
\item $n^2-8n+15$
\item $n^2+4n+3$. \textit{Essayer de factoriser ces polynômes.}
\end{enumerate}
\item Pour quelles valeurs des nombres entiers naturels $n$ et $m$ le nombre $2n^2+5nm+3m^2$ est-il premier ?\\
\textit{Indication} : On montrera que $2n^2+5nm+3m^2=(n+m)(2n+3m)$
\item Factoriser $n^4+4$ en partant de $n^4+4=(n^2+2)^2-4n^2$. Pour quelles valeurs entières de $n$ l'entier $n^4+4$ est-il premier ?
\item Si $p$ est un nombre premier et $n$ un entier naturel non nul. Montrer que deux cas seulement peuvent se présenter :
\begin{itemize}
\item soit $p$ divise $n$ ;
\item soit $p$ et $n$ sont premiers entre eux, c'est-à-dire ils ont pour plus grand diviseur $1$.
\end{itemize}
\item Deux nombres premiers sont dits jumeaux si leur différence est égale à $2$. Pour vérifier que $1607$ et $1609$ sont des nombres premiers jumeaux, par quels nombres premiers faut-il vérifier qu'ils ne sont pas divisibles ?
\\
Les nombres $33218925\times 2^{169690}\pm 1$ sont deux nombres premiers jumeaux de plus de $50000$ chiffres (découverts en $2002$). On ne sait toujours pas s'il existe une infinité de nombres premiers jumeaux.
\end{enumerate}
\end{exoi}

\begin{exoi}
Le but de l'exercice est de montrer qu'il existe une infinité de nombres premiers de la forme $6k+5$ où $k\in \N$.
\begin{enumerate}
\item \begin{enumerate}
\item Déterminer six nombres premiers de cette forme.
\item Déterminer six nombres composés de cette forme.
\end{enumerate}
\item Montrer que tout nombre premier, autre que $2$ et $3$ est de la forme $6k+1$ ou $6k+5$, où $k\in \N$.
\item On suppose qu'il existe un nombre fini de nombres premiers de la	forme $6k+5$ que l'on nomme $p_1$, $p_2$, $\dots$, $p_n$.\\
On considère le nombre $$ N=6p_1p_2\dots p_n-1$$
\begin{enumerate}
\item Justifier que $N\equiv -1[6]$.
\item En déduire que $N$ est de la forme $6k+5$ puis qu'il ne peut être premier.
\item Montrer qu'aucun des nombres $p_1$, $p_2$, $\dots$, $p_n$ ne divisent $N$ et en déduire que les diviseurs premiers de $N$ sont de la forme $6k+1$.
\item Montrer que $N\equiv 1[6]$.
\end{enumerate}
\item Conclure.
\end{enumerate}
\end{exoi}

\begin{exoi}\textbf{Antilles-Guyanne, Juin 2005} \hfill (5 points)\\
\begin{enumerate}
\item \begin{enumerate}
      \item D\'eterminer suivant les valeurs de l'entier naturel non nul $n$ le reste dans la division euclidienne 
	par 9 de $7^n$.
       \item D\'emontrer alors que $2005^{2005}\equiv 7 \, [9]$
      \end{enumerate}
\item \begin{enumerate}
      \item D\'emontrer que pour tout entier naturel non nul $n$ : $10^n \equiv 1 \, [9]$
       \item On d\'esigne par $N$ un entier naturel \'ecrit en base 10, on appelle $S$ la somme de ses chiffres. \\
      D\'emontrer la relation suivante : $N \equiv S \, [9]$
      \item En d\'eduire que $N$ est divisible par 9 si et seulement si $S$ est divisible par $9$.
      \end{enumerate}
\item On suppose que $A=2005^{2005}$ ; on d\'esigne par : \begin{itemize}
							  \item $B$ la somme des chiffres de $A$
                                                          \item $C$ la somme des chiffres de $B$
							  \item $D$ la somme des chiffres de $C$
                                                          \end{itemize}
      \begin{enumerate}
      \item D\'emontrer la relation suivante : $A \equiv D \, [9]$
      \item Sachant que $2005 <10000$, d\'emontrer que $A$ s'\'ecrit en num\'eration d\'ecimale avec au plus 8020 chiffres. \\
      En d\'eduire que $B \leq 72180$.
      \item D\'emontrer que $C \leq 45$
      \item En \'etudiant la liste des entiers inf\'erieurs \`a 45, d\'eterminer un majorant de $D$ plus petit que 15.
      \item Montrer que $D=7$.
      \end{enumerate}
\end{enumerate}
\end{exoi}
\subsection{Questions diverses sur les nombres premiers}

\subsubsection{Les nombres de Carmichaël}

\begin{defi}
Un entier $n\geq 3$ est un nombre de Carmichaël si et seulement si :
\begin{enumerate}
\item il est le produit d'au moins trois nombres premiers impairs ;
\item il est tel que, pour chaque diviseur premier $p$ de $n$, l'entier $p-1$ divise $n-1$
\end{enumerate}
\end{defi}


\begin{exoi}
\begin{enumerate}
\item $30$ et $561$ sont-ils des nombres de Carmichaël ?
\item Les nombres premiers sont-ils des nombres de Carmichaël ?
\item Décomposer $1729$ puis $2695$ en produit de facteurs premiers.
\item $1729$ et $2695$ sont-ils des nombres de Carmichaël ?
\end{enumerate}
\end{exoi}

\Rq{Le petit théorème de Fermat énonce que les nombres premiers ont la propriété $\mathcal P$ : si $p$ est un nombre premier et si $a$ est un entier non divisible par $p$, alors  $a^{p-1} - 1$ est un multiple de $p$. ». Autrement dit, sous les mêmes conditions sur a et p:. Sa réciproque est fausse, les nombres de Carmichael sont les nombres positifs qui satisfont à $\mathcal P$ sans être premiers, ce sont des menteurs de Fermat ; l'existence de tels nombres pseudo-premiers absolus est ce qui empêche d'utiliser le test de primalité de Fermat pour prouver qu'un nombre est premier.
Plus les nombres deviennent grands et plus les nombres de Carmichael deviennent rares, la majorité d'entre eux rendent le test de primalité de Fermat largement inutile comparé aux autres tests de primalité comme le test de primalité de Solovay-Strassen. Par exemple, le $646e$ nombre de Carmichael vaut $993 905 641$ et il existe $105 212$ nombres de Carmichael entre $1$ et $10^{15}$.
}

\subsubsection{Les nombres parfaits}
\begin{exoi}\textbf{Nombre parfaits}\hfill $\spadesuit \spadesuit \spadesuit$\\
\emph{Définition : Dire qu'un entier naturel $n$ est parfait signifie que la somme de tous ses diviseurs positifs est égale à $2n$.}
\begin{enumerate}
\item Montrer que :
$$ \forall x\neq 1, \qquad \sum_{i=0}^{n} x^i=\dfrac{1-x^{n+1}}{1-x}$$
\textit{Indication} : On pourra calculer $(1-x)\sum_{i=0}^{n} x^i$.
\item Démontrer que $28$ est un nombre parfait.
\item $p$ désigne un nombre premier tel que $q=2^p-1$ soit premier.
\begin{enumerate}
\item Déterminer les diviseurs positifs de $2^{p-1}$.
\item Déterminer les diviseurs positifs de $2^p-1$.
\item Calculer la somme des diviseurs positifs de l'entier $E^p=2^{p-1}(2^p-1)$.\\
\textit{Remarque} : Les nombres $E_p$ sont appelés \textit{nombres d'Euclide}.
\item En déduire que $2^{p-1}(2^p-1)$ est un nombre parfait.
\item Déterminer alors trois nombres parfaits.
\end{enumerate}
\item \hfill $\spadesuit \spadesuit \spadesuit \spadesuit \spadesuit$\\
 $p$ et $q$ désignent des nombres premiers distincts supérieurs ou égaux à $3$ et $\alpha$ et $\beta$ sont des entiers naturels non nuls ; on note $n=p^\alpha q^\beta$.
\begin{enumerate}
\item Déterminer les diviseurs positifs de $p^\alpha$ et de $q^\beta$.
\item Démontrer que la somme $S$ des diviseurs positifs de $n$ est donnée par :
$$ S=\dfrac{p^{\alpha+1}-1}{p-1}\times \dfrac{q^{\beta+1}-1}{q-1}$$
\item Démontrer que $n$ est parfait, si et seulement si $p^\alpha q^\beta\left((p-2)(q-2)-2\right)=1-p^{\alpha+1}-q^{\beta+1}$.
\item En étudiant le signe de chaque membre, démontrer qu'il ne peut pas exister de nombres parfaits impairs dont la décomposition en produit de facteurs premiers ne contienne que deux facteurs premiers distincts.
\item Démontrer que s'il existe un nombre parfait impair, il est supérieur à $105$.
\\
\textit{Remarque} : On ignore, à l'heure actuelle, s'il existe des nombres parfaits impairs.
\end{enumerate}
\end{enumerate}
\end{exoi}


\subsubsection{Les nombres de Fermat}

Un nombre de Fermat est un entier naturel qui peut s'écrire sous la forme $2^{2^n} + 1$, avec $n$ entier. Le $n$-ème nombre de Fermat, $2^{2^n} + 1$, est noté $F_n$.

Ces nombres doivent leur nom au mathématicien français Pierre de Fermat (1601-1665) qui émit la conjecture que tous ces nombres étaient premiers. Cette conjecture se révéla fausse, $F_5$ étant composé, de même que tous les nombres de Fermat jusqu'à $F_{32}$. On ne sait pas si les nombres à partir de $F_{33}$ sont premiers ou composés. Les seuls nombres de Fermat premiers connus sont donc $F_0$, $F_1$, $F_2$, $F_3$ et $F_4$.

Ces nombres disposent de propriétés intéressantes, en général issues de l'arithmétique modulaire ; en particulier, Carl Friedrich Gauss a établi un lien entre ces nombres et la construction à la règle et au compas des polygones réguliers : un polygone régulier à n côtés peut être construit à la règle et au compas si et seulement si n est une puissance de 2, ou le produit d'une puissance de 2 et de nombres de Fermat premiers distincts.


\pagebreak
\section{PGCD - PPCM}
\noindent Soient $a$ et $b$ deux entiers non tous les deux nuls. 
On notera $\mathscr D (a,b)$ l'ensemble de leurs diviseurs communs.

\subsection{Généralité}
\begin{defi}[et Propriété]$\mathscr D (a,b)$ est un ensemble non vide fini. 
Il admet donc un plus grand élément, appelé $PGCD(a,b)$ (Plus Grand Diviseur Commun de $a$ et $b$). On le note parfois $a\wedge b$. \newline
L'ensemble des multiples communs strictement positifs de $a$ et $b$ est un ensemble dénombrable minoré. 
Il admet un plus petit élément, appelé $PPCM(a,b)$ (Plus Petit Multiple Commun de $a$ et $b$). \end{defi}

\Expls{$PGCD(4,6)=2 \qquad PGCD(12,13)=1 \qquad PGCD(21,35)=7$ \newline
$PPCM(4,6)=12 \qquad PPCM(12,13)=156 \qquad PPCM(21,35)=105$}\\

\begin{defi}On dit que $a$ et $b$ sont premiers entre eux si et seulement si $PGCD(a,b)=1$\end{defi}

\Expls{$PGCD(3,2)=1 \qquad PGCD(10,21)=1 \qquad PGCD(51,113)=1$}\\

\begin{prop}[Immédiates]\begin{enumerate}
\item $0 < PGCD(a,b)=PGCD(b,a)=PGCD(|a|,|b|) < min(|a|,|b|)$
\item $PGCD(a,0)=|a|$
\item $PGCD(a,1)=1$
\item Si $b|a$ alors $PGCD(a,b)=|b|$
      \end{enumerate}
\end{prop}

\Rq{
Dans tout le chapitre, sauf indication contraire, on considérera désormais les diviseurs positifs 
communs à deux entiers naturels $a$ et $b$ non tous les deux nuls.}

\begin{prop}[Réduction]
L'ensemble des diviseurs de $a$ et $b$ est égal à l'ensemble des diviseurs de $b$ et $a-b$. 
En fait :
$$\mathscr D (a,b)=\mathscr D (a-b,b)=\mathscr D (a-kb,b) \quad \textrm{ pour tout } k \in\Z$$ 
\end{prop}

\Dem{Il s'agit de montrer une double inclusion. Soit $k\in\Z$.\\
$\mathscr D (a,b) \subset \mathscr D (a-kb,b) : $
Si $d$ divise $a$ et $b$, il divise aussi $a-kb$.\\
$\mathscr D (a,b) \supset \mathscr D (a-kb,b) : $
Si $d$ divise $b$ et $a-kb$ alors il divise $(a-kb) + kb=a$.\\
D'où l'égalité $\mathscr D (a,b) = \mathscr D (a-kb,b)$. En prenant $k=1$, on obtient la propriété.
}

\Expl{
$p$ et $q$ étant deux entiers naturels non nuls, on note $a=9p+4q$ et $b=2p+q$.
\begin{enumerate}
 \item Démontrer que $pgcd(a,b)=pgcd(p,q)$
 \item Démontrer que $9p+4$ et $2p+1$ sont premiers entre eux.
 \item Déterminer $pgcd(9p+4,2p-1)$ en fonction des valeurs de $p$. Vérifier pour $p=5$ et $p=9$.\\
\end{enumerate}
}


\begin{coro}Si $0 < b \leq  a $, alors $\mathscr D (a,b)=\mathscr D (r,b)$ où $r$ est le reste de la division euclidienne de $a$ par $b$.
\end{coro}
\Dem{Cas particulier de la propriété précédente puisque $r$ est tel que $a=bq+r \Leftrightarrow a-bq=r$ avec $q \in\N$}



\subsection{Détermination du PGCD et du PPCM}

\subsubsection{Lien PGCD -PPCM}

\begin{prop}[Relation PGCD-PPCM]
Si $d=pgcd(a,b)$ et $m=ppcm(a,b)$ alors $md=ab$.
\end{prop}

\Dem{
$d=pgcd(a,b)$ donc il existe $a'$ et $b'$ deux entiers tels que $a=da'$ et $b=db'$ avec $pgcd(a',b')=1$.\\
Considérons l'ensemble des multiples communs à $a$ et $b$. Soi t$M$ l'un quelconque d'entre eux. Alors il existe deux entiers $p$ et $q$ tels que :  \\
$$M=ap=bq \Rightarrow a'dp=b'dq \Leftrightarrow a'p=b'q$$
D'après le théorème de Gauss, on a alors que $a' |q$ d'où il existe un entier $k$ tel que $ka'=q$. Donc $M = ap= bq = ba'k = db'a'k$.\\
Ainsi tout multiple commun à $a$ et $b$ peut s'écrire sous la forme $M=da'b'k$.\\
De plus, tout nombre de la forme $da'b'k$ est un multiple de $a$ et $b$ car $da'b'k=ab'k=a'bk$.\\
Le multiples communs à $a$ et $b$ sont donc les multiples de $da'b'$. Le plus petit étant $m=da'b'=\dfrac{ab}{d}$.
}

\begin{prop}[Homogénéité]
Pour tout $k\in\N^*$ on a $PPCM(ka,kb)=kPPCM(a,b)$
\end{prop}


\Dem{Découle directement de la propriété ci-dessus et de l'homogénéité du pgcd.}


\subsubsection{Décomposition en facteurs premiers}
Soit $a$ et $b$ deux nombres dont voici la décomposition en facteur premier,  (faisant intervenir tous les nombres premiers qui interviennent dans la décomposition de $a$ et tous les nombres premiers qui interviennent dans celle de $b$, pour cela certain des $\alpha_i$ et des $\beta_i$ peuvent-être nul)  :
$$ a=p_1^{\alpha_1} p_2^{\alpha_2}\times \dots \dots p_n^{\alpha_n}\qquad \text{et} \qquad b=p_1^{\beta_1} p_2^{\beta_2}\times \dots \dots p_n^{\beta_n}$$
Alors :
$$ pgcd(a;b)=p_1^{min(\alpha_1,\beta_1)}p_2^{min(\alpha_2,\beta_2)}\times \dots \times p_n^{min(\alpha_n,\beta_n)}$$

\Expl{Déterminer le pgcd de $2^6\times 3^2\times 11^2\times 17$ et $3^4\times 7^4\times 11\times 19^2$. } 


\begin{prop}Soient $a$ et $b$ deux entier supérieur ou égaux à 2. Leur PPCM est le produit
 des facteurs premiers figurant dans l'une ou l'autre de leurs décompositions, 
 chacun étant affecté de son plus grand exposant.
\end{prop}

\Dem{Découle du lien PGCD-PPCM et de la manière de trouve le PGCD de deux nombres à partir de leurs décompositions.}

\subsubsection{Algorithme d'Euclide}
\noindent \textit{Il existe plusieurs méthodes pour trouver le pgcd de deux nombres, tels que :
\begin{enumerate}
\item Lister les diviseurs
\item Décomposer les nombres en produits de facteurs premiers
\item Faire l'algorithme d'Euclide, l'objet de cette partie.
\end{enumerate}
}

\noindent On cherche à déteminer $PGCD(a,b)$ où $a$ et $b$ sont deux nombres entiers tels que $0<b<a$. \\
On s'appuyera les résultats suivants  : 
\begin{itemize}
 \item Si $b|a$ alors $PGCD(a,b)=b$.
 \item Si $b$ ne divise pas $a$, alors $\exists \, ! \, (q,r)\in\N^2$ tel que $0 < r <b$ et 
l'on a $\mathscr D (a,b)=\mathscr D (b,r)$.\\
\end{itemize}

\noindent Dans le deuxième cas, comme $b<a$ et $r<b$, on s'est ramené à travailler sur des nombres plus petits.\\
De plus, comme $r>0$ ($b$ ne divise pas $a$), on peut réitérer le processus, autant de fois que nécessaire (c'est-à-dire tant que le reste n'est pas nul). \\
Il arrivera forcément un moment où le reste de la division sera nul, car la suite des restes est strictement décroissante, minorée par 0.\\
On aura alors $\mathscr D (a,b)=\mathscr D (b,r)=\mathscr D (r,r_1)=\mathscr D (r_1,r_2)=\dots =\mathscr D (r_k,0)$, d'où $pgcd(a,b)=r_k$.\\

\noindent Le principe de l'algorithme d'Euclide est donc d'effectuer des divisions euclidiennes successives et bien choisies. 
Le $pgcd$ des deux nombres sera donc le dernier reste non nul obtenu.\\


\Cadre[Algorithme d'Euclide]{
On note $D=pgcd(a,b)$. On cherche $D$
\begin{enumerate}
 \item J'effectue la division euclidienne de $a$ par $b$ : $a=bq+r$. On a alors $\mathscr D (a,b)=\mathscr D (b,r)$
  \item Si $r=0$ alors $\mathscr D (a,b)=\mathscr D (b,0)$ et $pgcd(a,b)=pgcd(b,0)=b$. \\
	Sinon :
	  \begin{itemize}
	  \item[$\circ$] On pose $r_0:=b$, $r_1:=r$, $i:=<1$
	  \item[$\circ$] Tant que $r_i \neq 0$ :
	      \begin{itemize}
	      \item J'effectue la division euclidienne de $r_{i-1}$ par $r_i$ : $r_{i-1}=r_iq_{i+1}+r_{i+1}$. \\
	      On a alors $\mathscr D (a,b)=\mathscr D (r_i,r_{i+1})$
	      \item $i$ prend la valeur $i+1$
	      \end{itemize}
	  \end{itemize}
 \item On a alors $\mathscr D (a,b)=\mathscr D (r_{i},r_{i+1})= \mathscr D (r_i,0)$ et  $pgcd(a,b)=pgcd(r_i,0)=r_i$.
 \end{enumerate}
}

\Expl{Trouver le pgcd de 246 et 168.
\begin{eqnarray*}
 264 & = & 168 \times 1 + 96\\ 
 168 &=& 96 \times 1 + 72 \\
 96 &=& 72 \times 1 + 24 \\
 72 &=& 24 \times 3+0
\end{eqnarray*}
Le dernier reste non nul est $24$ : c'est donc le pgcd de 264 et 168.
}


\subsection{Quelques propriétés}
\subsection{Propriétés}

\begin{prop}L'ensemble des diviseurs de $a$ et $b$ est aussi l'ensemble des diviseurs de leur pgcd.
$$\mathscr D (a,b)=\mathscr D (pgcd(a,b))$$
En particulier, tous les diviseurs communs à deux nombres sont aussi des diviseurs de leur pgcd.
\end{prop}

\Dem{Découle du fait que $\mathscr D (a,b)=\mathscr D (r_k,0)=\mathscr D (r_k)$, avec $r_k=pgcd(a,b)$
} \\

\begin{prop}[Homogénéité]
Pour tout $k\in\N^*$ on a $PGCD(ka,kb)=kPGCD(a,b)$
\end{prop}

\Dem{
Si $a=0$ ou $b=0$, c'est trivial.\\
Sinon, on peut faire l'algorithme d'Euclide dans lequel, chaque égalité est multipliée par $k$, dont celle contenant le dernier reste non nul.
}\\

\begin{prop}[Caractéristique]
$$\textrm{Soit } d\in\N. \qquad \qquad d=pgcd(a,b) \Longleftrightarrow \left\{\begin{array}{l}
                                         a=da' \textrm{ et } b=db' \\
					 pgcd(a',b')=1
                                         \end{array}\right. $$
\end{prop}

\Dem{$\Rightarrow$ : 
Si $d=pgcd(a,b)$ alors $d|a$ et $d|b$ et il existe $a'$, $b'$ tels que $a=da'$ et $b=db'$.\\
De plus, on a $pgcd(a,b)=pgcd(da',db')=d \times pgcd(a',b')$. Donc nécessairement $pgcd(a',b')=1$.\\
$\Leftarrow$  : Si $a=da'$ et $b=db'$ avec $pgcd(a',b')=1$. \\
Comme $a$ et $b$ ne sont pas tous les deux nuls, on a $d\neq 0$ et donc $pgcd(a,b)=d \times pgcd(a',b')=d$.
}

\Rq{Toute fraction peut alors s'écrire sous forme irréductible.}


\begin{prop}Soient $a$ et $b$ deux entier supérieur ou égaux à 2.
\begin{itemize}
 \item S'ils n'ont aucun facteur commun, $pgcd(a,b)=1$
 \item Sinon, $pgcd(a,b)$ est égal au produit des facteurs premiers communs aux deux nombres,
 chacun étant affecté du plus petit exposant avec lequel il figure dans leur deux décomposition.
\end{itemize}
\end{prop}

\Dem{Découle de l'homogénéité.}
\section{Equation diophantienne - théorème de bezout et de gauss.}





\subsection{Théorème de Bezout}


Etienne Bezout (1730-1783) fut un génie assez précoce puisqu'à 19 ans, il était déjà adjoint de l'Académie des Sciences. Sa plus grande oeuvre, 
\textit{Théorie générale des équations algébriques}, un traité clair et détaillé, témoigne de sa pédagogie et de sa volonté de rendre parfaitement 
accessibles ses découvertes. \\
Bézout fit aussi une brillante carrière dans la marine royale et de chargé de l'enseignement des élèves du corps d'artillerie.\\

\begin{prop}Soient $a$ et $b$ deux entiers relatifs non tous les deux nuls et $d=pgcd(a,b)$.
\begin{enumerate}
 \item Il existe $u$ et $v$ entiers relatifs tels que $au+bv=d$
 \item L'ensemble des entiers $au+bv$ (avec $u$ et $v$ entiers relatifs) est l'ensemble des multiples de $d$.
\end{enumerate}
\end{prop}

\Dem{\begin{enumerate}
      \item On utilise l'algorithme d'Euclide. On a :\\
$a=bq_0+r_0 \Longleftrightarrow r_0 = a-bq_0 = au_0 + bv_0$ avec $u_0=1$ et $v_0=-q_0$ deux entiers relatifs.\\
$b=r_0q_1 + r_1 \Longleftrightarrow r_1 = b-r_0q_1 = b-(au_0+bv_0)q_1 = au_1+ bv_1$ avec $u_1=-u_0q_1$ et $v_1=1-v_0q_1$ deux entiers.\\
Pas à pas, on exprime chaque reste comme combinaison linéaire enitère de $a$ et $b$ jusqu'à $r_k$, ie le $pgcd(a,b)$.
\item $\subset$ : Soit $n=au+bv$ alors comme $d$ divise $a$ et $b$ on a $d|n$, ie $n$ est un multiple de $d$.\\
$\supset$ :  Soit $n$ un multiple de $d$. On sait qu'il existe $u$ et $v$ tels que $d=au+bv$. Alors il existe $k$ tel que $n=kd=k(au+bv)=aU+bV$. 
Donc $n$ est une  combinaison linéaire de $a$ et $b$.
     \end{enumerate}
}\\

\begin{theo}[de Bezout]Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement si il existe des entiers relatifs $u$ et $v$ tels que $au+bv=1$.\end{theo}

\Dem{$\Rightarrow$ : Si $a$ et $b$ sont premiers entre eux, on applique la propriété pour $d=1$.\\
$\Leftarrow$ : S'il existe des entiers relatifs $u$ et $v$ tels que $au+bv=1$ alors d'après la propriété, $1$ est un multiple du $pgcd(a,b)$. 
Par conséquent $d=1$.
}

\Expl{\begin{itemize}
 \item $a=4$ et $b=9$ sont premiers entre eux et $9\times 1 - 4 \times 2 = 1$. Donc $(u,v)=(-2;1)$ convient.
 \item $a=7$ et $b=17$
 \item $a=71$ et $b=19$
 \item Montrer que pour tout $n\in\Z$, $n$ et $n+1$ sont premiers entre eux
 \item Même question pour $2n+1$ et $3n+1$.
      \end{itemize}
}

\Rq{Il découle du théorème que l'équation $ax+by=c$, avec $d=pgcd(a,b)\neq 0$ admet  des solutions entières si et seulement si $d|c$}


\begin{exoi}
Montrer que, pour tout entier naturel $n$, $2n+5$ et $3n+7$ sont premiers entre eux.
\end{exoi}

\begin{exoi}
Déterminer le $PGCD(2n+1;2n+3)$ pour tout entier naturel $n$
\end{exoi}
\subsection{Théorème de Gauss}


Carl Friedrich Gauss (1777-1855) fut un mathématicien, astronome et physicien allemand. Il n'existe pas un seul domaine scientifique qu'il n'ait pas abordé, et on lui doit, 
entre autres, des travaux sur les polygone régulier, sur les nombres complexes, le magnétisme, l'algèbre et bien sûr, l'arithmétique.
Il s'impliqua de plus dans les affaires politiques de son temps.\\

\begin{theo}Soient $a$, $b$, et $c$ trois entiers relatifs non nuls.\\
Si $a|bc$ et $pgcd(a,b)=1$ alors $a|c$.\end{theo}

\Dem{
$a|bc$ donc il existe $k\in\Z$ tel que $bc=ka$.\\
$a$ et $b$ sont premiers entre eux, donc il existe $(u,v)\in\Z^2$ tels que $au+bn=1$. \\
Donc $c=cau+cbv = cau + kav = a(cu+kv)$ avec $cu+kv$ entier. Donc $a|c$.
}\\

\begin{coro}
Si deux entiers $a$ et $b$ divise un entier $c$ avec $pgcd(a,b)=1$ alors $ab|c$.
\end{coro}

\Dem{
$a|c$ donc il existe un entier $k$ tel que $c=ka$. De même il existe un entier $k'$ tel que $c=bk'$.\\
Donc $ak=bk'$ et $a|bk'$. Comme $a$ et $b$ sont premiers entre eux on a $a|k'$.\\
Alors il existe un entier $l$ tel que $k'=al$ et $c=bk'=bal$. Donc $ab|c$.
}

\Rq{Par conséquent :
\begin{itemize}
 \item Si un nombre premier $p$ divise un produit $ab$, alors $p|a$ ou $p|b$
 \item Si un entier $a$ est premier avec des entiers $b_1$, $b_2$, $\dots$, $b_n$, alors $a$ est premier
 avec $b_1\times b_2 \times \dots \times b_n$.
 \item L'unicité de la décomposition en nombre premier vu au chapitre 2 en découle.
\end{itemize}
}

\begin{exoi}
\begin{enumerate}
\item Résoudre dans $\Z$ l'équation $3x=5y$.
\item Résoudre dans $\Z$ l'équation $273x=637y$.
\end{enumerate}
\end{exoi}

\subsection{Equations du type $ax+by=c$.}

\begin{defi}
Une équation diophantienne est une équation à coefficients entiers et dont les inconnues sont entières.\\
Cette année, nous ne résolvons que les équations de la forme $ax+by=k \times PGCD(a,b)$.
\end{defi}

\Expls{
\begin{itemize}
 \item $5x+7y=1$ \item $6x+15y=3$ \item $5x-8y=2$ \item $6x+14y=100$
\end{itemize}
}

\Cadre[Méthode de Résolution]{
\begin{enumerate}
 \item Simplification de l'équation.
\begin{itemize}
 \item On calcule $d=pgcd(a,b)$
 \item On divise l'équation par $d$ : on obtient $a'x+b'y= d'$ avec $pgcd(a',b')=1$
\end{itemize}
 \item Recherche d'une solution particulière :
\begin{itemize}
 \item On cherche $(x_0,y_0)\in\Z^2$ tels que $a'x_0+b'y_0=d'$ à l'aide des divisions euclidiennes
\end{itemize}
 \item Recherche de toutes les solutions :
\begin{itemize}
 \item On désigne par $x$ et $y$ d'autres solutions. On a alors $a'(x-x_0)+b'(y-y_0)=0 \Leftrightarrow a'(x-x_0)=-b'(y-y_0)$
 \item D'après le théorème de Gauss, on a alors que $a'|(y-y_0)$ ie qu'il existe $k\in\Z$ tel que $ka'=y-y_0 \Leftrightarrow y=ka'+y_0$.
 \item Alors $a'(x-x_0)=-b'\times ka' \Leftrightarrow x=-b'k + x_0$
\end{itemize}
\item Conclusion : Les solutions sont les couples de la forme $(-b'k+x_0 ; a'k + y_0)$, avec $k\in\Z$
\end{enumerate}
}

\begin{exoi}
On cherche les solutions entières de l'équation :
$$ (E) : 7x+13y=1$$
\begin{enumerate}
\item Déterminer une solution $(x_0;y_0)$ de $(E)$.
\item Montrer qu'une solution $(x;y)$ de $(E)$ vérifie l'équation :
$$ 7(x-x_0)=13(y_0-y)$$
\item Résoudre cette équation.
\end{enumerate}
\end{exoi}

\begin{exoi}
$a$ et $b$ étant deux entiers naturels non nuls et $c$ un entier relatif, on veut résoudre l'équation :
$$ax+by=c$$
\partieBac{Résolution de l'équation $au+bv=PGCD(a;b)$}
On note $g$ le PGCD de $a$ et $b$.
\begin{enumerate}
\item Justifier qu'il existe un couple $(u_0;v_0)$ solution de cette équation.
\item On suppose qu'il existe une autre solution $(u;v)$ et on pose $a'=\dfrac{a}{g}$ et $b'=\dfrac{b}{g}$.
\begin{enumerate}
\item Montrer que $au+bv=au_0+bv_0$, puis que $a'(u-u_0)+b'(v-v_0)=0$.
\item En déduire que $a'$ divise $b'(v_0-v)$, puis à l'aide du théorème de Gauss que $a'$ divise $v_0-v$.
\item Justifier qu'il existe un entier relatif $k$ tel que $v=v_0-ka'$ puis montrer que $u=u_0+kb'$.
\item Réciproquement, montrer que, quel que soit l'entier relatif $k$, les couples $(u_0+kb';v_0-ka')$ sont solutions de l'équation $au+bv=g$.
\end{enumerate}
\item $PGCD(15;9)=3$. Déterminer l'ensemble des solutions entières de l'équation $15x+9y=3$.
\end{enumerate}
\partieBac{Résolution de l'équation $ax+by=c$.}
\begin{enumerate}
\item Montrer que si $c$ n'est pas un multiple de $g$ alors l'équation $ax+by=c$ n'admet pas de solution.
\item On suppose désormais que $c$ est un multiple de $g$ et que $c=c'g$ avec $c'$ entier relatif.\\
Montrer que l'équation $ax+by=c\Longleftrightarrow a'x+b'y=c'$.
\item Montrer qu'il existe un couple $(x_0;y_0)$ solution de l'équation $a'x+b'y=c'$.
\item Résoudre alors l'équation $a'x+b'y=c'$ en vous inspirant de la partie A.
\item Résoudre $15x+9y=21$.
\end{enumerate}
\partieBac{Applications}
Léo prend le métro pour aller au travail. A la station Bézout, il doit changer de rame, la correspondance est sur le même quai. Il sait que son premier métro (Ligna A - durée du trajet 8 minutes) passe toutes les $7$ minutes et le second (ligne B) toutes les $11$ minutes. Ce matin il a pris son premier métro à $6$ h 52, il est arrivé à $7h$ à la station Bézout et il a du attendre $6$ minutes la rame de la ligne $B$.\\
Léo voudrait savoir à qu'elle heure partir entre $6h$ et $9h$ pour ne pas attendre la rame de la ligne B à la station Bézout.\\
On note $x$ le nombre de rames de la ligne $A$ et $y$ le nombre de rames de la ligne $B$ passées à la station Bézout \textbf{après} $7$ h.
\begin{enumerate}
\item Montrer que, pour que l'attente soit nulle à la station Bézout, $x$ et $y$ doivent vérifier l'équation $(E_1) : 7x-11y=-12$.
\item Déterminer une solution particulière de $(E_1)$.
\item Déterminer l'ensemble des solutions de $(E_1)$.
\item Déterminer à quelles heures entre $6$ h et $9$ h, Léo peut prendre son premier métro pour ne pas attendre à la station Bézout.
\end{enumerate}
\end{exoi}

\subsection{Petit théorème de Fermat.}
\begin{theo}[Petit Théorème de Fermat]
Si $p$ est un entier premier et $a$ un entier naturel non divisble par $p$, alors $a^{p-1}-1$ est divisble par $p$  
(ou encore $a^{p-1} \equiv 1 \, [p]$)
\end{theo}

\Dem{On suppose donc que $a$ n'est pas divisible par $p$.\\
On considère le nombre $$ N=a\times 2a\times 3a\times \dots \times (p-1)a=(p-1)! a^{p-1}$$
On note $r_k$ le reste de la division euclidienne de $ka$ par $p$, $k$ étant un nombre entre $1$ et $p-1$. Il résulte que :
$$ ka\equiv r_k (p)\qquad \text{et} \qquad 0\leq r_k<p$$
Si l'un des $r_k=0$ alors $p$ divise $ka$ donc d'après le lemme d'Euclide $p$ divise $k$ ou $p$ divise $a$. Ceci est impossible car d'une part $k<p$ et d'autre part on suppose que $p$ ne divise pas $a$.
Ainsi on peut affirmer que :
$$ ka\equiv r_k (p)\qquad \text{et} \qquad 0<r_k<p$$
De plus les $r_k$ sont deux à deux distincts, en effet si on suppose le contraire, c'est-à-dire qu'il existe $i<j$ tel que $r_i=r_j$ alors on obtient :
$$ ia\equiv ja (p) \Longrightarrow (j-i)a\equiv 0 (p)$$
Et on vient de montrer que $p$ ne divise pas $ka$, pour $0<k<p-1$ donc en particulier il ne divise pas $(j-i)a$. Ainsi les $p-1$ restes valent chacune des valeurs entières comprises entre $1$ et $p-1$.
\\
D'autre part puisque $N=a\times 2a\times 3a\times \dots \times (p-1)a$ on obtient :
$$ N\equiv r_1\times r_2\times \dots \times r_k (p)\Longleftrightarrow (p-1)!a^{p-1}\equiv r_1\times r_2\times \dots \times r_k (p)$$
c'est-à-dire compte tenu du fait que les $r_k$ valent toutes les valeurs entre $1$ et $p-1$ :
$$(p-1)!a^{p-1}\equiv (p-1)! (p) \Longleftrightarrow< (p-1)! \left(a^{p-1}-1\right)\equiv 0 (p) $$
Il vient que $p$ divise le produit $ (p-1)! \left(a^{p-1}-1\right)$, et puisqu'il ne divise pas $(p-1)!$ il divise d'après le lemme d'euclide $a^{p-1}-1$ ce qui montre le petit théorème de Fermat.
$$$$}
\Expl{$2^{2002}-1$ est divisible par $2003$ (qui est premier).}

\begin{exoi}
Déterminer un diviseur premier des nombres suivants :
$$ 2^{10}-1\qquad 4^{16}-4\qquad 4^{14}-4\qquad 6^6-1$$
\end{exoi}

\begin{exoi}
En écrivant $999999$ sous la forme $10^n-1$, déterminer un diviseur premier de $999999$ autre que $3$.
\end{exoi}

\begin{coro}
Si $p$ est un entier premier et $a$ un entier naturel, alors $a^p-a$ est divisible par $p$ 
(ou encore $a^{p} \equiv a \, [p]$)
\end{coro}

\Dem{Si $p$ divise $a$ alors $p$ divise en particulier $a^{p-1}\times a-a$ ce qui donne le résultat.
\\
Sinon on sait d'après le petit théorème de Fermat que $a^{p-1}\equiv 1 (p)$ donc en multipliant par $a$ on obtient le résultat voulu.}

\Expl{Déterminer tous les entiers $p$ premiers tels que $p|(2^p+1)$.}


\begin{exoi}
Soit $p$ un nombre premier, $a$ et $b$ deux entiers relatifs.
\begin{enumerate}
\item A l'aide du corollaire du petit théorème de Fermat, montrer que si $p$ divise $a+b$, alors $p$ divise $a^p+b^p$.
\item En déduire un diviseur de $5^{11}+6^{11}$ et vérifier ce résultat.
\item Déduire de la question $1.$ une valeur de $p$ telle que $5^p+7^p$ soit divisible par $p$.
\item Déterminer, par une démarche analogue, une valeur de $p$ telle que $11^p-4^p$ soit divisible par $p$.
\end{enumerate}
\end{exoi}

\subsection{Chiffrement de Hill}
\Cadre{Un message codé, assez long, dans lequel chaque lettre a été codée par une autre toujours de la même façon comme le codage affine, est assez facile à attaquer en s'appuyant par exemple sur la fréquence des lettres dans un texte suivant la langue.
  \\
  Une amélioration, publiée en 1931 par le mathématicien américain Lester Hill, consiste à coder des blocs de lettres, le codage d'une lettre dépendant alors de sa place dans le bloc.
  \\
  Comment fonctionne un tel codage sur des blocs de deux lettres ?}


\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$. 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.$$

\section{Exemple de chiffrement}
On souhaite chiffrer le mot ETUDIER.

On partage le mot en blocs de $2$ lettres : ET - UD - IE - RA (le dernier bloc est complété au hasard).
\subsection{Cle - $a=-5$, $b=8$, $c=-2$ et $d=3$}

\begin{enumerate}
\item Chiffrement du premier bloc ET.
Déterminer $x$ et $y$ puis en déduire $x'$ et $y'$. Vérifier que  ET est chiffré par  CX.
\item Terminer le chiffrement du mot ETUDIER.
\item Quelle remarque ce chiffrement occasionne-t-il ?
\end{enumerate}

\subsection{Clé $a=6$ $b=7$, $c=-8$ et $d=5$.}
Coder le mot ETUDIER avec cette clé. Quel problème cela pose-t-il ?

\section{Chiffrement et déchiffrement : approche mathématique}
Toujours suivant le même principe, posons par exemple :
$$(1) :\qquad  \left\{\begin{array}{cccc}
x'& \equiv & 5x+11y &(26)\\
y'&\equiv & 8x+3y&(26)
\end{array}\right.$$

\begin{enumerate}
\item Coder le mot REQUIN en détachant les trois blocs de deux lettres.
\item 
Montrer que si $x$, $y$, $x'$ et $y'$ vérifient $(1)$ alors  $\left\{\begin{array}{cccc}
-3x'+11y'& \equiv & 73x& (26)\\
8x'-5y'&\equiv & 73y&(26)
\end{array}\right.$
\item Résoudre dans $\Z\times \Z$, l'équation $73x+26y=1$ avec $0\leq x\leq 25$.\\
\textit{On se contentera de déterminer l'inverse de $73$ modulo $26$ puis de proposer une fonction de décodage.}
\item Décoder alors le mot XEJQVVLDVW.
\end{enumerate}
\pagebreak
\subsection{Code RSA}

Le but du jeu est bien sûr de pouvoir transmettre un message codé, que seul le récepteur \og officiel \fg{} puisse décrypter, c'est-à-dire qui ne puisse pas être décrypté par un tiers qui intercepterait ledit message. Nous appellerons Alice la destinatrice du message, et Bernard l'émetteur.

\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}}


\Expl{Voyons ce qui se passe si on prend pour les deux nombres $p$ et $q$ les valeurs $11$ et $17$.\\
On a alors $n=187$ et $\varphi(n)=(11-1)(17-1)=160$.\\
Comme $160=7\times 23+1$, on a $7\times 23\equiv 1 [\varphi(n)]$.\\
On peut prendre $e=7$ et $d=23$.\\
\\
Alice va rendre public le couple (la clé) $(187,7)$.\\
\\
Bernard veut transmettre à Alice un message codé (nécessairement un nombre plus petit que $n=187$, mettons la date à laquelle ils vont faire une surprise à Elodie (par exemple, le $10$), message qui ne doit pas être intercepté par ladite Elodie, bien sûr.\\
\\
Bernard va donc calculer $10^7 (187)$, or $10^7=187\times 53475+175$ donc $10^7\equiv 175 (187)$, et envoyer le résultat $175$ à Alice.\\
\\
Alice va calculer le reste de la division euclidienne de $175^{23}$ par $187$.
\\
En utilisant Python, en tapant $175^{23}\%187$ on trouve $10$.\\
Alice retrouve donc bien le message envoyé, à savoir $10$.
 }
 
 \begin{exoi}
\begin{enumerate}
 \item Trouver $n$, $p$, $q$, $d$, $e$ qui conviennent à un cryptage RSA.
 \item Transmettre la clé publique $(n,e)$ à vos voisins de gauche et de droite et conserver la clé privée $d$. 
 \item Coder votre jour de naissance à l'aide de la clé publique fournit par votre voisin de gauche et lui transmettre votre message crypté.
 \item Décrypter le message que vous a transmit votre voisin de droite et vérifier qu'il s'agit bien du bon message (en lui demandant confirmation).
 \item Avec la clé publique que vous a transmis votre voisin de droite, essayer de trouver la clé privée $d$.
 \end{enumerate}  
 \end{exoi}
 
 \pagebreak
 
 \begin{exoi}
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}
\end{document}