X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/blobdiff_plain/53d3f77238e8e3cb2ff74399bf23d74402d3550a..8b65de9031d067d9806854c011a513c92dcf113e:/arithmetique/entiersNaturels.tex?ds=sidebyside

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index 0860dba..81ddb5b 100755
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -1,6 +1,6 @@
 \section{Principe de rÃ©currence }
 
-Pour dÃ©montrer par \emp{rÃ©currence}
+Pour dÃ©montrer par \emph{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:
@@ -10,36 +10,37 @@ 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 $\Nat$ 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}
 
 
-\begin{Exo}
-On souhaite calculer $S_1(n) = 1+2+...+n$.
-\begin{enumerate}
-\item Cherchez un bon candidat $S_1(n)$ pour cette formule.
-\begin{itemize}
-\item On pourra chercher un lien logique entre $S_1(1), S_1(2), S_1(3), S_1(4), ...$
-\item On pourra aussi faire le lien avec les suites arithmÃ©tiques.
-\item Ou encore, retrouver la mÃ©thode de Gauss : $S = 1+2+...+n$, et $S = n+(n-1)+...+2+1$. Si on somme ces deux expressions...
-\end{itemize}
-\item Prouvez, par rÃ©currence, que la somme est bien Ã©gale Ã  ce candidat.
-\item Quelle est la \og forme \fg{} de ce candidat (fonction tangente ? polynÃ´me ?) 
-\end{enumerate}
-\end{Exo}
+% \begin{Exo}
+% On souhaite calculer $S_1(n) = 1+2+...+n$.
+% \begin{enumerate}
+% \item Cherchez un bon candidat $S_1(n)$ pour cette formule.
+% \begin{itemize}
+% \item On pourra chercher un lien logique entre $S_1(1), S_1(2), S_1(3), S_1(4), ...$
+% \item On pourra aussi faire le lien avec les suites arithmÃ©tiques.
+% \item Ou encore, retrouver la mÃ©thode de Gauss : $S = 1+2+...+n$, et $S = n+(n-1)+...+2+1$. Si on somme ces deux expressions...
+% \end{itemize}
+% \item Prouvez, par rÃ©currence, que la somme est bien Ã©gale Ã  ce candidat.
+% \item Quelle est la \og forme \fg{} de ce candidat (fonction tangente ? polynÃ´me ?) 
+% \end{enumerate}
+% \end{Exo}
 
 
 \begin{Exo}
@@ -51,32 +52,41 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \item Ou encore, 
 \begin{itemize}
 \item Regardez la forme de $S_0(n) = 1^0+2^0+...+n^0$, et de $S_1(n) = 1^1+2^1+...+n^1$
-\item Interpolez la formule pour $S_2(n)$. On pourra imaginer que $S_2(n)$ est toujours un polynÃ´me en $n$. Quel serait son degrÃ© le plus probable ? Quelle en serait donc la forme ? On aura Ã  dÃ©terminer les coefficients intervenant dans ce polynÃ´me. Pour ce faire, il suffit de considÃ©rer que cette formule doit convenir pour n=1, 2, etc.
+\item Extrapolez la formule pour $S_2(n)$. On pourra imaginer que $S_2(n)$ est toujours un polynÃ´me en $n$. Quel serait son degrÃ© le plus probable ? Quelle en serait donc la forme ? On aura Ã  dÃ©terminer les coefficients intervenant dans ce polynÃ´me. Pour ce faire, il suffit de considÃ©rer que cette formule doit convenir pour n=1, 2, etc.
 \end{itemize}
 \end{itemize}
 \item DÃ©montrez, par rÃ©currence, que l'on a bien Ã©galitÃ© entre $1^2+2^2+...+n^2$ et votre candidat.
 \end{enumerate}
 \end{Exo}
 
-\begin{Exo}
-Poursuivre le raisonnement pour $S_3(n)$. Cette mÃ©thode permet-elle de calculer $S_k(n), \forall k,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$?
+% \end{Exo}
 
 
 \begin{Exo}
-Montrer que $\forall 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}
-Soit $(u_n)_{n \in \N}$ une suite rÃ©elle telle que $\forall n \in \N$,
-$$u_{n+2}-5u_{n+1}+6u_n = 0$$
-Montrez qu'il existe $\alpha, \beta \in \N$ tels quel $\forall n \in \N, u_n = \alpha 3^n + \beta 2^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}
+% Soit $(u_n)_{n \in \N}$ une suite rÃ©elle telle que pour tout $ n \in \N$,
+% $$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}
+% \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}
 
 
 
