X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/blobdiff_plain/beb8d60ba6a439d6c62b04baed82daeae79645bb..333558f52e52a5792ac99d50e89d3a9d837b9d67:/arithmetique/entiersNaturels.tex

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index fe36e3e..4f3126e 100755
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -10,19 +10,20 @@ on procÃ¨de en deux Ã©tapes:
   c'est l'hypothÃ¨se de rÃ©currence, et on dÃ©montre que $P(n+1)$ est vraie.
 \end{enumerate}  
 Le \emph{principe de rÃ©currence} dit alors que $P(n)$ est vraie quel que soit 
-l'entier $n \ge n_0$. Une variante consiste Ã  remplacer l'Ã©tape~\ref{itm:2} par 
-\begin{enumerate}
-\item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre 
-$n_0$ et $n$, et on dÃ©montre que $P(n+1)$ est vraie.
-\end{enumerate}
-Ceci se dÃ©duit du fait que $\N$ est un ensemble complÃ¨tement ordonnÃ©. 
+l'entier $n \ge n_0$. 
+% Une variante consiste Ã  remplacer l'Ã©tape~\ref{itm:2} par 
+% \begin{enumerate}
+% \item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre 
+% $n_0$ et $n$, et on dÃ©montre que $P(n+1)$ est vraie.
+% \end{enumerate}
+% Ceci se dÃ©duit du fait que $\N$ est un ensemble complÃ¨tement ordonnÃ©. 
 
 
 \begin{Exo}
 \begin{enumerate}
 \item Calculez 1, 1+3, 1+3+5, et 1+3+5+7.
 \item A quoi $1+3+5+7+...+(2n-1)+(2n+1)$ semble-t-il Ãªtre Ã©gal (en fonction de $n$) ?
-\item DÃ©montrer par rÃ©currence que l'on a effectivement l'Ã©galitÃ©
+\item DÃ©montrer par rÃ©currence que l'on a effectivement l'Ã©galitÃ©.
 \end{enumerate}
 \end{Exo}
 
@@ -58,13 +59,25 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \end{enumerate}
 \end{Exo}
 
+% \begin{Exo}
+% Poursuivre le raisonnement pour $S_3(n)$. Cette mÃ©thode permet-elle de calculer $S_k(n)$ pour tout $k$ et $n$ dans $\N$?
+% \end{Exo}
+
+
 \begin{Exo}
-Poursuivre le raisonnement pour $S_3(n)$. Cette mÃ©thode permet-elle de calculer $S_k(n)$ pour tout $k$ et $n$ dans $\N$?
+Soit la suite $(U_n)_{n\in \N}$ dÃ©finie par $U_n = 3^{2n+1} + 2^{n+2} $.
+\begin{enumerate}
+\item Calculer $U_0$, $U_1$ et $U_2$. Remarquer que ce sont tous 
+des multiples de $7$.
+\item Montrer que $U_{n+1} = 7 \times 3^{2n+1} + 2 U_n$.
+\item Montrer que $7$ est un multiple de $U_n$ pour tout entier naturel $n$.
+\end{enumerate}
 \end{Exo}
 
 
+
 \begin{Exo}
-Montrer que pour tout $n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
+Montrer que pour tout entier naturel $n$, 3 divise $4^n -1$.
 \end{Exo}
 
 \begin{Exo}
@@ -73,7 +86,6 @@ $$u_{n+2}-5u_{n+1}+6u_n = 0$$
 Montrez qu'il existe $\alpha, \beta \in \N$ tels quel pour tout $ n \in \N, u_n = \alpha 3^n + \beta 2^n$.
 \end{Exo}
 
-
 \begin{Exo}
 Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divisible par $m+n$.
 \end{Exo}
@@ -105,9 +117,9 @@ Un \emph{nombre premier}\index{nombre!premier} est un nombre entier strictement
 Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
 \end{Exo}
 
-\begin{Th}
-Il existe une infinitÃ© de nombres premiers.
-\end{Th}
+
+
+
 
 
 \begin{Rem}
@@ -116,10 +128,18 @@ Il existe une infinitÃ© de nombres premiers.
 
 
 
