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 ;
- }\}
- }
+\begin{Exo}
+Déterminer $154 \land 35$ par l'algorithme d'Euclide.
+\end{Exo}
-\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).
+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
-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{Exo}
+\begin{Exo}[Application de l'algorithme d'Euclide]
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 Montrer que $2^n -1 = 2 \times (2^{n-1} -1) +1$ pour $n \ge 2$.
\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$.
+\item Déterminer un couple 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$.
+\item Déterminer un couple d'entiers relatifs $(u,v)$ tels que $ua + vb=d$.
\end{enumerate}
\end{enumerate}
\end{Exo}
-\subsection{Obtention de cette représentation}
+
L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
\item Les restes successifs (tous strictement inférieurs à $b$), et en commençant par le dernier, constituent la représentation en base $b$ de l'entier donné.
\end{enumerate}
-
-% \subsection{Algorithme de Hörner}
-
-% Réciproquement, étant donnée la représentation en base $b$ d'un
-% entier, on obtient sa valeur par application de l'algorithme de Hörner :
-
-% $n= n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$ est calculé par
-% $(......(((n_{p}b+n_{p-1})b+n_{p-2})b+\cdots+n_{1})b+n_{0})$
-
-
+\begin{Exo}
+Donner la représentation de 23 en base 2.
+\end{Exo}
\begin{Exo}[Numération, changements de base]
\begin{enumerate}
-\item Chercher les entiers dont le carré a, en représentation décimale, mêmes chiffres des dizaines et des unités.
+\item Chercher les entiers dont le carré a, en représentation décimale,
+le même chiffre pour les dizaines et les unités.
\item On pose $a=2p-1$, $b=2p+1$, $c=2p+3$; trouver l'entier $p$ de manière que $a^2+b^2+c^2$ soit de la forme $\sur{xxxx}_{10}$.
\item L'entier $n$ s'écrit $\sur{341}_{10}$ et $\sur{2331}_a$. Trouver $a$.
\item Montrer que, dans toute base $b$ supérieure ou égale à 3, l'entier qui s'écrit $\sur{11211}_b$ n'est pas premier.
-\item soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
+\item Soit $n\geqslant 7$. Donner l'écriture de $(n+1)^4$ en base $n$.
\end{enumerate}
\end{Exo}
\Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
les cas suivants:
\begin{itemize}
-\item $x$ est entier (c'est à dire $q=1$)
+\item $x$ est entier (c'est à dire $q=1$).
\item $x$ est rationnel non entier, et $q$ est premier avec 10 (On
pourra montrer que, si $q$ est premier avec 10, il existe un entier
$k$, non nul, tel que $10^k\equiv 1\ [q]$).
\begin{Exo}
Calculez :
\begin{enumerate}
- \item $3*10^9 mod 97$,
-\item $3^{1024} mod 1037$.
+ \item $3*10^9 \mod 97$,
+\item $3^{1024} \mod 1037$.
\end{enumerate}
\end{Exo}
\begin{itemize}
\item $\qqs x \in \Z, x-x=0=0 \cdot n$; or $0 \in \Z$, donc $x
\equiv x [n]$ (réflexivité). \item Si $x \equiv y
-[n]$,$\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et,
+[n]$, $\exi k \in \Z$, $x-y=k \cdot n$; alors $y-x=(-k) \cdot n$, et,
puisque $k \in \Z$, $(-k) \in \Z$, donc $y \equiv x [n]$ (symétrie).
-\item Si $x \equiv y [n]$,$\exi k\in\Z$, $x-y=k \cdot n$; si, de
+\item Si $x \equiv y [n]$, $\exi k\in\Z$, $x-y=k \cdot n$; si, de
plus, $y \equiv z [n]$, $\exi l\in\Z$, $y-z=l \cdot n$; alors (par
addition), $x-z=(k+l) \times n$; comme $k\in\Z$ et $l\in\Z$,
$(k+l)\in\Z$, donc $x \equiv z [n]$ (transitivité).
$$\left\{\begin{array}{ccc}
x & \equiv & 2\ [88] \\
x & \equiv & 1\ [27] \\
-\end{array}\right.$$
-\item {\it Application: Problème du cuisinier}: Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or, toutes d'égale valeur.
+\end{array}\right..$$
+\item {\it Application au problème du cuisinier}: une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or, toutes d'égale valeur.
Ils décident de se les partager également et de donner le reste éventuel au cuisinier. Celui-ci recevrait alors 3 pièces d'or.
Comme il nous est difficile de représenter ici la liste compléte de tous ces entiers, nous allons illustrer ce propos en supposant que les entiers sont représentés sur 4 bits.
+Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)
-\subsubsection{Illustration dans le cas de 4 bits.}
-
-Pour des mots de 4 bits, il y a alors 16 entiers représentables : (a.s.= arithmétique signée, a.n.s. = arithmétique non signée)\vskip 10pt
\begin{center}\begin{tabular}{|c|c|c|c|} \hline
code binaire & & a.s. & a.n.s. \\ \hline
0000 & interprété par & 0 & 0 \\ \hline
Ainsi, il est facile de déduire la comparaison signée de la comparaison non signée : les codes qui commencent par 1 sont \og plus petits\fg{} que ceux qui commencent par 0, et, s'ils commencent par le même bit, c'est la comparaison non signée qui peut être utilisée.
-Mais il y a quand même deux instructions assembleur distinctes pour la comparaison signée et pour la comparaison non signée.
-
-\subsubsection{Quelques exemples de calculs.}
Pour l'addition et la soustraction, les opérations et les tests de validité des résultats sont les mêmes en arithmétique signée et non signée.
-
-\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).
+Pour la multiplication, l'instruction n'est pas la même (le dépassement de capacité doit être ignoré en a.s. dans le dernier exemple).
\begin{Ex}
Réciproquement, montrer que, si les quotients obtenus en divisant $a$ et $b$ par un diviseur commun $d$ sont premiers entre eux, alors $d=pgcd(a,b)$.
\end{Exo}
-\noindent Réponse : Soit $d = pgcd(a,b)$, et $q_1$ et $q_2$ les quotients de $a$ et $b$ par $d$. Alors $d = aa'+bb' = d q_1 a' + d q_2 b'$. Donc $1 = q_1 a' + q_2 b'$ : $q_1$ et $q_2$ sont premiers entre eux. La réciproque est du même genre.
+\noindent Réponse : Soit $d = \textit{PGCD}(a,b)$, et $q_1$ et $q_2$ les quotients de $a$ et $b$ par $d$. Alors $d = aa'+bb' = d q_1 a' + d q_2 b'$. Donc $1 = q_1 a' + q_2 b'$ : $q_1$ et $q_2$ sont premiers entre eux. La réciproque est du même genre.
Exprimer $pgcd(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602.
\end{Exo}
-%\noindent Réponse $14 = 1330*(-19)+602*42$.
+\begin{Theo}[Théorème de Gauss]
+Soient $a$, $b$ et $c$ trois entiers naturel non nuls.
+Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$,
+alors $a$ divise $c$.
+\end{Theo}
+
+
+\begin{Exo}
+L'objectif est de résoudre l'équation $(E)$ d'inconnues $x$ et $y$
+$405x -120y =15$.
+\begin{enumerate}
+\item Trouver le pgcd de 405 et 120 à l'aide de l'algorithme d'Euclide.
+\item En déduire une solution particulière de cette équation.
+\item En utilisant la solution particulière, montrer que $(E)$ est
+ équivalente à $27(x-3) = 8(y-10)$.
+\item Utiliser le théorème de Gauss pour montrer que
+ l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$.
+\end{enumerate}
+\end{Exo}
-\gsaut
\centerline{\x{Fin du Chapitre}}
\ No newline at end of file