@@ -87,9 +97,9 @@ Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divi
 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$.
+On Ã©crit aussi $p \mid n$ pour $p$ divise $n$.
 \end{Def}
 
-
 \begin{Exo}
  Soit $m = 2^3 * 5 * 7^2 * 13^3$. Combien le nombre $m$ a-t-il de diviseurs naturels ?
 \end{Exo}
@@ -101,14 +111,30 @@ Un \emph{nombre premier}\index{nombre!premier} est un nombre entier strictement
 \end{Def}
 
 
-\begin{Ex}
+\begin{Exo}
 Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
-\end{Ex}
+\end{Exo}
 
 \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}
+
+
+
+
+
 
 \begin{Rem}
  Le problÃ¨me de la primalitÃ© d'un nombre (trÃ¨s grand, Ã©videmment) est difficile.
@@ -116,12 +142,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)
+On dit que les exposants $\alpha$, $\beta$, $\gamma$, \ldots sont les ordres de multiplicitÃ© des diviseurs $a$, $b$, $c$, \ldots
 \end{Def}
 
 
@@ -135,40 +167,49 @@ 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$.
 
 
 
 
-\subsection{Relation de divisibilitÃ©}
+%\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.
+% 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.
 
-\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}
+% 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. 
 
-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.
+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 
+sont respectivement notÃ©s $a\et b$ et $a\ou b$.
 \end{Def}
 
-\begin{Notation}
-Ils sont respectivement notÃ©s $a\et b$ et $a\ou b$.
-\end{Notation}
-
-
-\begin{Def}
+\begin{Def}[Nombres premiers entre eux]
 Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$. 
 \end{Def}
 
@@ -176,64 +217,73 @@ Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers en
 
 
 \begin{Exo}[Nombres de Fermat]
-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 Montrer que, pour que $2^n+1$ soit premier, il faut que $n$ soit une puissance de 2.
+\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.
+%\item En dÃ©duire qu'il existe une infinitÃ© de nombres premiers.
 \end{enumerate}
 \end{Exo}
 
 
 
-\section{Algorithmes d'Euclide et applications}
+\section{Algorithmes d'Euclide et applications}\index{algorithme!d'Euclide}
 
-\subsection{PGCD de deux entiers} 
+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.
 
-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.
+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.
 
 
-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$...
+On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. 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 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$, 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 Si $r=0$ on a $a\et b= b\et 0$ qui est Ã©gal Ã  $b$.
 
-\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 Sinon,  $r$ est diffÃ©rent de $0$ et on peut donc effectuer la
+  division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, 
+  tel que $0 \le r_{1}<r$ et $b\et r=r\et r_{1}$.
 
-\item Le PGCD est alors l'avant-dernier reste (le dernier non nul).
+\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.
+  Le PGCD est alors l'avant-dernier reste (le dernier non nul).
 \end{enumerate}
 
 
@@ -241,54 +291,55 @@ 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}[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 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 un  couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
+\end{enumerate}
+\end{enumerate}
+\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}
+% \begin{Exo}
+% Comme $48=2^43$ et que $56=2^37$, on voit aisÃ©ment que $48\et 56=2^3$.
+% \end{Exo}
 
-\begin{Exo}
- Calculez $102 \ou 138$.
-\end{Exo}
+% \begin{Exo}
+%  Calculez $102 \ou 138$.
+% \end{Exo}
 
-\noindent RÃ©ponse : 2346.
+% \noindent RÃ©ponse : 2346.
 
 % \begin{Th}
 % $\Net$ est un treillis pour la divisibilitÃ©. 
@@ -319,23 +370,14 @@ Comme $48=2^43$ et que $56=2^37$, on voit aisÃ©ment que $48\et 56=2^3$.
 
 
 