-\subsection{DÃ©composition en facteurs premiers}
+
+
+%\subsection{DÃ©composition en facteurs premiers}
 
 \begin{Def}[DÃ©composition en facteurs premiers]
-L'Ã©criture d'un entier $n$ sous la forme $n=a^{\alpha}b^{\beta}c^{\gamma}\ldots$, oÃ¹ $a\vir b\vir c\vir\ldots$ sont les diviseurs premiers distincts de $n$ et oÃ¹ les exposants $\alpha\vir\beta\vir\gamma\vir\ldots$ sont tels que, par exemple, $n$ est divisible par $a^{\alpha}$ mais pas par $a^{\alpha+1}$ s'appelle la \emph{dÃ©composition en facteurs premiers} \index{dÃ©composition en facteurs premiers} de $n$.
+L'Ã©criture d'un entier $n$ sous la forme $n=a^{\alpha}b^{\beta}c^{\gamma}\ldots$, oÃ¹ \begin{itemize}
+\item $a$, $b$, $c$, \ldots  sont des nombres premiers distincts 
+deux Ã  deux tels que $a < b < c <\ldots$;
+\item les exposants $\alpha$, $\beta$, $\gamma$ sont des entiers naturels 
+  non nuls;
+\end{itemize}
+\noindent s'appelle la \emph{dÃ©composition en facteurs premiers} \index{dÃ©composition en facteurs premiers} de $n$.
 
 On dit que les exposants $\alpha$, $\beta$, $\gamma$, \ldots sont les ordres de multiplicitÃ© des diviseurs $a$, $b$, $c$, \ldots
 \end{Def}
@@ -135,35 +155,61 @@ La dÃ©composition d'un entier en ses facteurs premiers est unique.
  \'Ecrivez les nombres 3850 et 1911 sous forme de produits de nombres premiers.
 \end{Exo}
 
-\noindent RÃ©ponses : $2*5^2*7*11$ et $3*7^2*13$.
 
 
 
+%\noindent RÃ©ponses : $2*5^2*7*11$ et $3*7^2*13$.
+
+
+\begin{Th}
+Il existe une infinitÃ© de nombres premiers.
+\end{Th}
+
+\begin{Exo}[Nombres premiers en quantitÃ© infinie]
+Supposons comme hypothÃ¨se que l'ensemble des nombres premiers $\{ p_1, p_2, p_3 \ldots p_{n-1}, p_n \}$ est de cardinalitÃ© finie $n$.
+On construit le nombre $N =  p_1. p_2. p_3. \ldots .p_{n-1}. p_n +1$.
+\begin{enumerate}
+\item Montrer que d'aprÃ¨s l'hypothÃ¨se, il existe un nombre premier $q$ tel que 
+  $N$ est un multiple de $q$.
+\item Montrer cependant que $N$ n'est pas un multiple de $p_1$. Idem pour $p_2$, \ldots $p_n$.
+\item En dÃ©duire que $q$ est un nombre premier diffÃ©rent de $p_1$, de $p_2$, \ldots de $p_n$. 
+\item En dÃ©duire une contradiction dans l'hypothÃ¨se.
+\end{enumerate}
+\end{Exo}
+
+
 
-\subsection{Relation de divisibilitÃ©}
+%\subsection{Relation de divisibilitÃ©}
 
-Dans le chapitre sur les relations entre ensembles,
-on a vu que la relation binaire de \og divisibilitÃ©\fg{} (notÃ©e $\mid$) 
-dÃ©finie dans $\Net$.
-est une relation d'ordre.
-Or 6 ne divise pas 14 et 14 ne divise pas 6.
-Ces deux entiers ne sont donc pas comparables.
-Cet ordre n'est donc que partiel.
+% Dans le chapitre sur les relations entre ensembles,
+% on a vu que la relation binaire de \og divisibilitÃ©\fg{} (notÃ©e $\mid$) 
+% dÃ©finie dans $\Net$.
+% est une relation d'ordre.
+% Or 6 ne divise pas 14 et 14 ne divise pas 6.
+% Ces deux entiers ne sont donc pas comparables.
+% Cet ordre n'est donc que partiel.
 
