modif algo euclide

[cours-maths-dis.git] / arithmetique / entiersNaturels.tex

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index babbac9cbef7b1a89d0923845808f2b4b3fdb90f..dfe64394c45879ae5d962cfec675496611f603d4 100755 (executable)
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -1,139 +1,45 @@
+\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 \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:

 \begin{enumerate}
 \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}
 \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}
 \end{enumerate}

-
-\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}
+Ceci se déduit du fait que $\N$ est un ensemble complètement ordonné. 

 
 
 
 

-\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$) ?
 \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}
 
 
 \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}
-\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}
 
 
 \begin{Exo}


@@ -145,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 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{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.


@@ -153,21 +59,18 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \end{Exo}
 
 \begin{Exo}
 \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}
 
 
 \end{Exo}
 
 

-\paragraph{Autres exercices sur la récurrence}
-
-

 \begin{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}
 \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$$
 $$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}
 
 
 \end{Exo}
 
 


@@ -176,51 +79,31 @@ Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divi
 \end{Exo}
 
 
 \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]
 
 \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$.
+On écrit aussi $p \mid n$ pour $p$ divise $n$.

 \end{Def}
 
 \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}
 
 \begin{Exo}
  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.
 \end{Def}
 
 
 
 \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.
 \end{Def}
 
 

-\begin{Ex}
+\begin{Exo}

 Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
 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.
 
 \begin{Th}
 Il existe une infinité de nombres premiers.


@@ -233,12 +116,12 @@ 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$.
 
 
 \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}
 
 
 \end{Def}
 
 


@@ -256,8 +139,46 @@ 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 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. 
+
+
+
+\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.
+
+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{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}
+
+
+
+

 \begin{Exo}[Nombres de Fermat]
 \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.
 
 \begin{enumerate}
 \item Montrer que, pour que $2^n+1$ soit premier, il faut que $n$ soit une puissance de 2.
 


@@ -272,81 +193,149 @@ On appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
 \end{Exo}
 
 
 \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}\index{algorithme!d'Euclide}

 
 

-Cette relation est une relation d'ordre partiel : il existe des paires d'entiers non comparables par cette relation.
+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{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...
+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{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{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.

 
 

-Le PPCM, lui, vaut $a\ou b=ab/(a\et b)$. 
-\end{Proof}

 
 

+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'$. 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$ on a $a\et b= b\et 0$ qui est égal à $b$.
+
+\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 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}
+
+
+\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$.
-\end{Ex}

 
 \begin{Exo}
 
 \begin{Exo}

- Calculez $ppcm(102,138)$.
+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{Exo}
 
 \end{Exo}
 

-\noindent Réponse : 2346.
+% \begin{Exo}
+% Comme $48=2^43$ et que $56=2^37$, on voit aisément que $48\et 56=2^3$.
+% \end{Exo}

 
 

-\begin{Th}
-$\Net$ est un treillis pour la divisibilité. 
+% \begin{Exo}
+%  Calculez $102 \ou 138$.
+% \end{Exo}

 
 

-On peut de plus montrer que :
+% \noindent Réponse : 2346.

 
 

-\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{Th}
+% $\Net$ est un treillis pour la divisibilité. 

 
 

+% 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}

 
 

-\noindent Réponse : En se plongeant dans le calcul modulo $b$, on a : ad = 0.
+% \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.

 
 

-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$.

 
 
 
 
 
 

-\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.\\
 
 
 L'ensemble habituellement noté $\Z$ des entiers relatifs est obtenu à partir de $\N$ par le procédé de symétrisation pour l'addition.\\
 


@@ -383,13 +372,13 @@ Enfin, lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un
 \end{Def}
 
 
 \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$). 
 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 )$. 
 0 est divisible par tout nombre entier non nul $(0 = 0 \times b + 0 )$. 

-\end{Ex}
+\end{Exo}

 
 
 \begin{Exo}
 
 
 \begin{Exo}


@@ -541,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$.
 
 
 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\}$, 
 Si $n = 3$, il y a trois classes distinctes :
 \begin{itemize}
  \item $\dot 0=\{\ldots,-6,-3,0,3,6,9,\ldots\}$, 


@@ -550,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{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.
 
 
 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.


@@ -565,9 +554,9 @@ Il est noté $\Z/n\Z$.
 \end{Notation}
 
 
 \end{Notation}
 
 

-\begin{Ex}
+\begin{Exo}

  $\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.
  $\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.

-\end{Ex}
+\end{Exo}

 
 
 \begin{Th}
 
 
 \begin{Th}


@@ -602,7 +591,7 @@ Par définition, on pose $\dot x + \dot y = \dot {(x+y)}$ et $\dot x \cdot
 \end{Def}
 
 
 \end{Def}
 
 

-\begin{Ex}
+\begin{Exo}

 C'est ainsi qu'on obtient les tables d'opérations suivantes dans $\Z/4\Z$ :\\
 
 
 C'est ainsi qu'on obtient les tables d'opérations suivantes dans $\Z/4\Z$ :\\
 
 


@@ -622,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
 \dot 3 & \dot 0 & \dot 3 & \dot 2 & \dot 1 \\ \hline \end{array}$ 
 \end{center}
 \vskip 10pt

-\end{Ex}
+\end{Exo}

 
 
 \begin{Rem}
 
 
 \begin{Rem}


@@ -815,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).
 
 
 \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 :
 
 
 Premiers résultats, corrects :
 


@@ -828,10 +817,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 1011 & 11 & (-5) \\
 \end{tabular}
  \end{center}
 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}
  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}


@@ -842,10 +831,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 1010 & 10 & (-6) \\
 \end{tabular}
 \end{center}
 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}
 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}


@@ -857,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{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}
 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}


@@ -873,10 +862,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 \underline{$\times$ 2} \\ 1010 & 10 & (-6) \\
 \end{tabular}
  \end{center}
 \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}
 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}


@@ -887,12 +876,12 @@ Opération binaire & Entiers non signés & Entiers signés \\
 (1)1110 & 14 & (-2) \\
 \end{tabular} 
  \end{center}
 (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}
 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}


@@ -903,94 +892,10 @@ Opération binaire & Entiers non signés & Entiers signés \\
 (-2)} \\ (1011)0110 & 6 & 6 \\
 \end{tabular} 
 \end{center}
 (-2)} \\ (1011)0110 & 6 & 6 \\
 \end{tabular} 
 \end{center}

-\end{Ex}
-
-
-
-
-\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
+\end{Exo}

 
 

-\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 ) ;}
-}\}}

 
 
 
 
 
 


@@ -1097,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...
 
 
 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$ \\
 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$ \\


@@ -1107,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 
 (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.
 
 \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.