-\subsection{Entiers relatifs}
-
-L'ensemble habituellement notÃ© $\Z$ des entiers relatifs est obtenu Ã  partir de $\N$ par le procÃ©dÃ© de symÃ©trisation pour l'addition.\\
-
-
-Sans s'Ã©tendre sur le sujet, disons que cela consiste Ã  introduire les entiers strictement nÃ©gatifs comme opposÃ©s des positifs correspondants, par $n+(-n)=0$.\\
-
-
-On sait que les porpriÃ©tÃ©s des opÃ©rations sont conservÃ©es; la seule propriÃ©tÃ© perdue dans cette extension est la compatibiltÃ© entre la relation d'ordre et la multiplication.\\
-
-En revanche, on gagne Ã©videmment l'existence d'un opposÃ© pour chaque entier.
-
 
 
 \section{Division euclidienne dans $\Z$ et applications}
 
-\subsection{DÃ©finition}
+L'ensemble habituellement notÃ© $\Z$ des entiers relatifs
+est obtenu Ã  partir de $\N$ par le procÃ©dÃ© de symÃ©trisation pour l'addition: 
+cela consiste Ã  introduire les entiers strictement nÃ©gatifs comme
+opposÃ©s des positifs correspondants, par $n+(-n)=0$.
 
 
 On se donne deux entiers relatifs $a$ et $b$, $b$ non nul.
@@ -349,10 +391,10 @@ vÃ©rifient la relation suivante : $a=bq+r$ , avec $0\leqslant r<|b|$.
 \begin{Def}[Division euclidienne]
 Obtenir les valeurs de $q$ et de $r$, c'est effectuer la \emph{division
 euclidienne}\index{division euclidienne} de $a$ par $b$.
-
-$q$ est appelÃ© \emph{quotient}\index{quotient}, $r$ est appelÃ© \index{reste}\emph{reste} (dans la division euclidienne).
-
-Enfin, lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un \emph{diviseur} de $a$.
+Le nombre $q$ est appelÃ© \emph{quotient}\index{quotient}, et 
+le nombre $r$ est appelÃ© \index{reste}\emph{reste} 
+(dans la division euclidienne).
+Lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un \emph{diviseur} de $a$.
 \end{Def}
 
 
@@ -367,21 +409,16 @@ Tout nombre non nul est au moins divisible par 1 et par lui-mÃªme ($a=a\times 1+
 
 \begin{Exo}
 Quels sont le quotient et le reste de la division euclidienne de $m$ par $n$ dans le cas oÃ¹ :
-
 \begin{enumerate}
  \item $m = -38$ et $n=6$,
 \item $m=165$ et $n=-14$.
 \end{enumerate}
-
-RÃ©ponses : (-7,4) et (-11,11).
-
 \end{Exo}
 
 
 
-\begin{Exo}[DivisibilitÃ© dans $\N$]
+\begin{Exo}
 On se place dans l'ensemble $\N$.
-
 \begin{enumerate}
 \item Trouver les restes dans la division par 5 du carrÃ© d'un entier.
 \item Trouver les restes dans la division par 8 du carrÃ© d'un entier impair.
@@ -391,29 +428,24 @@ On se place dans l'ensemble $\N$.
 \end{Exo}
 
 
-\subsection{ReprÃ©sentation des nombres entiers}
+\section{ReprÃ©sentation des nombres entiers}
+
 
-\subsubsection{DÃ©finition}
 
 \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}$$ 
-\end{Def}
 
-
-\begin{Notation}
 Cette Ã©criture est abrÃ©gÃ©e en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
-\end{Notation}
+\end{Def}
 
-\begin{Rem}
 En informatique, on utilise couramment les bases 2, 8 et 16.
-\end{Rem}
 
 
-\subsubsection{Obtention de cette reprÃ©sentation}
+
+
 
 L'algorithme pour obtenir la reprÃ©sentation en base $b$ d'un entier est :
 
@@ -423,26 +455,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}
 
-
-\subsubsection{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}
 
 
-\subsubsection{Exercices}
 
 \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 Soit $n\geqslant 7$. Donner l'Ã©criture de $(n+1)^4$ en base $n$.
 \end{enumerate}
 \end{Exo}
 
@@ -470,7 +496,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]$).
@@ -481,20 +507,32 @@ $k$, non nul, tel que $10^k\equiv 1\ [q]$).
 \end{Exo}
 
 