-Cependant 2 divise 6 et 14. C'est le plus grand des minorants de 6 et 14
-selon cette relation. C'est donc la borne infÃ©rieure.
-De mÃªme  6 divise 42 et 14 aussi. C'est le plus petit des majorants de 6 et 14
-selon cette relation. C'est donc la borne supÃ©rieure.
-Chaque couple d'entiers a donc  une borne infÃ©rieure et une borne supÃ©rieure. 
+% Cependant 2 divise 6 et 14. C'est le plus grand des minorants de 6 et 14
+% selon cette relation. C'est donc la borne infÃ©rieure.
+% De mÃªme  42 est divisible par 6 et 14 aussi. 
+% C'est le plus petit des majorants de 6 et 14
+% selon cette relation. C'est donc la borne supÃ©rieure.
+% Chaque couple d'entiers a donc  une borne infÃ©rieure et une borne supÃ©rieure. 
 
 
 
 \begin{Def}[PGCD, PPCM]
-Tout ensemble fini de nombres entiers strictement positifs admet 
-une borne supÃ©rieure
-et une borne infÃ©rieure pour la relation de divisibilitÃ©.
-Cette borne infÃ©rieure et cette borne supÃ©rieure sont respectivement appelÃ©es \emph{plus grand commun diviseur (PGCD)} \index{plus grand commun diviseur}  \index{PGCD} et \emph{plus petit commun multiple (PPCM)} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
-
+Soient $a$ et $b$ deux entiers naturels strictement positifs. 
+\begin{itemize}
+\item L'ensemble des diviseurs communs Ã  
+$a$ et $b$ admet un plus grand Ã©lÃ©ment $d$, 
+le \emph{plus grand commun diviseur (PGCD)}\index{plus grand commun diviseur}\index{PGCD}
+de ces entiers. On le note  $\textit{PGCD}(a,b)$. 
+\item L'ensemble des multiples strictement positifs
+  communs Ã  $a$ et $b$ admet un plus petit Ã©lÃ©ment $m$, 
+le \emph{plus petit commun multiple (PPCM)} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
+On le note $\textit{PPCM}(a,b)$.
+\end{itemize}
 Pour $a$ et $b$ dans $\N$, 
 $\textit{PGCD}(a,b)$ et 
 $\textit{PPCM}(a,b)$ et 
@@ -178,17 +224,27 @@ Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers en
 
 
 \begin{Exo}[Nombres de Fermat]
-Pour $p \in \N$, on appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
+Pour $p \in \N$, on appelle nombres de Fermat les nombres de la forme 
+$F_p = 2^{2^p}+1$.
+\begin{enumerate}
+\item Question prÃ©liminaire: montrer que les deux Ã©galitÃ©s suivantes sont Ã©tablies:
 \begin{enumerate}
-\item Montrer que, pour que $2^n+1$ soit premier, il faut que $n$ soit une puissance de 2.
+\item $x^n- 1 = (x-1)(x^{n-1}+x^{n-2}+\ldots+ x + 1)$  pour tout entier naturel $n$ strictement positif.
+\item $x^n+ 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots \pm x \mp 1)$  pour tout entier naturel $n$ impair
+\end{enumerate}
+
+\item Montrer que, 
+  pour que $2^n+1$ soit premier, il est nÃ©cessaire 
+  que $n$ soit une puissance de 2. 
 
-\item La rÃ©ciproque n'est pas vraie : donner un exemple de nombre de Fermat qui ne soit pas premier.
+\item Pour montrer que ce n'est pas suffisant, vÃ©rifier que $F_5$ est 
+  divisible par 641.
 
 \item Montrer que, pour $k\geqslant 1$, $F_p$ divise $F_{p+k}-2$.
 
 \item En dÃ©duire que $F_p$ et $F_{p+k}$ sont premiers entre eux.
 
-\item En dÃ©duire qu'il existe une infinitÃ© de nombres premiers.
+
 \end{enumerate}
 \end{Exo}
 
@@ -205,7 +261,8 @@ dÃ©fini.
 
 
 L'algorithme consistant Ã  comparer les dÃ©compositions en facteurs
