modifs main et arithmétiques

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

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index fe36e3ea319d7a1c2e7f1be29cb7cdae043909df..fbc1326fadbf13a86765860b297069147dd85b62 100755 (executable)
--- 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 
   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$) ?
 
 
 \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}
 


@@ -58,25 +59,34 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \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}
 
 
 \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}
 \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}
 
 \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}
 
 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.
 
 \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]
 
 \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}
 
 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}
 
  \'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]
 
 
 
 \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 
 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]
 
 
 \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}
 \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 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}
 
 \end{enumerate}
 \end{Exo}
 


@@ -205,7 +248,8 @@ défini.
 
 
 L'algorithme consistant à comparer les décompositions en facteurs
 
 
 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.
 
 
 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$.
 
 \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')$.
 
 \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$.
 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}
 
 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
 
 \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  
 \begin{Exo}
 Si $p$ est un nombre premier, et $n$ un entier avec $n \ge 2$, on note 
 $a=p^n+1$ et