-
-
-
-
-\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 ) ;}
-}\}}
-
-
-
-\subsection{Théorème de Bézout}
-
-
-On considère deux nombres entiers strictement positifs $a$ et $b$.
-
-\begin{Th}[Théorème de Bézout]
-\index{théorème!de Bézout}
-Il existe un couple d'entiers $u$ et $v$ tels que $au-bv=d$, où $d$ est le PGCD de $a$ et de $b$.
-\end{Th}
-
-\begin{Proof}
-On peut se ramener au cas où $a \et b=1$.
-
-En effet, si $d>1$, on peut écrire $a=a'd$ et $b=b'd$ avec $a' \et b'=1$; si le théorème est établi dans le cas du PGCD égal à $1$, on peut affirmer l'existence de $u$ et de $v$ tels que $a'u-b'v=1$; en multipliant les deux membres de cette égalité par $d$, on obtient $a'du-b'dv=d$,
-soit $au-bv=d$.
-
-Il suffit donc d'établir le théorème dans le cas où $d=1$ ($a$ et $b$ premiers entre eux). Plaçons nous dans $(\Z/b\Z)^*$ et considérons l'application de cet ensemble dans lui-même définie par $x \fc ax$. Essayons de résoudre $ax=ax'$, soit $a(x-x')=0$, soit encore $a(x-x') \equiv 0[b]$, ou finalement $a(x-x')=kb$, avec $k \in \Z$.
-
-Comme $a\et b=1$, $a$ ne divise pas $b$, donc divise $k$; on peut écrire $k=k'a$, il reste $x-x'=k'b$, donc $x \equiv x'[b]$, donc $x=x'$; finalement $ax=ax' \Imp x=x'$, donc l'application envisagée est injective; comme il s'agit d'un ensemble fini, elle est évidemment aussi surjective, donc il existe $u$ tel que $au=1$, ce qui s'écrit encore $au \equiv 1[b]$, ou encore $au=bv+1$, finalement $au-bv=1$.
-\end{Proof}
-
-
-
-\begin{Rem}
-Ce couple n'est pas unique.
-\begin{Proof}
-En effet, si $(u,v)$ est un couple de Bézout pour $(a,b)$, donc tel que $au-bv=d$, où $d=a\et b$, alors, pout tout $k$ dans $\Z$, $a(u+kb)-b(v+ka)= au-bv+kab-kab=au-bv=d$ aussi.
-\end{Proof}
-\end{Rem}
-
-
-
-\begin{Exo}
-Montrez que, si $m$ est multiple de deux nombres premiers entre eux $a$ et $b$, alors $m$ est multiple de $ab$.
-\end{Exo}
-
-\noindent Réponse : $1 = aa'+bb'$, donc $m = maa'+mbb'$. Or $m=ax=by$, donc $m = ab(ya'+xb')$.
-
-
-
-\begin{Exo}
-Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors les quotients obtenus sont premiers entre eux.
-
-Réciproquement, montrer que, si les quotients obtenus en divisant $a$ et $b$ par un diviseur commun $d$ sont premiers entre eux, alors $d=pgcd(a,b)$.
-\end{Exo}
-
-\noindent Réponse : Soit $d = pgcd(a,b)$, et $q_1$ et $q_2$ les quotients de $a$ et $b$ par $d$. Alors $d = aa'+bb' = d q_1 a' + d q_2 b'$. Donc $1 = q_1 a' + q_2 b'$ : $q_1$ et $q_2$ sont premiers entre eux. La réciproque est du même genre.
-
-
-
-\subsection{Algorithme d'Euclide généralisé}
-
-\subsubsection{Idée de base.}
-
-Pour deux entiers positifs $a$ et $b$, on a vu que l'algorithme d'Euclide s'écrit : $a \et b = b \et r$, où $r$ est le reste dans la division euclidienne de $a$ par $b$.\\
-
-
-En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on définit une famille finie $(r_0,r_1,\ldots,r_k,r_{k+1})$ par $r_i=q_{i+1}r_{i+1}+r_{i+2}$ (c'est-à-dire que $r_{i+2}$ est le reste dans la division euclidienne de $r_i$ par $r_{i+1}$).\\
-
-
-\noindent Cette famille...
-\begin{itemize}
-\item est strictement décroissante,
-\item est telle que $r_{k+1}=0$,
-\item vérifie $r_0 \et r_1 = r_1 \et r_2= \ldots = r_{k-1} \et r_k = r_k \et r_{k+1} = r_k \et 0 = r_k$.
-\end{itemize}
-
-\bigskip
-
-On remarque que $r_{k-1}$ est un multiple de $r_k$, puisque la division euclidienne de $r_{k-1}$ par $r_k$ s'écrit $r_{k-1}=q_kr_k$.\\
-
-Soit $d$ le PGCD de $a$ et de $b$ (évidemment, $d=r_k$), on peut écrire $1 \times r_k-0 \times r_{k-1} = d$ puis $1 \times r_{k-2} - q_{k-1} \times r_{k-1}=d$.\\
-
-
-D'une manière générale, si $(u,v)$ est un couple de Bézout pour $r_{i+1}$ et $r_{i+2}$, soit $u \cdot r_{i+1}+v \cdot r_{i+2}=d$, comme $r_i=q_{i+1}\cdot r_{i+1} + r_{i+2}$, on a $u\cdot r_{i+1}+v \cdot (r_i-q_{i+1}\cdot r_{i+1})=d$, soit $(u-q_{i+1}\cdot v)\cdot r_{i+1}+v \cdot r_i=d$.\\
-
-\subsubsection{L'algorithme.}
-\index{algorithme!d'Euclide!généralisé}
-Ceci donne l'idée de construire deux familles par les relations :
-\begin{itemize}
-\item $u_0=1$, $u_1=0$,$u_{i+2}=u_i-q_{i+1} \cdot u_{i+1}$
-\item $v_0=0$, $v_1=1$, $v_{i+2}=v_i-q_{i+1} \cdot v_{i+1}$.
-\end{itemize}
-
-C'est ce que l'on appelle algorithme d'Euclide généralisé. On a alors $(u_k,v_k,r_k)=(u,v,d)$, $u$ et $v$ tels que $a \cdot u+b \cdot v=d$.\\
-
-\begin{Pre}
-Pour cela, il suffit de montrer par récurrence que $\qqs i \in
-\{0,\ldots,k\}, r_0 \cdot u_i + r_1 \cdot v_i = r_i$.
-\begin{itemize}
- \item Initialisation de la récurrence : la relation est vraie pour $i=0$, en effet $r_0 \cdot u_0+r_1 \cdot v_0=r_0$, puisque $u_0=1$ et $v_0=0$.
-\item Caractère héréditaire de la propriété : en supposant que $i$ est un entier pour lequel $r_0 \cdot u_i + r_1 \cdot v_i =
-r_i$ et $r_0 \cdot u_{i+1}+r_1 \cdot v_{i+1}=r_{i+1}$, calculons $r_0 \cdot u_{i+2}+r_1 \cdot v_{i+2}= r_0 \cdot (u_i-q_{i+1} \cdot u_{i+1}) + r_1 \cdot (v_i-q_{i+1} \cdot v_{i+1}) = r_0 \cdot
-u_i+r_1 \cdot v_i-q_{i+1}\cdot (r_0 \cdot u_{i+1}+r_1 \cdot
-v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$.
-\end{itemize}
-\end{Pre}
-
-
-\subsubsection{Exemple.}
-
-Illustrons la mise en \oe{}uvre de cet algorithme...
-
-\begin{Ex}
-Soit à obtenir un couple de Bézout pour (23,17) :\vskip 10pt
-\begin{center}\begin{tabular}{c c c c}
-(23,1,0) & (17,0,1) & $\longrightarrow$ & $q=1$ \\
-(17,0,1) & (6,1,-1) & $\longrightarrow$ & $q=2$ \\
-(6,1,-1) & (5,-2,3) & $\longrightarrow$ & $q=1$ \\
-(5,-2,3) & (1,3,-4) & $\longrightarrow$ & $q=5$ \\
-(1,3,-4) & (0,-17,23) & $\longrightarrow$ & FIN
-\end{tabular}\end{center}\vskip 10pt
-On a bien $3 \times 23-4 \times 17=1$.\psaut
-\end{Ex}
-
-\begin{Rem}
-Il est possible d'obtenir -1 (ou $-d$ en général) comme résultat, donc $au-bv=-1$, cela dépend de la parité du nombre d'itérations effectuées dans l'algorithme précédent.
-
-Ce n'est pas un résultat faux, puisqu'alors $bv-au=1$ et qu'on a quand même un couple de Bézout pour $(b,a)$.\\
-
-S'il est nécessaire d'obtenir un couple $(u,v)$ tel que $au-bv=1$
-et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un couple $(u',v')$ tel que $bv'-au'=1$, il suffit de prendre $u=b-u'$ et $v=a-v'$ et, dans ces conditions $au-bv=a(b-u')-b(a-v')= ab -au' -ab +bv'=bv'-au'=1$.
-\end{Rem}
-
-\begin{Exo}
-Exprimer $pgcd(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602.
-\end{Exo}
-
-\noindent Réponse $14 = 1330*(-19)+602*42$.
-
-
-
-\gsaut
