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

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index babbac9..1fc13ca 100755
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -1,126 +1,32 @@
+\section{Principe de rÃ©currence }
 
-
-
-\section{Nombres entiers naturels ($\N$)}
-
-\subsection{DÃ©finition de $\N$}
-
-\subsubsection{DÃ©finition}
-
-\begin{Def}[Ensemble des entiers naturels]
-On appelle \emph{ensemble des nombres entiers naturels}\index{entiers naturels} $\N$ tout ensemble possÃ©dant les propriÃ©tÃ©s suivantes
+Pour dÃ©montrer par \emp{rÃ©currence}
+\index{rÃ©currence!restreinte} 
+qu'une propriÃ©tÃ© $P(n)$ est vraie quel que soit l'entier $n \ge n_0$, 
+on procÃ¨de en deux Ã©tapes:
 \begin{enumerate}
-\item Il existe une injection de $\N$ dans $\N$.
-
-Cette injection, appelÃ©e \emph{fonction de succession}\index{fonction!de succession}, sera notÃ©e $s$ dans la suite.
-
-L'image d'un entier $n$ par la fonction de succession $s$, soit $s(n)$, est appelÃ©e \emph{successeur} \index{successeur} de $n$.\\
-
-\item Il existe un Ã©lÃ©ment de $\N$ qui n'est le successeur d'aucun Ã©lÃ©ment de $\N$.
-
-Cet Ã©lÃ©ment est appelÃ© \og \emph{zÃ©ro}\fg{}\index{zÃ©ro} et notÃ© 0 dans la suite.
-
-\item Le \og \emph{Principe de rÃ©currence} \fg{} \index{principe de rÃ©currence} \index{rÃ©currence} est satisfait :
-
-Soit $M$ la partie de $\N$ constituÃ©e par les entiers qui possÃ¨dent une certaine propriÃ©tÃ© $p$. On note \og $p(n)$\fg{} le fait que l'entier $n$ possÃ¨de la propriÃ©tÃ© $p$.
-
-\begin{Th}[Principe de rÃ©currence]
-Il s'Ã©nonce ainsi : \og Si $M$ contient 0 et le successeur de chacun de ses Ã©lÃ©ments, alors $M=\N$.\fg{}
-\end{Th}
-
-
-Sous forme formalisÃ©e...
-
-Soit $M=\{n\in\N \mid p(n)\}$; si $0\in M$ et si $[n \in M \Imp s(n) \in M]$, alors $M=\N$.
-\end{enumerate}
-\end{Def}
-
-
-
-\begin{Rem}
- $M=\N$ signifie Ã©videmment que la propriÃ©tÃ© est
-possÃ©dÃ©e par tous les entiers naturels. C'est, en gÃ©nÃ©ral, la conclusion attendue d'un \og raisonnement par rÃ©currence\fg{}
-\end{Rem}
-
-
-\subsubsection{Sur la rÃ©currence}
-
-Il existe une version \og affaiblie\fg{} du principe de rÃ©currence : la rÃ©currence restreinte, qui permet de s'assurer qu'une propriÃ©tÃ© est vraie Ã  partir d'un certain rang...
-
-
-\begin{Th}[RÃ©currence restreinte]
-\index{rÃ©currence!restreinte}
-Soit $M=\{n\in\N \mid p(n)\}$.
-
-Si $p\in M$ et si, $[n \in M \Imp s(n) \in M]$, alors $M$ est de la forme $\{p,p+1,p+2,\ldots\}$.
-\end{Th}
-
-
-Il existe encore une version \og renforcÃ©e\fg{} : la rÃ©currence gÃ©nÃ©ralisÃ©e, qui permet de \og supposer la
-propriÃ©tÃ© vraie jusqu'Ã  l'ordre $n$\fg{}...
-
-
-\begin{Th}[RÃ©currence gÃ©nÃ©ralisÃ©e]
-\index{rÃ©currence!gÃ©nÃ©ralisÃ©e}
- Soit $M=\{n\in\N \mid p(n)\}$.
-
-Si, $\qqs p \in M$, $\{0,1,2,\ldots,p\} \sse M$ et si $s(p)\in M$, alors $M=\N$.
-\end{Th}
-
-\begin{Proof}
- Elle se dÃ©montre Ã  partir de la rÃ©currence \og normale\fg{}.
-\end{Proof}
-
-
-\begin{Rem}
-La rÃ©currence gÃ©nÃ©ralisÃ©e permet d'Ã©viter un double raisonnement par rÃ©currence.
-\end{Rem}
-
-\bigskip
-
-\noindent ManiÃ¨re correcte de rÃ©diger un raisonnement par rÃ©currence :
-
+\item on vÃ©rifie que $P(n_0)$ est vraie;
+\item\label{itm:2} on suppose que $P(n)$ est vraie pour un certain entier $n \ge n_0$, 
+  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 Soit $M$ l'ensemble des entiers naturels qui vÃ©rifient ... (mettre ici l'Ã©noncÃ© de la propriÃ©tÃ© que l'on cherche Ã  dÃ©montrer)
-
-\item Initialisation de la rÃ©currence : vÃ©rifier que 0 est Ã©lÃ©ment de $M$ (\og la propriÃ©tÃ© est vraie pour $n=0$\fg{})
-
-\item CaractÃ¨re hÃ©rÃ©ditaire de la propriÃ©tÃ© : soit $n$ un Ã©lÃ©ment de $M$ (cela a un sens, puisque l'on sait maintenant que $M$ n'est pas vide : il contient au moins 0), vÃ©rifions que $s(n)$ est encore Ã©lÃ©ment de $M$ (\og la propriÃ©tÃ© est vraie pour $n+1$\fg{})
+\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 $\Nat$ est un ensemble complÃ¨tement ordonnÃ©. 
 