-premiers n'est pas efficace, la dÃ©couverte de diviseurs de nombres
+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.
 
 
@@ -219,11 +276,17 @@ On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. Supposo
 \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'$. 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 Montrons que \og $d$ est un diviseur commun Ã  $a$ et $b$ \fg{}
+  est Ã©quivalent Ã   \og $d$ est un diviseur commun Ã  $b$ et $r$ \fg{}.
+\begin{itemize}
+\item  Soit $d$ un diviseur commun Ã  $a$ et $b$, qui peuvent alors s'Ã©crire $a=da'$ et $b=db'$. 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$.
+\end{itemize}
 
-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.
+Ainsi, 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$ on a $a\et b= b\et 0$ qui est Ã©gal Ã  $b$.
@@ -241,57 +304,42 @@ En particulier $a\et b=b\et r$.
 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).
+\begin{Exo}
+DÃ©terminer $154 \land 35$ par l'algorithme d'Euclide.
+\end{Exo}
 
-\bigskip
 
-Voici sa programmation rÃ©cursive :
+Voici sa programmation itÃ©rative en Python:
 
+\begin{scriptsize}
+\begin{verbatim}
+def pgcd_euclide(a,b) :
+    assert a>b and b >=0
+    while b != 0 :
+        r = a%b
+        a = b
+        b = r 
+    return a
+\end{verbatim}
+\end{scriptsize}
 \bigskip
 
- {\prol int pgcd ( int a , int b ) \{
-{\dec 
-if ( b == 0 )
-{\dec return a ;}
-else
-{\dec return pgcd ( b , a \% b ) ;}
-}\}}
-
-
-\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}
@@ -393,90 +441,206 @@ On se place dans l'ensemble $\N$.
 \end{Exo}
 
 
-\section{ReprÃ©sentation des nombres entiers}
 
 
+\section{ThÃ©orÃ¨me de BÃ©zout}
 
-\begin{Def}[Principe de la numÃ©ration de position]
-\index{Principe de la numÃ©rotation de position}
-Il consiste Ã  choisir une base $b$ de numÃ©ration, et $b$ symboles qui constitueront les chiffres dans la reprÃ©sentation d'un entier positif en base $b$.
-Celle-ci s'Ã©crira alors
-$$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$ 
 
-Cette Ã©criture est abrÃ©gÃ©e en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
-\end{Def}
+On considÃ¨re deux nombres entiers strictement positifs $a$ et $b$.
 
-En informatique, on utilise couramment les bases 2, 8 et 16.
+\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$.
 
-\subsection{Obtention de cette reprÃ©sentation}
+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$.
 
-L'algorithme pour obtenir la reprÃ©sentation en base $b$ d'un entier est :
+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{enumerate}
- \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
- \item Le quotient est Ã  sont tour divisÃ© par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'Ã  obtenir un quotient nul.
-\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}
+\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}
 
-% 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}
+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}[NumÃ©ration, changements de base]
+\begin{Exo}
 \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 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 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Ã©}
 
-\begin{Exo}[DÃ©veloppement dÃ©cimal]
-On considÃ¨re le nombre rÃ©el $x$ dont le dÃ©\-ve\-lop\-pe\-ment dÃ©cimal s'Ã©crit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la sÃ©quence $012\ 345\ 679$ est reproduite indÃ©finiment). Ce dÃ©veloppement dÃ©cimal est pÃ©riodique, de pÃ©riode 9.
-\begin{enumerate}
-\item Montrer que $x$
-vÃ©rifie une Ã©quation de la forme $10^kx=n+x$, oÃ¹ $k$ et $n$ sont
-des entiers Ã  dÃ©terminer. En rÃ©solvant cette Ã©quation,
-montrer que $x$ est un nombre rationnel, et le mettre sous la forme
-$x= \fr pq$ , oÃ¹ $p$ et $q$ sont premiers entre eux.
-\item Appliquer
-la mÃªme mÃ©thode au ``nombre" $y$ dont le dÃ©veloppement
-dÃ©cimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (pÃ©riodique de pÃ©riode
-1). Quelle conclusion peut-on en tirer?
-\item DÃ©montrer que tout nombre rÃ©el dont le dÃ©veloppement
-dÃ©cimal est fini ou pÃ©riodique Ã  partir d'un certain rang
-est un nombre rationnel.
-\item RÃ©ciproquement, on se propose de dÃ©montrer que le
-dÃ©veloppement dÃ©cimal de tout nombre rationnel est fini ou
-pÃ©riodique Ã  partir d'un certain rang. Pour cela, on
-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:
+
+
+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 $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]$).
-\item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
+\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}{9}-\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{ArithmÃ©tique modulo $n$} 
 