-\subsection{ArithmÃ©tique modulo $n$} 
+\section{ArithmÃ©tique modulo $n$} 
 
 On rappelle ici la dÃ©finition de la relation dite de \og congruence modulo n\fg{} dÃ©finie dans $\Z$ Ã©tudiÃ©e dans le chapitre consacrÃ© aux relations entre ensembles.
 
 \begin{Def}[Congruence modulo $n$]
 Soit $n$ un entier strictement supÃ©rieur Ã  1 et $x$ et $y$ deux Ã©lÃ©ments de $\Z$.
-
 On dit que \og $x$ est \emph{congru} Ã  $y$ \emph{modulo}\index{congru}\index{modulo} $n$\fg{} lorsque $x$ et $y$ possÃ¨dent le mÃªme reste dans la division (euclidienne) par $n$ :
 $$x \equiv y [n] \Ssi \exi k \in \Z, x-y=k \cdot n $$
 \end{Def}
 
 
+\begin{Exo}
+ Calculez :
+\begin{enumerate}
+ \item $3*10^9 \mod 97$,
+\item $3^{1024} \mod 1037$.
+\end{enumerate}
+\end{Exo}
+
+%\noindent RÃ©ponses : 5 et 630.
+
+
+
+
 \begin{Th}
-Il s'agit d'une relation d'Ã©quivalence dans $\Z$. 
+La relation de congruence modulo $n$ est une relation d'Ã©quivalence dans $\Z$. 
 \end{Th}
 
 \begin{Proof}
@@ -502,9 +540,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Ã©).
@@ -525,10 +563,11 @@ Si $n = 3$, il y a trois classes distinctes :
 On retrouve ensuite les mÃªmes Ã©lÃ©ments : $\dot 3=\dot 0$, etc... 
 \end{Ex}
 
-
 D'une maniÃ¨re gÃ©nÃ©rale, pour $n$ quelconque, il y a exactement $n$ classes d'Ã©quivalence, notÃ©es de $\dot 0$ Ã  $\dot {(n-1)}$, c'est-Ã -dire, il faut le remarquer, un nombre fini.
 
 
+
+
 \begin{Th}
 L'ensemble-quotient (ensemble des classes d'Ã©quivalence) de la relation de congruence modulo $n$ est un ensemble fini.
 \end{Th}
@@ -543,27 +582,51 @@ Il est notÃ© $\Z/n\Z$.
 \end{Ex}
 
 
+\begin{Def}
+On dit qu'une relation d'Ã©quivalence, notÃ©e  $\equiv$, 
+dÃ©finie dans une structure algÃ©brique $S$, 
+est compatible avec les lois de $S$  
+lorsque les rÃ©sultats des opÃ©rations effectuÃ©es sur des Ã©lÃ©ments Ã©quivalents
+demeurent Ã©quivalents:
+\begin{itemize}
+\item pour l'addition: si $x \equiv x'$ et  $y \equiv y'$, 
+alors on doit avoir $x + y  \equiv x' + y'$;
+\item pour la multiplication $\times$:  si $x \equiv x'$ et  $y \equiv y'$, 
+alors on doit avoir $x \times y  \equiv x' \times y'$.
+\end{itemize}
+\end{Def}
+
+
+
+
+
 \begin{Th}
 La relation de \og congruence modulo $n$\fg{} est compatible avec l'addition et la multiplication des nombres entiers. 
 \end{Th}
 
 
 \begin{Proof}
-En effet, on suppose que :
+En effet, on suppose que:
 \begin{itemize}
-\item $x \equiv x' [n] \Ssi \exi k\in \Z,\ x-x'=k \cdot n$ et que
+\item $x \equiv x' [n] \Ssi \exi k\in \Z,\ x-x'=k \cdot n$;
 \item $y \equiv y' [n] \Ssi \exi l\in \Z, y-y'=l \cdot n$.
-\item Alors, par addition, $(x+y)-(x'+y')=(k+l)\cdot n$; $(k+l)\in\Z$, donc $(x+y)\equiv(x'+y') [n]$ : la congruence modulo $n$ est compatible avec l'addition dans $\Z$.
 \end{itemize}
