-\section{Algorithmes d'Euclide et applications}
-
-\subsection{PGCD de deux entiers}
-
-On a vu plus haut la justification de l'existence du PGCD de deux nombres strictement positifs par comparaison de leurs décompositions en facteurs premiers.\\
-
-
-Par définition, le PGCD de $a$ non nul avec 0 est $a$ (défintion raisonnable, car 0 est divisible par tout entier non nul, donc par $a$, qui l'est aussi par $a$) et enfin le PGCD de 0 et de 0 n'est pas
-défini.
-
-
-Il est possible de considérer des nombres négatifs (bien que ce soit sans grand intérêt dans les applications pratiques), mais le PGCD est celui des valeurs absolues.\\
-
-L'algorithme consistant à comparer les décompositions en facteurs premiers n'est pas efficace, la découverte de diviseurs de nombres très grands est un problème difficile dont nous reparlerons plus loin.
-
-
-\subsection{Algorithme d'Euclide}
-
-\subsubsection{Algorithme}
-\index{algorithme!d'Euclide}
-On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. \\
-
-\noindent Supposons par exemple $a>b$...
-
-\begin{enumerate}
-\item La division euclidienne de $a$ par $b$ peut s'écrire $a=bq+r$ avec $0\infeg r<b$.
-
-\item Soit $d$ un diviseur commun à $a$ et $b$, qui peuvent alors s'écrire $a=da'$ et $b=db'$.
-
-\item L'égalité $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun à $b$ et $r$.
-
-\item Réciproquement, soit $d$ un diviseur commun à $b$ et $r$, qui peuvent alors s'écrire $b=db'$ et $r=dr'$ et l'égalité $a=bq+r$ devient $a=d(b'q+r')$.
-
-Donc $d$ est un diviseur commun à $a$ et $b$, et, par inclusion réciproque, les ensembles des diviseurs communs à $a$ et $b$ d'une part et à $b$ et $r$ d'autre part sont identiques.
-
-En particulier $a\et b=b\et r$.
-
-\item Si $r=0$, le $a\et b=b$, sinon on peut effectuer la division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, tel que $r_{1}<r$ et $b\et r=r\et r_{1}$.
-
-\item Cet algorithme est itéré jusqu'à l'obtention d'un reste nul, ce qui se produit obligatoirement puisqu'il s'agit d'entiers et que la suite des restes ainsi construite est strictement décroissante.
-
-\item Le PGCD est alors l'avant-dernier reste (le dernier non nul).
-\end{enumerate}
-
-
-\begin{Rem}
-Cet algorithme permet donc d'obtenir le PGCD de deux nombres sans connaître leurs décompositions en facteurs premiers.
-\end{Rem}
-
-\subsubsection{Programmation}
-
-Voici sa programmation itérative en C :
-
-\bigskip
-
-{\prol int pgcd ( int a , int b ) \{
-{\dec int r ;
-while ( b != 0 ) \{
-{\dec r = a \% b ;
- a = b ;
- b = r ;
- } \}
- return a ;
- }\}
- }
-
-\bigskip
-
-\noindent (en toute rigueur, il faudrait vérifier que $a$ et $b$ sont bien positifs; par ailleurs, cette fonction retourne 0 comme PGCD de 0 et de 0 : à vérifier avant l'appel).
-
-\bigskip
-
-Voici sa programmation récursive :
-
-\bigskip
-
- {\prol int pgcd ( int a , int b ) \{
-{\dec
-if ( b == 0 )
-{\dec return a ;}
-else
-{\dec return pgcd ( b , a \% b ) ;}
-}\}}
-
