X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/blobdiff_plain/5e35d149cf50ea634e9a0c02fca2c79993d25427..51b2e980b2f878a95b131df419bf9b1026dc2ff0:/arithmetique/entiersNaturels.tex

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index fbc1326..945a103 100755
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -311,21 +311,22 @@ def pgcd_euclide(a,b) :
 \end{scriptsize}
 \bigskip
 
-\begin{Exo}
+\begin{Exo}[Application de l'algorithme d'Euclide]
 Si $p$ est un nombre premier, et $n$ un entier avec $n \ge 2$, on note 
 $a=p^n+1$ et  
 $b=p^n-1$.
 \begin{enumerate}
 \item On suppose que $p$ est égal à 2. 
 \begin{enumerate}
+\item Montrer que $2^n -1 = 2 \times (2^{n-1} -1) +1$ pour $n \ge 2$.
 \item Calculer $d = a \et b$ au moyen de l'algorithme d'Euclide.
-\item Déterminer tous les couples d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
+\item Déterminer un couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
 \end{enumerate}
 \item On suppose maintenant que $p$ est différent de 2. 
  \begin{enumerate}
 \item Montrer que $a$ et $b$ sont pairs et poser $a=2A$ et $b=2B$. 
 \item Calculer $A-B$. En déduire la valeur $d$ de $a \et b$.
-\item Déterminer tous les couples d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
+\item Déterminer un  couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
 \end{enumerate}
 \end{enumerate}
 \end{Exo}
@@ -427,6 +428,208 @@ On se place dans l'ensemble $\N$.
 \end{Exo}
 
 
