From 1284ef2ac6e46e2f78902a137ba13570a9272ac9 Mon Sep 17 00:00:00 2001
From: couchot <couchot@couchot-Latitude-E6320.(none)>
Date: Mon, 4 Mar 2013 16:40:44 +0100
Subject: [PATCH] modif algo euclide

---
 arithmetique/entiersNaturels.tex | 184 +++++++++++++++----------------
 1 file changed, 92 insertions(+), 92 deletions(-)

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index 1fc13ca..dfe6439 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:
@@ -15,7 +15,7 @@ l'entier $n \ge n_0$. Une variante consiste à remplacer l'étape~\ref{itm:2} pa
 \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é. 
+Ceci se déduit du fait que $\N$ est un ensemble complètement ordonné. 
 
 
 \begin{Exo}
@@ -27,19 +27,19 @@ Ceci se déduit du fait que $\Nat$ est un ensemble complètement ordonné.
 \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,7 +51,7 @@ 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.
@@ -59,18 +59,18 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \end{Exo}
 
 \begin{Exo}
-Poursuivre le raisonnement pour $S_3(n)$. Cette méthode permet-elle de calculer $S_k(n), \forall k,n$ ?
+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 $n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
 \end{Exo}
 
 \begin{Exo}
-Soit $(u_n)_{n \in \N}$ une suite réelle telle que $\forall n \in \N$,
+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 $\forall n \in \N, u_n = \alpha 3^n + \beta 2^n$.
+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}
 
 
@@ -87,9 +87,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,9 +101,9 @@ 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.
@@ -121,7 +121,7 @@ Il existe une infinité de nombres 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$.
 
-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}
 
 
@@ -143,32 +143,34 @@ 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.
+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  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. 
 
-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.
+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.
+
+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,7 +178,7 @@ 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 $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.
 
@@ -192,48 +194,46 @@ On appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
 
 
 
-\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 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$, 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 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}
 
 
@@ -277,7 +277,7 @@ else
 }\}}
 
 
-\begin{Ex}
+\begin{Exo}
 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$.
@@ -294,11 +294,11 @@ $b=p^n-1$.
 \item Déterminer tous les couples d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
 \end{enumerate}
 \end{enumerate}
-\end{Ex}
+\end{Exo}
 
-% \begin{Ex}
+% \begin{Exo}
 % Comme $48=2^43$ et que $56=2^37$, on voit aisément que $48\et 56=2^3$.
-% \end{Ex}
+% \end{Exo}
 
 % \begin{Exo}
 %  Calculez $102 \ou 138$.
@@ -335,7 +335,7 @@ $b=p^n-1$.
 
 
 
-\subsection{Entiers relatifs}
+\section{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.\\
 
@@ -372,13 +372,13 @@ Enfin, lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un
 \end{Def}
 
 
-\begin{Ex}
+\begin{Exo}
 Tout nombre non nul est au moins divisible par 1 et par lui-même ($a=a\times 1+0$). 
-\end{Ex}
+\end{Exo}
 
-\begin{Ex}
+\begin{Exo}
 0 est divisible par tout nombre entier non nul $(0 = 0 \times b + 0 )$. 
-\end{Ex}
+\end{Exo}
 
 
 \begin{Exo}
@@ -530,7 +530,7 @@ $(k+l)\in\Z$, donc $x \equiv z [n]$ (transitivité).
 
 La classe d'équivalence d'un entier donné comprend donc cet entier et tous ceux qui ont le même reste que lui dans la division euclidienne par $n$.
 
-\begin{Ex}
+\begin{Exo}
 Si $n = 3$, il y a trois classes distinctes :
 \begin{itemize}
  \item $\dot 0=\{\ldots,-6,-3,0,3,6,9,\ldots\}$, 
@@ -539,7 +539,7 @@ Si $n = 3$, il y a trois classes distinctes :
 \end{itemize}
 
 On retrouve ensuite les mêmes éléments : $\dot 3=\dot 0$, etc... 
-\end{Ex}
+\end{Exo}
 
 
 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.
@@ -554,9 +554,9 @@ Il est noté $\Z/n\Z$.
 \end{Notation}
 
 
-\begin{Ex}
+\begin{Exo}
  $\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.
-\end{Ex}
+\end{Exo}
 
 
 \begin{Th}
@@ -591,7 +591,7 @@ Par définition, on pose $\dot x + \dot y = \dot {(x+y)}$ et $\dot x \cdot
 \end{Def}
 
 
-\begin{Ex}
+\begin{Exo}
 C'est ainsi qu'on obtient les tables d'opérations suivantes dans $\Z/4\Z$ :\\
 
 
@@ -611,7 +611,7 @@ $\begin{array}{|c|c|c|c|c|}\hline
 \dot 3 & \dot 0 & \dot 3 & \dot 2 & \dot 1 \\ \hline \end{array}$ 
 \end{center}
 \vskip 10pt
-\end{Ex}
+\end{Exo}
 
 
 \begin{Rem}
@@ -804,7 +804,7 @@ Pour l'addition et la soustraction, les opérations et les tests de validité de
 
 \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).
 
