X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-maths-dis.git/blobdiff_plain/beb8d60ba6a439d6c62b04baed82daeae79645bb..5e35d149cf50ea634e9a0c02fca2c79993d25427:/arithmetique/entiersNaturels.tex?ds=inline

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index fe36e3e..fbc1326 100755
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -10,19 +10,20 @@ on procÃ¨de en deux Ã©tapes:
   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}
 
@@ -58,25 +59,34 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \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}
 
 
 
@@ -109,6 +119,22 @@ Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
 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.
@@ -116,10 +142,16 @@ Il existe une infinitÃ© de nombres premiers.
 
 
 
-\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}
@@ -135,35 +167,42 @@ La dÃ©composition d'un entier en ses facteurs premiers est unique.
  \'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 
@@ -178,17 +217,21 @@ Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers en
 
 
 \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}
 
@@ -205,7 +248,8 @@ dÃ©fini.
 
 
 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.
 
 
@@ -219,11 +263,17 @@ On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. Supposo
 \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$.
@@ -241,42 +291,26 @@ En particulier $a\et b=b\et r$.
 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  