-\bigskip
-
-\begin{Rem}
-Toute phrase, telle que celles que l'on peut souvent lire, de la forme \og supposons la propriÃ©tÃ© vraie pour $n$\fg{} devrait immÃ©diatement appeler la question : qu'est-ce que c'est que $n$ ?
-
-\begin{itemize}
-\setlength{\labelwidth}{100pt} 
- \item Si $n$ est \og un entier quelconque\fg{} , alors vous supposez la propriÃ©tÃ© vraie pour un entier quelconque, et il ne vous reste plus grand chose Ã  dÃ©montrer....
-
-\item Si $n$ est un entier fixÃ©, mettons 47, alors vous allez dÃ©montrer la propriÃ©tÃ© pour 48, et il vous restera pas mal de chemin Ã  faire\ldots
-\end{itemize}
-
-Non, ce que vous supposez, ce n'est pas que la propriÃ©tÃ© est vraie (pour quoi que ce soit), mais que $n$ est un entier pour lequel la propriÃ©tÃ© est vÃ©rifiÃ©e (cet entier Ã©tant Ã©videmment quelconque parmi ceux pour lesquels la propriÃ©tÃ© est vÃ©rifiÃ©e), ce n'est pas du tout la mÃªme chose. 
-\end{Rem}
-
-
-\subsubsection{Exercices}
-
-\paragraph{Une premiÃ¨re rÃ©currence}
 
 \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 que l'on a effectivement l'Ã©galitÃ©
+\item DÃ©montrer par rÃ©currence que l'on a effectivement l'Ã©galitÃ©
 \end{enumerate}
 \end{Exo}
 
 
