c'est l'hypothèse de récurrence, et on démontre que $P(n+1)$ est vraie.
\end{enumerate}
Le \emph{principe de récurrence} dit alors que $P(n)$ est vraie quel que soit
-l'entier $n \ge n_0$. Une variante consiste à remplacer l'étape~\ref{itm:2} par
-\begin{enumerate}
-\item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre
-$n_0$ et $n$, et on démontre que $P(n+1)$ est vraie.
-\end{enumerate}
-Ceci se déduit du fait que $\N$ est un ensemble complètement ordonné.
+l'entier $n \ge n_0$.
+% Une variante consiste à remplacer l'étape~\ref{itm:2} par
+% \begin{enumerate}
+% \item[2 bis.] on suppose que $P(k)$ est vraie pour tout $k$ compris entre
+% $n_0$ et $n$, et on démontre que $P(n+1)$ est vraie.
+% \end{enumerate}
+% Ceci se déduit du fait que $\N$ est un ensemble complètement ordonné.
\begin{Exo}
\begin{enumerate}
\item Calculez 1, 1+3, 1+3+5, et 1+3+5+7.
\item A quoi $1+3+5+7+...+(2n-1)+(2n+1)$ semble-t-il être égal (en fonction de $n$) ?
-\item Démontrer par récurrence que l'on a effectivement l'égalité
+\item Démontrer par récurrence que l'on a effectivement l'égalité.
\end{enumerate}
\end{Exo}
\end{enumerate}
\end{Exo}
-\begin{Exo}
-Poursuivre le raisonnement pour $S_3(n)$. Cette méthode permet-elle de calculer $S_k(n)$ pour tout $k$ et $n$ dans $\N$?
-\end{Exo}
+% \begin{Exo}
+% 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 pour tout $n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
+Montrer que pour tout entier naturel $n$, 3 divise $4^n -1$.
\end{Exo}
\begin{Exo}
-Soit $(u_n)_{n \in \N}$ une suite réelle telle que pour tout $ n \in \N$,
-$$u_{n+2}-5u_{n+1}+6u_n = 0$$
-Montrez qu'il existe $\alpha, \beta \in \N$ tels quel pour tout $ n \in \N, u_n = \alpha 3^n + \beta 2^n$.
+Soit la suite $(U_n)_{n\in \N}$ définie par $U_n = 3^{2n+1} + 2^{n+2} $.
+\begin{enumerate}
+\item Calculer $U_0$, $U_1$ et $U_2$. Remarquer que ce sont tous
+des multiples de $7$.
+\item Montrer que $U_{n+1} = 7 \times 3^{2n+1} + 2 U_n$.
+\item Montrer que $7$ est un multiple de $U_n$ pour tout entier naturel $n$.
+\end{enumerate}
\end{Exo}
+% \begin{Exo}
+% Soit $(u_n)_{n \in \N}$ une suite réelle telle que pour tout $ n \in \N$,
+% $$u_{n+2}-5u_{n+1}+6u_n = 0$$
+% Montrez qu'il existe $\alpha, \beta \in \N$ tels quel pour tout $ n \in \N, u_n = \alpha 3^n + \beta 2^n$.
+% \end{Exo}
-\begin{Exo}
-Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divisible par $m+n$.
-\end{Exo}
+% \begin{Exo}
+% Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divisible par $m+n$.
+% \end{Exo}
Il existe une infinité de nombres premiers.
\end{Th}
+\begin{Exo}[Nombres premiers en quantité infinie]
+Supposons comme hypothèse que l'ensemble des nombres premiers $\{ p_1, p_2, p_3 \ldots p_{n-1}, p_n \}$ est de cardinalité finie $n$.
+On construit le nombre $N = p_1. p_2. p_3. \ldots .p_{n-1}. p_n +1$.
+\begin{enumerate}
+\item Montrer que d'après l'hypothèse, il existe un nombre premier $q$ tel que
+ $N$ est un multiple de $q$.
+\item Montrer cependant que $N$ n'est pas un multiple de $p_1$. Idem pour $p_2$, \ldots $p_n$.
+\item En déduire que $q$ est un nombre premier différent de $p_1$, de $p_2$, \ldots de $p_n$.
+\item En déduire une contradiction dans l'hypothèse.
+\end{enumerate}
+\end{Exo}
+
+
+
+
+
\begin{Rem}
Le problème de la primalité d'un nombre (très grand, évidemment) est difficile.
-\subsection{Décomposition en facteurs premiers}
+%\subsection{Décomposition en facteurs premiers}
\begin{Def}[Décomposition en facteurs premiers]
-L'écriture d'un entier $n$ sous la forme $n=a^{\alpha}b^{\beta}c^{\gamma}\ldots$, où $a\vir b\vir c\vir\ldots$ sont les diviseurs premiers distincts de $n$ et où les exposants $\alpha\vir\beta\vir\gamma\vir\ldots$ sont tels que, par exemple, $n$ est divisible par $a^{\alpha}$ mais pas par $a^{\alpha+1}$ s'appelle la \emph{décomposition en facteurs premiers} \index{décomposition en facteurs premiers} de $n$.
+L'écriture d'un entier $n$ sous la forme $n=a^{\alpha}b^{\beta}c^{\gamma}\ldots$, où \begin{itemize}
+\item $a$, $b$, $c$, \ldots sont des nombres premiers distincts
+deux à deux tels que $a < b < c < ldots$;
+\item les exposants $\alpha$, $\beta$, $\gamma$ sont des entiers naturels
+ non nuls;
+\end{itemize}
+\noindent s'appelle la \emph{décomposition en facteurs premiers} \index{décomposition en facteurs premiers} de $n$.
On dit que les exposants $\alpha$, $\beta$, $\gamma$, \ldots sont les ordres de multiplicité des diviseurs $a$, $b$, $c$, \ldots
\end{Def}
\'Ecrivez les nombres 3850 et 1911 sous forme de produits de nombres premiers.
\end{Exo}
-\noindent Réponses : $2*5^2*7*11$ et $3*7^2*13$.
+%\noindent Réponses : $2*5^2*7*11$ et $3*7^2*13$.
-\subsection{Relation de divisibilité}
+%\subsection{Relation de divisibilité}
-Dans le chapitre sur les relations entre ensembles,
-on a vu 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.
+% 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.
+% Cependant 2 divise 6 et 14. C'est le plus grand des minorants de 6 et 14
+% selon cette relation. C'est donc la borne inférieure.
+% De même 42 est divisible par 6 et 14 aussi.
+% C'est le plus petit des majorants de 6 et 14
+% selon cette relation. C'est donc la borne supérieure.
+% Chaque couple d'entiers a donc une borne inférieure et une borne supérieure.
\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.
-
+Soient $a$ et $b$ deux entiers naturels strictement positifs.
+\begin{itemize}
+\item L'ensemble des diviseurs communs à
+$a$ et $b$ admet un plus grand élément $d$,
+le \emph{plus grand commun diviseur (PGCD)}\index{plus grand commun diviseur}\index{PGCD}
+de ces entiers. On le note $\textit{PGCD}(a,b)$.
+\item L'ensemble des multiples strictement positifs
+ communs à $a$ et $b$ admet un plus petit élément $m$,
+le \emph{plus petit commun multiple (PPCM)} \index{PPCM} \index{plus petit commun multiple} de ces deux entiers.
+On le note $\textit{PPCM}(a,b)$.
+\end{itemize}
Pour $a$ et $b$ dans $\N$,
$\textit{PGCD}(a,b)$ et
$\textit{PPCM}(a,b)$ et
\begin{Exo}[Nombres de Fermat]
-Pour $p \in \N$, on appelle nombres de Fermat les nombres de la forme $2^{2^p}+1$.
+Pour $p \in \N$, on appelle nombres de Fermat les nombres de la forme
+$F_p = 2^{2^p}+1$.
\begin{enumerate}
-\item Montrer que, pour que $2^n+1$ soit premier, il faut que $n$ soit une puissance de 2.
+\item Montrer que,
+ pour que $2^n+1$ soit premier, il est nécessaire
+ que $n$ soit une puissance de 2.
-\item La réciproque n'est pas vraie : donner un exemple de nombre de Fermat qui ne soit pas premier.
+\item Pour montrer que ce n'est pas suffisant, vérifier que $F_5$ est
+ divisible par 641.
\item Montrer que, pour $k\geqslant 1$, $F_p$ divise $F_{p+k}-2$.
\item En déduire que $F_p$ et $F_{p+k}$ sont premiers entre eux.
-\item En déduire qu'il existe une infinité de nombres premiers.
+%\item En déduire qu'il existe une infinité de nombres premiers.
\end{enumerate}
\end{Exo}
L'algorithme consistant à comparer les décompositions en facteurs
-premiers n'est pas efficace, la découverte de diviseurs de nombres
+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{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 Montrons que \og $d$ est un diviseur commun à $a$ et $b$ \fg{}
+ est équivalent à \og $d$ est un diviseur commun à $b$ et $r$ \fg{}.
+\begin{itemize}
+\item Soit $d$ un diviseur commun à $a$ et $b$, qui peuvent alors s'écrire $a=da'$ et $b=db'$. L'égalité $a=bq+r$ devient $da'=db'q+r$ ou encore $r=d(a'-b'q)$, donc $d$ est aussi un diviseur commun à $b$ et $r$.
\item Réciproquement, soit $d$ un diviseur commun à $b$ et $r$, qui peuvent alors s'écrire $b=db'$ et $r=dr'$ et l'égalité $a=bq+r$ devient $a=d(b'q+r')$.
+Donc $d$ est un diviseur commun à $a$ et $b$.
+\end{itemize}
-Donc $d$ est un diviseur commun à $a$ et $b$, et, par inclusion réciproque, les ensembles des diviseurs communs à $a$ et $b$ d'une part et à $b$ et $r$ d'autre part sont identiques.
+Ainsi, les ensembles des diviseurs communs à $a$ et $b$
+d'une part et à $b$ et $r$ d'autre part sont identiques.
En particulier $a\et b=b\et r$.
\item Si $r=0$ on a $a\et b= b\et 0$ qui est égal à $b$.
Cet algorithme permet donc d'obtenir le PGCD de deux nombres sans connaître leurs décompositions en facteurs premiers.
\end{Rem}
-\subsubsection{Programmation}
-
-Voici sa programmation itérative en C :
-
-\bigskip
-
-{\prol int pgcd ( int a , int b ) \{
-{\dec int r ;
-while ( b != 0 ) \{
-{\dec r = a \% b ;
- a = b ;
- b = r ;
- } \}
- return a ;
- }\}
- }
-
-\bigskip
-
-\noindent (en toute rigueur, il faudrait vérifier que $a$ et $b$ sont bien positifs; par ailleurs, cette fonction retourne 0 comme PGCD de 0 et de 0 : à vérifier avant l'appel).
+\begin{Exo}
+Déterminer $154 \land 35$ par l'algorithme d'Euclide.
+\end{Exo}
-\bigskip
-Voici sa programmation récursive :
+Voici sa programmation itérative en Python:
+\begin{scriptsize}
+\begin{verbatim}
+def pgcd_euclide(a,b) :
+ assert a>b and b >=0
+ while b != 0 :
+ r = a%b
+ a = b
+ b = r
+ return a
+\end{verbatim}
+\end{scriptsize}
\bigskip
- {\prol int pgcd ( int a , int b ) \{
-{\dec
-if ( b == 0 )
-{\dec return a ;}
-else
-{\dec return pgcd ( b , a \% b ) ;}
-}\}}
-
-
\begin{Exo}
Si $p$ est un nombre premier, et $n$ un entier avec $n \ge 2$, on note
$a=p^n+1$ et