-En multipliant la premiÃ¨re Ã©galitÃ© par y : $xy-x'y=(ky)\cdot n$ et la seconde par x' : $x'y-x'y'=(x'l)\cdot n$ .
-
-Alors, par addition, $xy-x'y'=(ky+lx')\cdot n$. $(ky+lx')\in\zmat$, donc $x\cdot y\equiv x'\cdot y' [n]$ : la congruence modulo $n$ est aussi compatible avec la multiplication dans $\Z$.
+Alors:
+\begin{itemize}
+\item par addition, $(x+y)-(x'+y')=(k+l)\cdot n$; $(k+l)\in\Z$, donc $(x+y)\equiv(x'+y') [n]$: la congruence modulo $n$ est compatible avec l'addition dans $\Z$
+\item en multipliant l'Ã©galitÃ© $x-x'=k \cdot n$  par $y$, on a 
+  $xy-x'y=(ky)\cdot n$ et l'Ã©galitÃ© 
+  $y-y'=l \cdot n$
+  par $x'$ on a $x'y-x'y'=(x'l)\cdot n$.
+  
+  Par addition, $xy-x'y'=(ky+lx')\cdot n$. $(ky+lx')\in\zmat$, donc $x\cdot y\equiv x'\cdot y' [n]$: la congruence modulo $n$ est aussi compatible avec la multiplication dans $\Z$.
+\end{itemize}
 \end{Proof}
 
 
-\begin{Rem}
-C'est cette propriÃ©tÃ© qui permet de dÃ©finir dans l'ensemble quotient $\Z/n\Z$ des opÃ©rations, dites \emph{induites} par celles qui existent dans $\Z$...
-\end{Rem}
+% \begin{Rem}
+% C'est cette propriÃ©tÃ© qui permet de dÃ©finir dans l'ensemble quotient $\Z/n\Z$ des opÃ©rations, dites \emph{induites} par celles qui existent dans $\Z$...
+% \end{Rem}
 
 
 
@@ -604,14 +667,16 @@ On aperÃ§oit la prÃ©sence de \og diviseurs de zÃ©ro\fg{} ($\dot 2 \times \dot 2=
 
 
 \begin{Exo}
- Calculez :
+RÃ©solvez modulo 18 les Ã©quations suivantes :
+
 \begin{enumerate}
- \item $3*10^9 mod 97$,
-\item $3^{1024} mod 1037$.
+ \item $2x+17 = 15$,
+\item $3x+4 = 12$,
+\item $5x+13 = 16$.
 \end{enumerate}
 \end{Exo}
 
-\noindent RÃ©ponses : 5 et 630.
+%\noindent RÃ©ponses : \{8,17\}, \{ \} et \{15\}.
 
 
 \begin{Exo}[SystÃ¨mes de congruences]
@@ -626,7 +691,7 @@ Un tel systÃ¨me peut ne pas avoir de solution
 Une condition suffisante d'existence de
 solutions est que $p$ et $q$ soient premiers entre eux.
 
-C'est le cas que nous traiterons ici; dans ce cas, il existe deux entiers $u$ et $v$ tels que $pu+qv=1$ (thÃ©orÃ¨me de Bezout).
+C'est le cas que nous traiterons ici; dans ce cas, il existe deux entiers $u$ et $v$ tels que $pu+qv=1$ (thÃ©orÃ¨me de BÃ©zout).
 
 Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution du systÃ¨me (pourquoi??); les autres sont de la forme $x + kpq$, oÃ¹ $k$ est un entier quelconque.
 \begin{enumerate}
@@ -634,8 +699,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. 
 
@@ -648,49 +713,37 @@ Quel est le plus petit nombre de piÃ¨ces d'or qu'il espÃ¨re lorsqu'il dÃ©cide d'
 \end{Exo}
 
 
-\begin{Exo}
-RÃ©solvez modulo 18 les Ã©quations suivantes :
-
-\begin{enumerate}
- \item $2x+17 = 15$,
-\item $3x+4 = 12$,
-\item $5x+13 = 16$.
-\end{enumerate}
-\end{Exo}
-
-\noindent RÃ©ponses : \{8,17\}, \{ \} et \{15\}.
 
 
 \begin{Exo}
  Si $m$ est un entier naturel plus grand que 2, quel est l'inverse de $m-1$ modulo $m$ ?
 \end{Exo}
 
-\noindent RÃ©ponse : $m-1$.
+%\noindent RÃ©ponse : $m-1$.
 
 
 \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$.
-
 VÃ©rifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de base 2.
 \end{Exo}
 
 
-\subsection{Division \og entiÃ¨re\fg{} informatique et division euclidienne}
+\section{ArithmÃ©tique en informatique}
 
 
-La plupart des langages de programmation utilisÃ©s en informatique disposent d'un type de donnÃ©es pour reprÃ©senter ce que les informaticiens appellent les entiers signÃ©s (les entiers relatifs) et possÃ¨dent des opÃ©rateurs pour effectuer les calculs classiques sur ces nombres.\\
+La plupart des langages de programmation utilisÃ©s en informatique disposent d'un type de donnÃ©es pour reprÃ©senter ce que les informaticiens appellent les entiers signÃ©s (les entiers relatifs) et possÃ¨dent des opÃ©rateurs pour effectuer les calculs classiques sur ces nombres.
 
+\subsection{Division entiÃ¨re}
 
-En C ou java, par exemple, le symbole $/$ reprÃ©sente le quotient dans la \og division entiÃ¨re\fg{} et le symbole $\%$ reprÃ©sente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entiÃ¨re\fg{} ).\\
+En C ou java, par exemple, le symbole $/$ reprÃ©sente le quotient dans la \og division entiÃ¨re\fg{} et le symbole $\%$ reprÃ©sente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entiÃ¨re\fg{} ).
 
 
-Pour des raisons pratiques de rÃ©alisation des micro-circuits des processeurs qui rÃ©alisent ces opÃ©rations, la \og division entiÃ¨re\fg{} ne donne pas exactement le mÃªme rÃ©sultat que la division euclidienne.\\
+Pour des raisons pratiques de rÃ©alisation des micro-circuits des processeurs qui rÃ©alisent ces opÃ©rations, la \og division entiÃ¨re\fg{} ne donne pas exactement le mÃªme rÃ©sultat que la division euclidienne.
 
 
 
 ConsidÃ©rons par exemple les 4 cas possibles de division euclidienne de $a$ par $b$ lorsque $|a|=29$ et $|b|=7$ (en n'oubliant pas que le reste d'une division euclidienne ne peut Ãªtre que positif)
 