-\paragraph{Somme d'entiers Ã©levÃ©s Ã  une puissance donnÃ©e}
-
-On montre, dans ce qui suit, une application de la technique de rÃ©currence, pour calculer $S_k(n) = 1^k+2^k+...+n^k, \forall k,n \in \N$ (d'autres techniques, plus efficaces, existent).
-
 \begin{Exo}
 On souhaite calculer $S_1(n) = 1+2+...+n$.
 \begin{enumerate}
@@ -157,9 +63,6 @@ Poursuivre le raisonnement pour $S_3(n)$. Cette mÃ©thode permet-elle de calculer
 \end{Exo}
 
 
-\paragraph{Autres exercices sur la rÃ©currence}
-
-
 \begin{Exo}
 Montrer que $\forall n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
 \end{Exo}
@@ -176,34 +79,14 @@ Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divi
 \end{Exo}
 
 
-\subsection{OpÃ©rations et relation d'ordre dans $\N$} 
-
-On suppose ici connues les opÃ©rations et la relation d'ordre classiques qui existent dans $\N$ : addition, multiplication, relation d'inÃ©galitÃ© au sens large.
-
-
-Ces Ã©lÃ©ments peuvent Ãªtre dÃ©finis rigoureusement, et toutes les propriÃ©tÃ©s dÃ©montrÃ©es par rÃ©currence.
-
-\begin{Ex}
-Par exemple, on peut dÃ©finir la relation $p\leqslant n$ par $\exi q\in\N,\ n=p+q$. 
-\end{Ex}
-
-\begin{Th}
-Les opÃ©rations prÃ©cÃ©dentes ont pour propriÃ©tÃ©s :
-\begin{itemize}
-\item l'addition est commutative, associative, il existe un Ã©lÃ©ment neutre (0),
-\item la multiplication est commutative, associative et admet aussi un Ã©lÃ©ment neutre (1),
-\item la multiplication est distributive sur l'addition,
-\item les entiers sont totalement ordonnÃ©s par l'inÃ©galitÃ©, et cette relation d'ordre est compatible avec l'addition et avec la multiplication.
-\end{itemize} 
-\end{Th}
-
 
-\subsection{Nombres premiers}
 
-\subsubsection{DÃ©finitions}
+\section{Nombres premiers}
 
 \begin{Def}[Multiple, diviseur]
-Si un entier $n$ peut s'Ã©crire sous la forme $n=pq$, oÃ¹ $p$ et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple} de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
+Si un entier $n$ peut s'Ã©crire sous la forme $n=pq$, oÃ¹ $p$
+et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple}
+de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
 \end{Def}
 
 
@@ -211,7 +94,7 @@ Si un entier $n$ peut s'Ã©crire sous la forme $n=pq$, oÃ¹ $p$ et $q$ sont des en
  Soit $m = 2^3 * 5 * 7^2 * 13^3$. Combien le nombre $m$ a-t-il de diviseurs naturels ?
 \end{Exo}
 
-\noindent RÃ©ponse : (3+1)*(1+1)*(2+1)*(3+1)=96.
+%\noindent RÃ©ponse : (3+1)*(1+1)*(2+1)*(3+1)=96.
 
 \begin{Def}[Nombre premier]
 Un \emph{nombre premier}\index{nombre!premier} est un nombre entier strictement supÃ©rieur Ã  1 qui n'est divisible que par 1 et par lui-mÃªme.
@@ -233,7 +116,7 @@ Il existe une infinitÃ© de nombres premiers.
 
 
 
-\subsubsection{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$.
@@ -256,6 +139,42 @@ La dÃ©composition d'un entier en ses facteurs premiers est unique.
 
 
 
+
+\subsection{Relation de divisibilitÃ©}
+
+Dans le chapitre sur les relations entre ensembles,
+on a vu la relation binaire de \og divisibilitÃ©\fg{} dÃ©finie dans $\Net$.
+Cette relation est une relation d'ordre partielle:
+il existe des paires d'entiers non comparables par cette relation.
+
+\begin{Ex}
+3 ne divise pas 7 et 7 ne divise pas 3.
+Ces deux entiers ne sont donc pas comparables du point de vue de la divisibilitÃ©. 
+\end{Ex}
+
+Cet ordre n'est donc que partiel, mais il existe, pour chaque 
+couple d'entiers distincts, une borne infÃ©rieure et une borne supÃ©rieure. 
+Cette relation engendre donc un treillis.
+
+
+\begin{Def}[PGCD, PPCM]
+Tout ensemble fini de nombres entiers strictement positifs admet une borne sup et une borne inf pour la relation de divisibilitÃ©.
+
+Cette borne infÃ©rieure et cette borne supÃ©rieure sont respectivement appelÃ©es \emph{plus grand commun diviseur}\index{plus grand commun diviseur} \index{PGCD} et \emph{plus petit commun multiple} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
+\end{Def}
+
+\begin{Notation}
+Ils sont respectivement notÃ©s $a\et b$ et $a\ou b$.
+\end{Notation}
+
+
+\begin{Def}
+Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$. 
+\end{Def}
+
+
+
+
 \begin{Exo}[Nombres de Fermat]
 On appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
 \begin{enumerate}
@@ -272,77 +191,147 @@ On appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
 \end{Exo}
 
 
-\subsection{Relation de divisibilitÃ©}
 
-On a vu dans le chapitre sur les relations entre ensembles la relation binaire de divisibilitÃ© dÃ©finie dans $\Net$.
+\section{Algorithmes d'Euclide et applications}
 
-Cette relation est une relation d'ordre partiel : il existe des paires d'entiers non comparables par cette relation.
+\subsection{PGCD de deux entiers} 
 
-\begin{Ex}
-3 ne divise pas 7 et 7 ne divise pas 3.
+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.\\
 
-Ces deux entiers ne sont donc pas comparables du point de vue de la divisibilitÃ©. 
-\end{Ex}
 
-Cet ordre n'est donc que partiel, mais il existe, pour chaque couple d'entiers distincts, une borne infÃ©rieure et une borne supÃ©rieure...
+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.
 
 
-\begin{Def}[PGCD, PPCM]
-Tout ensemble fini de nombres entiers strictement positifs admet une borne sup et une borne inf pour la relation de divisibilitÃ©.
+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.\\
 
-Cette borne infÃ©rieure et cette borne supÃ©rieure sont respectivement appelÃ©es \emph{plus grand commun diviseur}\index{plus grand commun diviseur} \index{PGCD} et \emph{plus petit commun multiple} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
-\end{Def}
+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.
 
-\begin{Notation}
-Ils sont respectivement notÃ©s $a\et b$ et $a\ou b$.
-\end{Notation}
 
-\begin{Proof}
-L'existence du PGCD dÃ©coule de l'existence de la dÃ©composition en facteurs premiers : il suffit de comparer les dÃ©compositions des deux nombres pour dÃ©couvrir leur PGCD.
+\subsection{Algorithme d'Euclide} 
 
-Le PPCM, lui, vaut $a\ou b=ab/(a\et b)$. 
-\end{Proof}
+\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 ) ;}
+}\}}
 
 
 \begin{Ex}
