+\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}
-\item Il existe une injection de $\N$ dans $\N$.
-
-Cette injection, appelée \emph{fonction de succession}\index{fonction!de succession}, sera notée $s$ dans la suite.
-
-L'image d'un entier $n$ par la fonction de succession $s$, soit $s(n)$, est appelée \emph{successeur} \index{successeur} de $n$.\\
-
-\item Il existe un élément de $\N$ qui n'est le successeur d'aucun élément de $\N$.
-
-Cet élément est appelé \og \emph{zéro}\fg{}\index{zéro} et noté 0 dans la suite.
-
-\item Le \og \emph{Principe de récurrence} \fg{} \index{principe de récurrence} \index{récurrence} est satisfait :
-
-Soit $M$ la partie de $\N$ constituée par les entiers qui possèdent une certaine propriété $p$. On note \og $p(n)$\fg{} le fait que l'entier $n$ possède la propriété $p$.
-
-\begin{Th}[Principe de récurrence]
-Il s'énonce ainsi : \og Si $M$ contient 0 et le successeur de chacun de ses éléments, alors $M=\N$.\fg{}
-\end{Th}
-
-
-Sous forme formalisée...
-
-Soit $M=\{n\in\N \mid p(n)\}$; si $0\in M$ et si $[n \in M \Imp s(n) \in M]$, alors $M=\N$.
-\end{enumerate}
-\end{Def}
-
-
-
-\begin{Rem}
- $M=\N$ signifie évidemment que la propriété est
-possédée par tous les entiers naturels. C'est, en général, la conclusion attendue d'un \og raisonnement par récurrence\fg{}
-\end{Rem}
-
-
-\subsubsection{Sur la récurrence}
-
-Il existe une version \og affaiblie\fg{} du principe de récurrence : la récurrence restreinte, qui permet de s'assurer qu'une propriété est vraie à partir d'un certain rang...
-
-
-\begin{Th}[Récurrence restreinte]
-\index{récurrence!restreinte}
-Soit $M=\{n\in\N \mid p(n)\}$.
-
-Si $p\in M$ et si, $[n \in M \Imp s(n) \in M]$, alors $M$ est de la forme $\{p,p+1,p+2,\ldots\}$.
-\end{Th}
-
-
-Il existe encore une version \og renforcée\fg{} : la récurrence généralisée, qui permet de \og supposer la
-propriété vraie jusqu'à l'ordre $n$\fg{}...
-
-
-\begin{Th}[Récurrence généralisée]
-\index{récurrence!généralisée}
- Soit $M=\{n\in\N \mid p(n)\}$.
-
-Si, $\qqs p \in M$, $\{0,1,2,\ldots,p\} \sse M$ et si $s(p)\in M$, alors $M=\N$.
-\end{Th}
-
-\begin{Proof}
- Elle se démontre à partir de la récurrence \og normale\fg{}.
-\end{Proof}
-
-
-\begin{Rem}
-La récurrence généralisée permet d'éviter un double raisonnement par récurrence.
-\end{Rem}
-
-\bigskip
-
-\noindent Manière correcte de rédiger un raisonnement par récurrence :
-
+\item on vérifie que $P(n_0)$ est vraie;
+\item\label{itm:2} on suppose que $P(n)$ est vraie pour un certain entier $n \ge n_0$,
+ c'est l'hypothèse de récurrence, et on démontre que $P(n+1)$ est vraie.
+\end{enumerate}
+Le \emph{principe de récurrence} dit alors que $P(n)$ est vraie quel que soit
+l'entier $n \ge n_0$. Une variante consiste à remplacer l'étape~\ref{itm:2} par
\begin{enumerate}
- \item Soit $M$ l'ensemble des entiers naturels qui vérifient ... (mettre ici l'énoncé de la propriété que l'on cherche à démontrer)
-
-\item Initialisation de la récurrence : vérifier que 0 est élément de $M$ (\og la propriété est vraie pour $n=0$\fg{})
-
-\item Caractère héréditaire de la propriété : soit $n$ un élément de $M$ (cela a un sens, puisque l'on sait maintenant que $M$ n'est pas vide : il contient au moins 0), vérifions que $s(n)$ est encore élément de $M$ (\og la propriété est vraie pour $n+1$\fg{})
+\item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre
+$n_0$ et $n$, et on démontre que $P(n+1)$ est vraie.
\end{enumerate}
-
-\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$) ?
-\item Démontrer que l'on a effectivement l'égalité
+\item Démontrer par récurrence que l'on a effectivement l'égalité
\end{enumerate}
\end{Exo}
-\paragraph{Somme d'entiers élevés à une puissance donnée}
-
-On montre, dans ce qui suit, une application de la technique de récurrence, pour calculer $S_k(n) = 1^k+2^k+...+n^k, \forall k,n \in \N$ (d'autres techniques, plus efficaces, existent).
-
-\begin{Exo}
-On souhaite calculer $S_1(n) = 1+2+...+n$.
-\begin{enumerate}
-\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}
\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{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}
-\paragraph{Autres exercices sur la récurrence}
-
-
\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}
\end{Exo}
-\subsection{Opérations et relation d'ordre dans $\N$}
-On suppose ici connues les opérations et la relation d'ordre classiques qui existent dans $\N$ : addition, multiplication, relation d'inégalité au sens large.
-
-Ces éléments peuvent être définis rigoureusement, et toutes les propriétés démontrées par récurrence.
-
-\begin{Ex}
-Par exemple, on peut définir la relation $p\leqslant n$ par $\exi q\in\N,\ n=p+q$.
-\end{Ex}
-
-\begin{Th}
-Les opérations précédentes ont pour propriétés :
-\begin{itemize}
-\item l'addition est commutative, associative, il existe un élément neutre (0),
-\item la multiplication est commutative, associative et admet aussi un élément neutre (1),
-\item la multiplication est distributive sur l'addition,
-\item les entiers sont totalement ordonnés par l'inégalité, et cette relation d'ordre est compatible avec l'addition et avec la multiplication.
-\end{itemize}
-\end{Th}
-
-
-\subsection{Nombres premiers}
-
-\subsubsection{Définitions}
+\section{Nombres premiers}
\begin{Def}[Multiple, diviseur]
-Si un entier $n$ peut s'écrire sous la forme $n=pq$, où $p$ et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple} de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
+Si un entier $n$ peut s'écrire sous la forme $n=pq$, où $p$
+et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple}
+de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
+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}
-\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{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.
-\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$.
-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}
+
+\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]
-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.
\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}
- 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}
-\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.\\
\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}
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\}$,
\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.
\end{Notation}
-\begin{Ex}
+\begin{Exo}
$\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.
-\end{Ex}
+\end{Exo}
\begin{Th}
\end{Def}
-\begin{Ex}
+\begin{Exo}
C'est ainsi qu'on obtient les tables d'opérations suivantes dans $\Z/4\Z$ :\\
\dot 3 & \dot 0 & \dot 3 & \dot 2 & \dot 1 \\ \hline \end{array}$
\end{center}
\vskip 10pt
-\end{Ex}
+\end{Exo}
\begin{Rem}
\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 :
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}
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}
\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}
\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}
(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}
(-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 ) ;}
-}\}}
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$ \\
(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.