@@ -492,8 +656,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}
 
@@ -511,9 +675,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Ã©).
@@ -670,8 +834,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. 
 
@@ -694,11 +858,92 @@ Quel est le plus petit nombre de piÃ¨ces d'or qu'il espÃ¨re lorsqu'il dÃ©cide d'
 
 
 \begin{Exo}
-Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) mod p = 0$.
+Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) \mod p = 0$.
 VÃ©rifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de base 2.
 \end{Exo}
 
 
+
+\section{ReprÃ©sentation des nombres entiers}
+
+
+
+\begin{Def}[Principe de la numÃ©ration de position]
+\index{Principe de la numÃ©rotation de position}
+Il consiste Ã  choisir une base $b$ de numÃ©ration, et $b$ symboles qui constitueront les chiffres dans la reprÃ©sentation d'un entier positif en base $b$.
+Celle-ci s'Ã©crira alors
+$$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$ 
+
+Cette Ã©criture est abrÃ©gÃ©e en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
+\end{Def}
+
+En informatique, on utilise couramment les bases 2, 8 et 16.
+
+
+
+
+
+L'algorithme pour obtenir la reprÃ©sentation en base $b$ d'un entier est :
+
+\begin{enumerate}
+ \item Effectuer la division euclidienne de cet entier par $b$, division qui donne un premier quotient et un premier reste.
+ \item Le quotient est Ã  sont tour divisÃ© par $b$ pour donner un second quotient et un second reste, et ainsi de suite jusqu'Ã  obtenir un quotient nul.
+\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}
+
+\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, 
+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$.
+\end{enumerate}
+\end{Exo}
+
+
+
+\begin{Exo}[DÃ©veloppement dÃ©cimal]
+On considÃ¨re le nombre rÃ©el $x$ dont le dÃ©\-ve\-lop\-pe\-ment dÃ©cimal s'Ã©crit $x=0,012\ 345\ 679\ 012\ 345\ 679\ \ldots\ \ldots\ \ldots$ (la sÃ©quence $012\ 345\ 679$ est reproduite indÃ©finiment). Ce dÃ©veloppement dÃ©cimal est pÃ©riodique, de pÃ©riode 9.
+\begin{enumerate}
+\item Montrer que $x$
+vÃ©rifie une Ã©quation de la forme $10^kx=n+x$, oÃ¹ $k$ et $n$ sont
+des entiers Ã  dÃ©terminer. En rÃ©solvant cette Ã©quation,
+montrer que $x$ est un nombre rationnel, et le mettre sous la forme
+$x= \fr pq$ , oÃ¹ $p$ et $q$ sont premiers entre eux.
+\item Appliquer
+la mÃªme mÃ©thode au ``nombre" $y$ dont le dÃ©veloppement
+dÃ©cimal est $y= 0,999\ 999\ 999\ 999\ \ldots$ (pÃ©riodique de pÃ©riode
+1). Quelle conclusion peut-on en tirer?
+\item DÃ©montrer que tout nombre rÃ©el dont le dÃ©veloppement
+dÃ©cimal est fini ou pÃ©riodique Ã  partir d'un certain rang
+est un nombre rationnel.
+\item RÃ©ciproquement, on se propose de dÃ©montrer que le
+dÃ©veloppement dÃ©cimal de tout nombre rationnel est fini ou
+pÃ©riodique Ã  partir d'un certain rang. Pour cela, on
+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 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]$).
+\item $x$ est rationnel non entier, mais $q$ n'est pas premier avec 10.
+\end{itemize}
+\end{enumerate}
+
+\end{Exo}
+
+
+
 \section{ArithmÃ©tique en informatique}
 
 
@@ -756,10 +1001,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
@@ -802,15 +1045,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}
 
@@ -901,143 +1140,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
