+\section{Principe de récurrence }
-
-
-\section{Nombres entiers naturels ($\N$)}
-
-\subsection{Définition de $\N$}
-
-\subsubsection{Définition}
-
-\begin{Def}[Ensemble des entiers naturels]
-On appelle \emph{ensemble des nombres entiers naturels}\index{entiers naturels} $\N$ tout ensemble possédant les propriétés suivantes
+Pour démontrer par \emp{récurrence}
+\index{récurrence!restreinte}
+qu'une propriété $P(n)$ est vraie quel que soit l'entier $n \ge n_0$,
+on procède en deux étapes:
\begin{enumerate}
-\item Il existe une injection de $\N$ dans $\N$.
-
-Cette injection, appelée \emph{fonction de succession}\index{fonction!de succession}, sera notée $s$ dans la suite.
-
-L'image d'un entier $n$ par la fonction de succession $s$, soit $s(n)$, est appelée \emph{successeur} \index{successeur} de $n$.\\
-
-\item Il existe un élément de $\N$ qui n'est le successeur d'aucun élément de $\N$.
-
-Cet élément est appelé \og \emph{zéro}\fg{}\index{zéro} et noté 0 dans la suite.
-
-\item Le \og \emph{Principe de récurrence} \fg{} \index{principe de récurrence} \index{récurrence} est satisfait :
-
-Soit $M$ la partie de $\N$ constituée par les entiers qui possèdent une certaine propriété $p$. On note \og $p(n)$\fg{} le fait que l'entier $n$ possède la propriété $p$.
-
-\begin{Th}[Principe de récurrence]
-Il s'énonce ainsi : \og Si $M$ contient 0 et le successeur de chacun de ses éléments, alors $M=\N$.\fg{}
-\end{Th}
-
-
-Sous forme formalisée...
-
-Soit $M=\{n\in\N \mid p(n)\}$; si $0\in M$ et si $[n \in M \Imp s(n) \in M]$, alors $M=\N$.
-\end{enumerate}
-\end{Def}
-
-
-
-\begin{Rem}
- $M=\N$ signifie évidemment que la propriété est
-possédée par tous les entiers naturels. C'est, en général, la conclusion attendue d'un \og raisonnement par récurrence\fg{}
-\end{Rem}
-
-
-\subsubsection{Sur la récurrence}
-
-Il existe une version \og affaiblie\fg{} du principe de récurrence : la récurrence restreinte, qui permet de s'assurer qu'une propriété est vraie à partir d'un certain rang...
-
-
-\begin{Th}[Récurrence restreinte]
-\index{récurrence!restreinte}
-Soit $M=\{n\in\N \mid p(n)\}$.
-
-Si $p\in M$ et si, $[n \in M \Imp s(n) \in M]$, alors $M$ est de la forme $\{p,p+1,p+2,\ldots\}$.
-\end{Th}
-
-
-Il existe encore une version \og renforcée\fg{} : la récurrence généralisée, qui permet de \og supposer la
-propriété vraie jusqu'à l'ordre $n$\fg{}...
-
-
-\begin{Th}[Récurrence généralisée]
-\index{récurrence!généralisée}
- Soit $M=\{n\in\N \mid p(n)\}$.
-
-Si, $\qqs p \in M$, $\{0,1,2,\ldots,p\} \sse M$ et si $s(p)\in M$, alors $M=\N$.
-\end{Th}
-
-\begin{Proof}
- Elle se démontre à partir de la récurrence \og normale\fg{}.
-\end{Proof}
-
-
-\begin{Rem}
-La récurrence généralisée permet d'éviter un double raisonnement par récurrence.
-\end{Rem}
-
-\bigskip
-
-\noindent Manière correcte de rédiger un raisonnement par récurrence :
-
+\item on vérifie que $P(n_0)$ est vraie;
+\item\label{itm:2} on suppose que $P(n)$ est vraie pour un certain entier $n \ge n_0$,
+ c'est l'hypothèse de récurrence, et on démontre que $P(n+1)$ est vraie.
+\end{enumerate}
+Le \emph{principe de récurrence} dit alors que $P(n)$ est vraie quel que soit
+l'entier $n \ge n_0$. Une variante consiste à remplacer l'étape~\ref{itm:2} par
\begin{enumerate}
- \item Soit $M$ l'ensemble des entiers naturels qui vérifient ... (mettre ici l'énoncé de la propriété que l'on cherche à démontrer)
-
-\item Initialisation de la récurrence : vérifier que 0 est élément de $M$ (\og la propriété est vraie pour $n=0$\fg{})
-
-\item Caractère héréditaire de la propriété : soit $n$ un élément de $M$ (cela a un sens, puisque l'on sait maintenant que $M$ n'est pas vide : il contient au moins 0), vérifions que $s(n)$ est encore élément de $M$ (\og la propriété est vraie pour $n+1$\fg{})
+\item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre
+$n_0$ et $n$, et on démontre que $P(n+1)$ est vraie.
\end{enumerate}
-
-\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 $\Nat$ 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}
\end{Exo}
-\paragraph{Autres exercices sur la récurrence}
-
-
\begin{Exo}
Montrer que $\forall n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
\end{Exo}
\end{Exo}
-\subsection{Opérations et relation d'ordre dans $\N$}
-On suppose ici connues les opérations et la relation d'ordre classiques qui existent dans $\N$ : addition, multiplication, relation d'inégalité au sens large.
-
-Ces éléments peuvent être définis rigoureusement, et toutes les propriétés démontrées par récurrence.
-
-\begin{Ex}
-Par exemple, on peut définir la relation $p\leqslant n$ par $\exi q\in\N,\ n=p+q$.
-\end{Ex}
-
-\begin{Th}
-Les opérations précédentes ont pour propriétés :
-\begin{itemize}
-\item l'addition est commutative, associative, il existe un élément neutre (0),
-\item la multiplication est commutative, associative et admet aussi un élément neutre (1),
-\item la multiplication est distributive sur l'addition,
-\item les entiers sont totalement ordonnés par l'inégalité, et cette relation d'ordre est compatible avec l'addition et avec la multiplication.
-\end{itemize}
-\end{Th}
-
-
-\subsection{Nombres premiers}
-
-\subsubsection{Définitions}
+\section{Nombres premiers}
\begin{Def}[Multiple, diviseur]
-Si un entier $n$ peut s'écrire sous la forme $n=pq$, où $p$ et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple} de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
+Si un entier $n$ peut s'écrire sous la forme $n=pq$, où $p$
+et $q$ sont des entiers, on dit que $n$ est un \emph{multiple} \index{multiple}
+de $p$ et que $p$ est un \emph{diviseur}\index{diviseur} de $n$.
\end{Def}
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.
-\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$.
+
+\subsection{Relation de divisibilité}
+
+Dans le chapitre sur les relations entre ensembles,
+on a vu la relation binaire de \og divisibilité\fg{} définie dans $\Net$.
+Cette relation est une relation d'ordre partielle:
+il existe des paires d'entiers non comparables par cette relation.
+
+\begin{Ex}
+3 ne divise pas 7 et 7 ne divise pas 3.
+Ces deux entiers ne sont donc pas comparables du point de vue de la divisibilité.
+\end{Ex}
+
+Cet ordre n'est donc que partiel, mais il existe, pour chaque
+couple d'entiers distincts, une borne inférieure et une borne supérieure.
+Cette relation engendre donc un treillis.
+
+
+\begin{Def}[PGCD, PPCM]
+Tout ensemble fini de nombres entiers strictement positifs admet une borne sup et une borne inf pour la relation de divisibilité.
+
+Cette borne inférieure et cette borne supérieure sont respectivement appelées \emph{plus grand commun diviseur}\index{plus grand commun diviseur} \index{PGCD} et \emph{plus petit commun multiple} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
+\end{Def}
+
+\begin{Notation}
+Ils sont respectivement notés $a\et b$ et $a\ou b$.
+\end{Notation}
+
+
+\begin{Def}
+Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$.
+\end{Def}
+
+
+
+
\begin{Exo}[Nombres de Fermat]
On appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
\begin{enumerate}
\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}
+
+\subsection{PGCD de deux entiers}
-Cette relation est une relation d'ordre partiel : il existe des paires d'entiers non comparables par cette relation.
+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.\\
-\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}
+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.
-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...
+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.\\
-\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é.
+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.
-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}
+\subsection{Algorithme d'Euclide}
+
+\subsubsection{Algorithme}
+\index{algorithme!d'Euclide}
+On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. \\
+
+\noindent Supposons par exemple $a>b$...
+
+\begin{enumerate}
+\item La division euclidienne de $a$ par $b$ peut s'écrire $a=bq+r$ avec $0\infeg r<b$.
+
+\item Soit $d$ un diviseur commun à $a$ et $b$, qui peuvent alors s'écrire $a=da'$ et $b=db'$.
+
+\item L'égalité $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun à $b$ et $r$.
+
+\item Réciproquement, soit $d$ un diviseur commun à $b$ et $r$, qui peuvent alors s'écrire $b=db'$ et $r=dr'$ et l'égalité $a=bq+r$ devient $a=d(b'q+r')$.
+
+Donc $d$ est un diviseur commun à $a$ et $b$, et, par inclusion réciproque, les ensembles des diviseurs communs à $a$ et $b$ d'une part et à $b$ et $r$ d'autre part sont identiques.
+
+En particulier $a\et b=b\et r$.
+
+\item Si $r=0$, le $a\et b=b$, sinon on peut effectuer la division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, tel que $r_{1}<r$ et $b\et r=r\et r_{1}$.
+
+\item Cet algorithme est itéré jusqu'à l'obtention d'un reste nul, ce qui se produit obligatoirement puisqu'il s'agit d'entiers et que la suite des restes ainsi construite est strictement décroissante.
+
+\item Le PGCD est alors l'avant-dernier reste (le dernier non nul).
+\end{enumerate}
+
+
+\begin{Rem}
+Cet algorithme permet donc d'obtenir le PGCD de deux nombres sans connaître leurs décompositions en facteurs premiers.
+\end{Rem}
+
+\subsubsection{Programmation}
+
+Voici sa programmation itérative en C :
+
+\bigskip
+
+{\prol int pgcd ( int a , int b ) \{
+{\dec int r ;
+while ( b != 0 ) \{
+{\dec r = a \% b ;
+ a = b ;
+ b = r ;
+ } \}
+ return a ;
+ }\}
+ }
+
+\bigskip
+
+\noindent (en toute rigueur, il faudrait vérifier que $a$ et $b$ sont bien positifs; par ailleurs, cette fonction retourne 0 comme PGCD de 0 et de 0 : à vérifier avant l'appel).
+
+\bigskip
+
+Voici sa programmation récursive :
+
+\bigskip
+
+ {\prol int pgcd ( int a , int b ) \{
+{\dec
+if ( b == 0 )
+{\dec return a ;}
+else
+{\dec return pgcd ( b , a \% b ) ;}
+}\}}
+
-\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}
\begin{Ex}
\end{Ex}
\begin{Exo}
- Calculez $ppcm(102,138)$.
+ Calculez $102 \ou 138$.
\end{Exo}
\noindent Réponse : 2346.
-\begin{Th}
-$\Net$ est un treillis pour la divisibilité.
+% \begin{Th}
+% $\Net$ est un treillis pour la divisibilité.
-On peut de plus montrer que :
+% 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{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$.
+% \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}
+% Prouvez que si $a$ et $b$ sont premiers entre eux, alors $b|d$
+% \end{Exo}
-\noindent Réponse : En se plongeant dans le calcul modulo $b$, on a : ad = 0.
+% \noindent Réponse : En se plongeant dans le calcul modulo $b$, on a : ad = 0.
-Comme $a$ et $b$ sont premiers entre eux, $a$ est inversible, et donc $d=0$.
+% Comme $a$ et $b$ sont premiers entre eux, $a$ est inversible, et donc $d=0$.
-On en déduit que $d$ est un multiple de $b$.
+% On en déduit que $d$ est un multiple de $b$.
-\section{Algorithmes d'Euclide et applications}
-
-\subsection{PGCD de deux entiers}
-
-On a vu plus haut la justification de l'existence du PGCD de deux nombres strictement positifs par comparaison de leurs décompositions en facteurs premiers.\\
-
-
-Par définition, le PGCD de $a$ non nul avec 0 est $a$ (défintion raisonnable, car 0 est divisible par tout entier non nul, donc par $a$, qui l'est aussi par $a$) et enfin le PGCD de 0 et de 0 n'est pas
-défini.
-
-
-Il est possible de considérer des nombres négatifs (bien que ce soit sans grand intérêt dans les applications pratiques), mais le PGCD est celui des valeurs absolues.\\
-
-L'algorithme consistant à comparer les décompositions en facteurs premiers n'est pas efficace, la découverte de diviseurs de nombres très grands est un problème difficile dont nous reparlerons plus loin.
-
-
-\subsection{Algorithme d'Euclide}
-
-\subsubsection{Algorithme}
-\index{algorithme!d'Euclide}
-On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. \\
-
-\noindent Supposons par exemple $a>b$...
-
-\begin{enumerate}
-\item La division euclidienne de $a$ par $b$ peut s'écrire $a=bq+r$ avec $0\infeg r<b$.
-
-\item Soit $d$ un diviseur commun à $a$ et $b$, qui peuvent alors s'écrire $a=da'$ et $b=db'$.
-
-\item L'égalité $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun à $b$ et $r$.
-
-\item Réciproquement, soit $d$ un diviseur commun à $b$ et $r$, qui peuvent alors s'écrire $b=db'$ et $r=dr'$ et l'égalité $a=bq+r$ devient $a=d(b'q+r')$.
-
-Donc $d$ est un diviseur commun à $a$ et $b$, et, par inclusion réciproque, les ensembles des diviseurs communs à $a$ et $b$ d'une part et à $b$ et $r$ d'autre part sont identiques.
-
-En particulier $a\et b=b\et r$.
-
-\item Si $r=0$, le $a\et b=b$, sinon on peut effectuer la division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, tel que $r_{1}<r$ et $b\et r=r\et r_{1}$.
-
-\item Cet algorithme est itéré jusqu'à l'obtention d'un reste nul, ce qui se produit obligatoirement puisqu'il s'agit d'entiers et que la suite des restes ainsi construite est strictement décroissante.
-
-\item Le PGCD est alors l'avant-dernier reste (le dernier non nul).
-\end{enumerate}
-
-
-\begin{Rem}
-Cet algorithme permet donc d'obtenir le PGCD de deux nombres sans connaître leurs décompositions en facteurs premiers.
-\end{Rem}
-
-\subsubsection{Programmation}
-
-Voici sa programmation itérative en C :
-
-\bigskip
-
-{\prol int pgcd ( int a , int b ) \{
-{\dec int r ;
-while ( b != 0 ) \{
-{\dec r = a \% b ;
- a = b ;
- b = r ;
- } \}
- return a ;
- }\}
- }
-
-\bigskip
-
-\noindent (en toute rigueur, il faudrait vérifier que $a$ et $b$ sont bien positifs; par ailleurs, cette fonction retourne 0 comme PGCD de 0 et de 0 : à vérifier avant l'appel).
-
-\bigskip
-
-Voici sa programmation récursive :
-
-\bigskip
-
- {\prol int pgcd ( int a , int b ) \{
-{\dec
-if ( b == 0 )
-{\dec return a ;}
-else
-{\dec return pgcd ( b , a \% b ) ;}
-}\}}
-
\subsection{Théorème de Bézout}