+
+
+\section{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}
+\begin{enumerate}
+\item Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors les quotients obtenus sont premiers entre eux.
+
+\item Réciproquement, montrer que, si les quotients obtenus en divisant $a$ et $b$ par un diviseur commun $d$ sont premiers entre eux, alors $d=\textit{PGCD}(a,b)$.
+\end{enumerate}
+\end{Exo}
+
+% \noindent Réponse : Soit $d = \textit{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é}
+
+
+
+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$.
+
+\subsection{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}
+
+
+\subsection{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 $\textit{PGCD}(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602.
+\end{Exo}
+
+
+
+\begin{Th}[Théorème de Gauss]
+Soient $a$, $b$ et $c$ trois entiers naturel non nuls. 
+Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$, 
+alors $a$ divise $c$.
+\end{Th}
+
+
+\begin{Exo}
+L'objectif est de résoudre l'équation $(E)$ d'inconnues $x$ et $y$ 
+$405x -120y =15$.
+\begin{enumerate}
+\item Trouver le pgcd de 405 et 120  à l'aide de l'algorithme d'Euclide.
+\item En déduire une solution particulière de cette équation.
+\item En utilisant la solution particulière, montrer que $(E)$ est 
+  équivalente à $27(x-3) = 8(y-10)$.
+\item Utiliser le théorème de Gauss pour montrer que 
+  l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. 
+\end{enumerate}
+\end{Exo}
+
+\begin{Exo}
+  On considère l'équation $\frac{x}{0}-\frac{y}{4}=3$ où $x$ et $y$ sont des entiers naturels. 
+ \begin{enumerate}
+\item Montrer que cela implique qu'il existe $k \in \N$ tel que  
+ $x= 9(k+ 3)$ et $y=4k$.
+\item Démontrer que le PGCD de $x$ et $y$ ne peut être qu’un diviseur de 108. 
+\item Soit $m$ le  ppcm de $x$ et de $y$. 
+  On envisage la décomposition de $m$ en facteurs premiers. 
+  Trouver l'ensemble des entiers naturel $k$ pour que 
+  \begin{enumerate}
+ \item $m$ ne contienne pas le facteur 2.
+ \item $m$ contienne le facteur 2 ou le facteur $2^2$.
+\item  $m$ ne contienne pas le facteur 3.
+\item  $m$ contienne le facteur 3, ou le facteur $3^2$, ou le facteur $3^3$.
+\end{enumerate}
+\item Comment faut-il choisir $x$ et $y$ de telle façon que
+  l’on ait $\textit{PGCD}(x,y) = 18$? 
+\end{enumerate}
+\end{Exo}
+
+\begin{Exo}
+\begin{enumerate}
+\item Décomposer 319 en facteurs premiers. 
+
+\item Démontrer que si $x$ et $y$ sont deux entiers 
+  naturels premiers entre eux, il en est de même pour les 
+  nombres $3x + 5y$ et $x + 2y$. 
+\item Résoudre dans $\Z^2$ le système d’inconnues $a$ et $b$: 
+$$
+\left\{
+\begin{array}{rcl}
+(3a +5b)(a+2b) &= & 1276\\
+ab & = & 2m
+\textrm{ tel que  $m$ est le PPCM de $a$ et $b$. }
+\end{array}
+\right.
+$$
+\end{enumerate}
+\end{Exo}
+
+\begin{Exo}
+Au 8° siècle, un groupe composé d’hommes et
+de femmes a dépensé 100 pièces de monnaie dans une 
+auberge. 
+Les hommes ont dépensé 8 pièces chacun et les femmes 5
+pièces chacune. Combien pouvait-il y 
+avoir d’hommes et de femmes dans le groupe?
+\end{Exo}
+
+
 \section{Représentation des nombres entiers}
 
 
@@ -444,7 +647,7 @@ En informatique, on utilise couramment les bases 2, 8 et 16.
 
 
 
-\subsection{Obtention de cette représentation}
+
 
 L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
 
@@ -454,26 +657,20 @@ L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
 \item Les restes successifs (tous strictement inférieurs à $b$), et en commençant par le dernier, constituent la représentation en base $b$ de l'entier donné.
 \end{enumerate}
 
-
-% \subsection{Algorithme de Hörner}
-
-% Réciproquement, étant donnée la représentation en base $b$ d'un
-% entier, on obtient sa valeur par application de l'algorithme de Hörner :
-
-% $n= n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$ est calculé par 
-% $(......(((n_{p}b+n_{p-1})b+n_{p-2})b+\cdots+n_{1})b+n_{0})$
-
-
+\begin{Exo}
+Donner la représentation de 23 en base 2.
+\end{Exo}
 
 
 
 \begin{Exo}[Numération, changements de base]
 \begin{enumerate}
-\item Chercher les entiers dont le carré a, en représentation décimale, mêmes chiffres des dizaines et des unités. 
+\item Chercher les entiers dont le carré a, en représentation décimale, 
+le même chiffre pour les dizaines et les unités. 
 \item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de manière que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
 \item L'entier $n$ s'écrit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
-\item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas premier.
-\item soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
+\item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas  premier.
+\item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
 \end{enumerate}
 \end{Exo}
 
@@ -501,7 +698,7 @@ considère un rationnel $x=\fr pq$ , avec $q>0$, $p\in
 \Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
 les cas suivants:
 \begin{itemize}
-\item $x$ est entier (c'est à dire $q=1$)
+\item $x$ est entier (c'est à dire $q=1$).
 \item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
 pourra montrer que, si $q$ est premier avec 10, il existe un entier
 $k$, non nul, tel que $10^k\equiv 1\ [q]$).
@@ -526,8 +723,8 @@ $$x \equiv y [n] \Ssi \exi k \in \Z, x-y=k \cdot n $$
 \begin{Exo}
  Calculez :
 \begin{enumerate}
- \item $3*10^9 mod 97$,
-\item $3^{1024} mod 1037$.
+ \item $3*10^9 \mod 97$,
+\item $3^{1024} \mod 1037$.
 \end{enumerate}
 \end{Exo}
 
@@ -545,9 +742,9 @@ En effet :
 \begin{itemize}
 \item $\qqs x \in \Z, x-x=0=0 \cdot n$; or $0 \in \Z$, donc $x
 \equiv x [n]$ (réflexivité). \item Si $x \equiv y
-[n]$,$\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et,
+[n]$, $\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et,
 puisque $k \in \Z$, $(-k) \in \Z$, donc $y \equiv x [n]$ (symétrie).
-\item Si $x \equiv y [n]$,$\exi k\in\Z$, $x-y=k \cdot n$; si, de
+\item Si $x \equiv y [n]$, $\exi k\in\Z$, $x-y=k \cdot n$; si, de
 plus, $y \equiv z [n]$, $\exi l\in\Z$, $y-z=l \cdot n$; alors (par
 addition), $x-z=(k+l) \times n$; comme $k\in\Z$ et $l\in\Z$,
 $(k+l)\in\Z$, donc $x \equiv z [n]$ (transitivité).
@@ -704,8 +901,8 @@ Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution d
 $$\left\{\begin{array}{ccc}
 x & \equiv & 2\ [88] \\
 x & \equiv & 1\ [27] \\
-\end{array}\right.$$
-\item {\it Application: Problème du cuisinier}: Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or, toutes d'égale valeur.
+\end{array}\right..$$
+\item {\it Application au problème du cuisinier}: une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or, toutes d'égale valeur.
 
 Ils décident de se les partager également et de donner le reste éventuel au cuisinier. Celui-ci recevrait alors 3 pièces d'or. 
 
@@ -790,10 +987,8 @@ la représentation physique est la même.
 
 
 Comme il nous est difficile de représenter ici la liste compléte de tous ces entiers, nous allons illustrer ce propos en supposant que les entiers sont représentés sur 4 bits.
+Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)
 
-\subsubsection{Illustration dans le cas de 4 bits.}
-
-Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)\vskip 10pt
 \begin{center}\begin{tabular}{|c|c|c|c|} \hline
 code binaire & & a.s. & a.n.s. \\ \hline
 0000 & interprété par & 0 & 0 \\ \hline
@@ -836,15 +1031,11 @@ Mais il n'en reste pas moins que tous les entiers négatifs commencent par 1).
 Ainsi, il est facile de déduire la comparaison signée de la comparaison non signée : les codes qui commencent par 1 sont \og plus petits\fg{} que ceux qui commencent par 0, et, s'ils commencent par le même bit, c'est la comparaison non signée qui peut être utilisée.
 
 
-Mais il y a quand même deux instructions assembleur distinctes pour la comparaison signée et pour la comparaison non signée.
 
 
 
-\subsubsection{Quelques exemples de calculs.}
-
 Pour l'addition et la soustraction, les opérations et les tests de validité des résultats sont les mêmes en arithmétique signée et non signée.
-
-\noindent Pour la multiplication, l'instruction assembleur n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple).
+Pour la multiplication, l'instruction n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple).
 
 \begin{Ex}
 
@@ -935,143 +1126,4 @@ Opération binaire & Entiers non signés & Entiers signés \\
 \end{tabular} 
 \end{center}
 \end{Ex}
-
-
-
-
-
-
-\section{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é}
-
-
-
-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$.
-
-\subsection{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}
-
-
-\subsection{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
 \centerline{\x{Fin du Chapitre}}
\ No newline at end of file