-\begin{Ex}
+\begin{Exo}
 
 Premiers résultats, corrects :
 
@@ -817,10 +817,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 1011 & 11 & (-5) \\
 \end{tabular}
  \end{center}
-\end{Ex}
+\end{Exo}
 
 
-\begin{Ex}
+\begin{Exo}
  Un résultat correct en arithmétique non \break signée, et négatif en arithmétique signée, mais correct modulo 16 (-6 et 10 sont dans la même classe, mais cette classe  est représentée par 10 en a.n.s. et par -6 en a.s.) :
 \begin{center}
 \begin{tabular}{r | r | r}
@@ -831,10 +831,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 1010 & 10 & (-6) \\
 \end{tabular}
 \end{center}
-\end{Ex}
+\end{Exo}
 
 
-\begin{Ex}
+\begin{Exo}
 Un dépassement de capacité dans les deux cas, mais  le résultat est correct modulo 16 : les classes de 21, de -11 et de 5 sont les mêmes :
  \begin{center}
 \begin{tabular}{r | r | r}
@@ -846,12 +846,12 @@ Opération binaire & Entiers non signés & Entiers signés \\
 \end{tabular}
  \end{center}
 Le résultat (correct modulo 16) est disponible dans tous les cas, les \og dépassement de capacité\fg{} et \og résultat négatif\fg{} sont signalés par le positionnement d'un bit dans un registre spécial.
-\end{Ex}
+\end{Exo}
 
 
 
 
-\begin{Ex}
+\begin{Exo}
 Un résultat correct en a.n.s., résultat négatif en a.s., mais correct modulo 16 :
  \begin{center}
 \begin{tabular}{r | r | r}
@@ -862,10 +862,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 \underline{$\times$ 2} \\ 1010 & 10 & (-6) \\
 \end{tabular}
  \end{center}
-\end{Ex}
+\end{Exo}
 
 
-\begin{Ex}
+\begin{Exo}
 Dépassement de capacité dans les deux cas, résultat négatif en a.s., mais résultat correct modulo 16, compte tenu du choix des représentants dans les deux arithmétiques:
  \begin{center}
 \begin{tabular}{r | r | r}
@@ -876,12 +876,12 @@ Opération binaire & Entiers non signés & Entiers signés \\
 (1)1110 & 14 & (-2) \\
 \end{tabular} 
  \end{center}
-\end{Ex}
+\end{Exo}
 
 
 
 
-\begin{Ex}
+\begin{Exo}
 Dépassement de capacité dans les deux cas,  résultat correct en a.s., correct modulo 16 en a.n.s.
  \begin{center}
 \begin{tabular}{r | r | r}
@@ -892,7 +892,7 @@ Opération binaire & Entiers non signés & Entiers signés \\
 (-2)} \\ (1011)0110 & 6 & 6 \\
 \end{tabular} 
 \end{center}
-\end{Ex}
+\end{Exo}
 
 
 
@@ -1002,7 +1002,7 @@ v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$.
 
 Illustrons la mise en \oe{}uvre de cet algorithme...
 
-\begin{Ex}
+\begin{Exo}
 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$ \\
@@ -1012,7 +1012,7 @@ Soit à obtenir un couple de Bézout pour (23,17) :\vskip 10pt
 (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}
+\end{Exo}
 
 \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.
-- 
2.39.5