-\bigskip
 
 \begin{center}
 \begin{tabular}{|c|c|c|c|c|c|c|}
@@ -703,39 +756,37 @@ $-29$ &$-7$ & $-29=5\times (-7)+6$ & $5$ & $6$ & $4$ & $-1$ \\ \hline
 \end{tabular}
 \end{center}
 
-\bigskip
 
-Autrement dit, mathÃ©matiquement, le quotient est positif lorsque les deux nombres ont le mÃªme signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas Ãªtre le quotient des valeurs absolues.\\
+
+Autrement dit, mathÃ©matiquement, le quotient est positif lorsque les deux nombres ont le mÃªme signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas Ãªtre le quotient des valeurs absolues.
 
 
-Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le mÃªme signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.\\
+Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le mÃªme signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.
 
 
 Dans les applications de calcul arithmÃ©tique, par exemple un calcul de PGCD, ce n'est pas gÃªnant parce que les restes \og informatiques\fg{} sont congrus aux restes mathÃ©matiques modulo la valeur absolue du
-diviseur, et qu'il ne s'agit alors que du choix d'un reprÃ©sentant de la classe concernÃ©e (addition et multiplication Ã©tant compatibles avec la congruence modulo $n$).\\
+diviseur, et qu'il ne s'agit alors que du choix d'un reprÃ©sentant de la classe concernÃ©e (addition et multiplication Ã©tant compatibles avec la congruence modulo $n$).
 
 Mais il faut quand mÃªme savoir que l'on peut obtenir un \og reste\fg{} nÃ©gatif et prendre ses dispositions le cas Ã©chÃ©ant...
 
 
-\subsection{ArithmÃ©tique modulo $2^n$ dans les ordinateurs}
+\subsection{ArithmÃ©tique modulo $2^n$}
 
-\subsubsection{PrÃ©sentation gÃ©nÃ©rale}
+ 
 
-Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, oÃ¹ $n$ est le nombre de bits utilisÃ©s dans la reprÃ©sentation de ces nombres.\\
+Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, oÃ¹ $n$ est le nombre de bits utilisÃ©s dans la reprÃ©sentation de ces nombres.
 
 
-Dans la plupart des microprocesseurs, les entiers sont reprÃ©sentÃ©s sur 32 bits, les calculs se font donc dans $\Z/2^{32}\Z$ (et qu'ils le soient sur 64 bits ne change rien au problÃ¨me).\\
+Dans la plupart des microprocesseurs, les entiers sont reprÃ©sentÃ©s sur 64 bits, les calculs se font donc dans $\Z/2^{64}\Z$.
 
 
 Disposer d'entiers signÃ©s ou d'entiers non signÃ©s est uniquement une question de choix du reprÃ©sentant dans les classes d'Ã©quivalence, mais
-la reprÃ©sentation physique est la mÃªme.\\
+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.\\
+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
@@ -757,7 +808,7 @@ code binaire & & a.s. & a.n.s. \\ \hline
 \end{tabular}\end{center}\vskip 10pt
 
 
-Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., reprÃ©sentÃ© les entiers dans l'ordre croissant de 0000 (-8) Ã  1111 (7)?\\
+Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., reprÃ©sentÃ© les entiers dans l'ordre croissant de 0000 (-8) Ã  1111 (7)?
 
 \begin{itemize}
  \item Tout simplement pour des raisons d'efficacitÃ© : 0 doit toujours Ãªtre reprÃ©sentÃ© par le code \og nul\fg{} 0000.
@@ -766,27 +817,23 @@ Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., reprÃ©sentÃ© les entiers dan
 
 \bigskip
 
-Ces principes ont ainsi conduit Ã  placer les codes interprÃ©tÃ©s comme entiers nÃ©gatifs aprÃ¨s ceux qui reprÃ©sentent les entiers positifs.\\
+Ces principes ont ainsi conduit Ã  placer les codes interprÃ©tÃ©s comme entiers nÃ©gatifs aprÃ¨s ceux qui reprÃ©sentent les entiers positifs.
 
 
 Par ailleurs, on s'aperÃ§oit que, de cette maniÃ¨re, les codes des entiers
 nÃ©gatifs commencent tous par 1.
 On parle improprement de \og bit de signe\fg{}\index{bit de signe}: s'il s'agissait d'un vÃ©ritable bit de signe, le code 1001 devrait Ãªtre celui de -1, or c'est celui de -7.
-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 n'en reste pas moins que tous les entiers nÃ©gatifs commencent par 1).
 
 
-Mais il y a quand mÃªme deux instructions assembleur distinctes pour la comparaison signÃ©e et pour la comparaison non signÃ©e.
+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.
 
 
 
-\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 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.
+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}
 
@@ -883,7 +930,7 @@ OpÃ©ration binaire & Entiers non signÃ©s & Entiers signÃ©s \\
 
 
 
-\subsection{ThÃ©orÃ¨me de BÃ©zout}
+\section{ThÃ©orÃ¨me de BÃ©zout}
 
 
 On considÃ¨re deux nombres entiers strictement positifs $a$ et $b$.
@@ -929,18 +976,18 @@ Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors
 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.
+\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Ã©}
 
-\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$.\\
 
+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}$).\\
+
+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...
@@ -952,14 +999,14 @@ En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on dÃ©finit une famille finie
 
 \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$.\\
+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$.\\
+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$.\\
+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.}
+\subsection{L'algorithme.}
 \index{algorithme!d'Euclide!gÃ©nÃ©ralisÃ©}
 Ceci donne l'idÃ©e de construire deux familles par les relations :
 \begin{itemize}
@@ -967,7 +1014,7 @@ Ceci donne l'idÃ©e de construire deux familles par les relations :
 \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$.\\
+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
@@ -982,7 +1029,7 @@ v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$.
 \end{Pre}
 
 
-\subsubsection{Exemple.}
+\subsection{Exemple.}
 
 Illustrons la mise en \oe{}uvre de cet algorithme...
 
@@ -1001,7 +1048,7 @@ On a bien $3 \times 23-4 \times 17=1$.\psaut
 \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)$.\\
+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$. 
@@ -1011,9 +1058,26 @@ et oÃ¹ $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un coupl
 Exprimer $pgcd(1330,602)$ comme combinaison Ã  coefficients entiers des nombres 1330 et 602.
 \end{Exo}
 
-\noindent RÃ©ponse $14 = 1330*(-19)+602*42$.
 
 
+\begin{Theo}[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{Theo}
+
+
+\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}
 
-\gsaut
 \centerline{\x{Fin du Chapitre}}
\ No newline at end of file