-Comme $48=2^43$ et que $56=2^37$, on voit aisÃ©ment que $48\et 56=2^3$.
+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 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$.
+\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$.
+\end{enumerate}
+\end{enumerate}
 \end{Ex}
 
-\begin{Exo}
- Calculez $ppcm(102,138)$.
-\end{Exo}
+% \begin{Ex}
+% Comme $48=2^43$ et que $56=2^37$, on voit aisÃ©ment que $48\et 56=2^3$.
+% \end{Ex}
 
-\noindent RÃ©ponse : 2346.
+% \begin{Exo}
+%  Calculez $102 \ou 138$.
+% \end{Exo}
 
-\begin{Th}
-$\Net$ est un treillis pour la divisibilitÃ©. 
+% \noindent RÃ©ponse : 2346.
 
-On peut de plus montrer que :
+% \begin{Th}
+% $\Net$ est un treillis pour la divisibilitÃ©. 
 
-\begin{itemize}
- \item ce treillis est distributif, c'est-Ã -dire que $x\ou(y\et z)=(x\ou y)\et(x\ou z)$ et que $x\et(y\ou z)=(x\et y)\ou(x\et z)$,
- \item il admet un Ã©lÃ©ment minimum (1), mais pas d'Ã©lÃ©ment maximum,
- \item les nombres premiers sont les Ã©lÃ©ments minimaux de ($\Net\moins\{1\}$).
-\end{itemize}
-\end{Th}
+% On peut de plus montrer que :
 
+% \begin{itemize}
+%  \item ce treillis est distributif, c'est-Ã -dire que $x\ou(y\et z)=(x\ou y)\et(x\ou z)$ et que $x\et(y\ou z)=(x\et y)\ou(x\et z)$,
+%  \item il admet un Ã©lÃ©ment minimum (1), mais pas d'Ã©lÃ©ment maximum,
+%  \item les nombres premiers sont les Ã©lÃ©ments minimaux de ($\Net\moins\{1\}$).
+% \end{itemize}
+% \end{Th}
 
 
-\begin{Def}
-Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$. 
-\end{Def}
 
-\begin{Exo}
- Soient $a,b,c,d$ des entiers naturels non nuls tels que $ad=bc$.
 
-Prouvez que si $a$ et $b$ sont premiers entre eux, alors $b|d$
-\end{Exo}
+% \begin{Exo}
+%  Soient $a,b,c,d$ des entiers naturels non nuls tels que $ad=bc$.
+
+% Prouvez que si $a$ et $b$ sont premiers entre eux, alors $b|d$
+% \end{Exo}
 
-\noindent RÃ©ponse : En se plongeant dans le calcul modulo $b$, on a : ad = 0.
+% \noindent RÃ©ponse : En se plongeant dans le calcul modulo $b$, on a : ad = 0.
 
-Comme $a$ et $b$ sont premiers entre eux, $a$ est inversible, et donc $d=0$.
+% Comme $a$ et $b$ sont premiers entre eux, $a$ est inversible, et donc $d=0$.
 
-On en dÃ©duit que $d$ est un multiple de $b$.
+% On en dÃ©duit que $d$ est un multiple de $b$.
 
 
 
@@ -908,90 +897,6 @@ OpÃ©ration binaire & Entiers non signÃ©s & Entiers signÃ©s \\
 
 
 
-\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}
