t

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

diff --git a/arithmetique/entiersNaturels.tex b/arithmetique/entiersNaturels.tex
index 1fc13ca87f78e0645df21b23a7c04e5dc4c966d0..81ddb5b12a81fef980a32a2735893c9ca7ca8041 100755 (executable)
--- a/arithmetique/entiersNaturels.tex
+++ b/arithmetique/entiersNaturels.tex
@@ -1,6 +1,6 @@
 \section{Principe de récurrence }
 
 \section{Principe de récurrence }
 

-Pour démontrer par \emp{récurrence}
+Pour démontrer par \emph{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:
 \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:


@@ -10,36 +10,37 @@ 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 $\Nat$ 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}
 
 

-\begin{Exo}
-On souhaite calculer $S_1(n) = 1+2+...+n$.
-\begin{enumerate}
-\item Cherchez un bon candidat $S_1(n)$ pour cette formule.
-\begin{itemize}
-\item On pourra chercher un lien logique entre $S_1(1), S_1(2), S_1(3), S_1(4), ...$
-\item On pourra aussi faire le lien avec les suites arithmétiques.
-\item Ou encore, retrouver la méthode de Gauss : $S = 1+2+...+n$, et $S = n+(n-1)+...+2+1$. Si on somme ces deux expressions...
-\end{itemize}
-\item Prouvez, par récurrence, que la somme est bien égale à ce candidat.
-\item Quelle est la \og forme \fg{} de ce candidat (fonction tangente ? polynôme ?) 
-\end{enumerate}
-\end{Exo}
+% \begin{Exo}
+% On souhaite calculer $S_1(n) = 1+2+...+n$.
+% \begin{enumerate}
+% \item Cherchez un bon candidat $S_1(n)$ pour cette formule.
+% \begin{itemize}
+% \item On pourra chercher un lien logique entre $S_1(1), S_1(2), S_1(3), S_1(4), ...$
+% \item On pourra aussi faire le lien avec les suites arithmétiques.
+% \item Ou encore, retrouver la méthode de Gauss : $S = 1+2+...+n$, et $S = n+(n-1)+...+2+1$. Si on somme ces deux expressions...
+% \end{itemize}
+% \item Prouvez, par récurrence, que la somme est bien égale à ce candidat.
+% \item Quelle est la \og forme \fg{} de ce candidat (fonction tangente ? polynôme ?) 
+% \end{enumerate}
+% \end{Exo}

 
 
 \begin{Exo}
 
 
 \begin{Exo}


@@ -51,32 +52,41 @@ On souhaite calculer $S_2(n) = 1^2+2^2+...+n^2$.
 \item Ou encore, 
 \begin{itemize}
 \item Regardez la forme de $S_0(n) = 1^0+2^0+...+n^0$, et de $S_1(n) = 1^1+2^1+...+n^1$
 \item Ou encore, 
 \begin{itemize}
 \item Regardez la forme de $S_0(n) = 1^0+2^0+...+n^0$, et de $S_1(n) = 1^1+2^1+...+n^1$

-\item Interpolez la formule pour $S_2(n)$. On pourra imaginer que $S_2(n)$ est toujours un polynôme en $n$. Quel serait son degré le plus probable ? Quelle en serait donc la forme ? On aura à déterminer les coefficients intervenant dans ce polynôme. Pour ce faire, il suffit de considérer que cette formule doit convenir pour n=1, 2, etc.
+\item Extrapolez la formule pour $S_2(n)$. On pourra imaginer que $S_2(n)$ est toujours un polynôme en $n$. Quel serait son degré le plus probable ? Quelle en serait donc la forme ? On aura à déterminer les coefficients intervenant dans ce polynôme. Pour ce faire, il suffit de considérer que cette formule doit convenir pour n=1, 2, etc.

 \end{itemize}
 \end{itemize}
 \item Démontrez, par récurrence, que l'on a bien égalité entre $1^2+2^2+...+n^2$ et votre candidat.
 \end{enumerate}
 \end{Exo}
 
 \end{itemize}
 \end{itemize}
 \item Démontrez, par récurrence, que l'on a bien égalité entre $1^2+2^2+...+n^2$ et votre candidat.
 \end{enumerate}
 \end{Exo}
 

-\begin{Exo}
-Poursuivre le raisonnement pour $S_3(n)$. Cette méthode permet-elle de calculer $S_k(n), \forall k,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 $\forall 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 $\forall n \in \N$,
-$$u_{n+2}-5u_{n+1}+6u_n = 0$$
-Montrez qu'il existe $\alpha, \beta \in \N$ tels quel $\forall 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}

 
 
 
 
 
 


@@ -87,9 +97,9 @@ Montrer que $\forall m,n \in \N^*, \forall r \in \N, m^{2r+1}+n^{2r+1}$ est divi
 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$.

+On écrit aussi $p \mid n$ pour $p$ divise $n$.

 \end{Def}
 
 \end{Def}
 

-

 \begin{Exo}
  Soit $m = 2^3 * 5 * 7^2 * 13^3$. Combien le nombre $m$ a-t-il de diviseurs naturels ?
 \end{Exo}
 \begin{Exo}
  Soit $m = 2^3 * 5 * 7^2 * 13^3$. Combien le nombre $m$ a-t-il de diviseurs naturels ?
 \end{Exo}


@@ -101,14 +111,30 @@ Un \emph{nombre premier}\index{nombre!premier} est un nombre entier strictement
 \end{Def}
 
 
 \end{Def}
 
 

-\begin{Ex}
+\begin{Exo}

 Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.
 Ainsi, le plus petit nombre premier (et le seul qui soit pair) est 2.

-\end{Ex}
+\end{Exo}

 
 \begin{Th}
 Il existe une infinité de nombres premiers.
 \end{Th}
 
 
 \begin{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,12 +142,18 @@ 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)
+On dit que les exposants $\alpha$, $\beta$, $\gamma$, \ldots sont les ordres de multiplicité des diviseurs $a$, $b$, $c$, \ldots

 \end{Def}
 
 
 \end{Def}
 
 


@@ -135,40 +167,49 @@ 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 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.
+% 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.

 
 

-\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}
+% 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. 

 
 

-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]
 
 
 \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.
+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 
+sont respectivement notés $a\et b$ et $a\ou b$.

 \end{Def}
 
 \end{Def}
 

-\begin{Notation}
-Ils sont respectivement notés $a\et b$ et $a\ou b$.
-\end{Notation}
-
-
-\begin{Def}
+\begin{Def}[Nombres premiers entre eux]

 Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$. 
 \end{Def}
 
 Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers entre eux} lorsque $a\et b=1$. 
 \end{Def}
 


@@ -176,64 +217,73 @@ Deux nombres entiers strictement positifs $a$ et $b$ sont dits \emph{premiers en
 
 
 \begin{Exo}[Nombres de Fermat]
 
 
 \begin{Exo}[Nombres de Fermat]

-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}
 
 
 

-\section{Algorithmes d'Euclide et applications}
+\section{Algorithmes d'Euclide et applications}\index{algorithme!d'Euclide}

 
 

-\subsection{PGCD de deux entiers} 
+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.

 
 

-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.
+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.

 
 
 
 

-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$...
+On se limite ici au cas de deux entiers $a$ et $b$ strictement positifs. 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$.
 
 
 \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 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$.
 
 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 Si $r=0$ on a $a\et b= b\et 0$ qui est égal à $b$.

 
 

-\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 Sinon,  $r$ est différent de $0$ et on peut donc effectuer la
+  division euclidienne de $b$ par $r$, qui donne un reste $r_{1}$, 
+  tel que $0 \le r_{1}<r$ et $b\et r=r\et r_{1}$.

 
 

-\item Le PGCD est alors l'avant-dernier reste (le dernier non nul).
+\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.
+  Le PGCD est alors l'avant-dernier reste (le dernier non nul).

 \end{enumerate}
 
 
 \end{enumerate}
 
 


@@ -241,64 +291,49 @@ 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
+\begin{Exo}
+Déterminer $154 \land 35$ par l'algorithme d'Euclide.
+\end{Exo}

 
 

-\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 :
+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{Ex}
+\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}
 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 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$.
 \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{enumerate}
 \end{enumerate}

-\end{Ex}
+\end{Exo}

 
 

-% \begin{Ex}
+% \begin{Exo}

 % Comme $48=2^43$ et que $56=2^37$, on voit aisément que $48\et 56=2^3$.
 % Comme $48=2^43$ et que $56=2^37$, on voit aisément que $48\et 56=2^3$.

-% \end{Ex}
+% \end{Exo}

 
 % \begin{Exo}
 %  Calculez $102 \ou 138$.
 
 % \begin{Exo}
 %  Calculez $102 \ou 138$.


@@ -335,23 +370,14 @@ $b=p^n-1$.
 
 
 
 
 
 

-\subsection{Entiers relatifs}
-
-L'ensemble habituellement noté $\Z$ des entiers relatifs est obtenu à partir de $\N$ par le procédé de symétrisation pour l'addition.\\
-
-
-Sans s'étendre sur le sujet, disons que cela consiste à introduire les entiers strictement négatifs comme opposés des positifs correspondants, par $n+(-n)=0$.\\
-
-
-On sait que les porpriétés des opérations sont conservées; la seule propriété perdue dans cette extension est la compatibilté entre la relation d'ordre et la multiplication.\\
-
-En revanche, on gagne évidemment l'existence d'un opposé pour chaque entier.
-

 
 
 \section{Division euclidienne dans $\Z$ et applications}
 
 
 
 \section{Division euclidienne dans $\Z$ et applications}
 

-\subsection{Définition}
+L'ensemble habituellement noté $\Z$ des entiers relatifs
+est obtenu à partir de $\N$ par le procédé de symétrisation pour l'addition: 
+cela consiste à introduire les entiers strictement négatifs comme
+opposés des positifs correspondants, par $n+(-n)=0$.

 
 
 On se donne deux entiers relatifs $a$ et $b$, $b$ non nul.
 
 
 On se donne deux entiers relatifs $a$ et $b$, $b$ non nul.


@@ -365,10 +391,10 @@ vérifient la relation suivante : $a=bq+r$ , avec $0\leqslant r<|b|$.
 \begin{Def}[Division euclidienne]
 Obtenir les valeurs de $q$ et de $r$, c'est effectuer la \emph{division
 euclidienne}\index{division euclidienne} de $a$ par $b$.
 \begin{Def}[Division euclidienne]
 Obtenir les valeurs de $q$ et de $r$, c'est effectuer la \emph{division
 euclidienne}\index{division euclidienne} de $a$ par $b$.

-
-$q$ est appelé \emph{quotient}\index{quotient}, $r$ est appelé \index{reste}\emph{reste} (dans la division euclidienne).
-
-Enfin, lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un \emph{diviseur} de $a$.
+Le nombre $q$ est appelé \emph{quotient}\index{quotient}, et 
+le nombre $r$ est appelé \index{reste}\emph{reste} 
+(dans la division euclidienne).
+Lorsque $r$ est nul, $a$ est dit \emph{divisible} par $b$, ou $b$ est un \emph{diviseur} de $a$.

 \end{Def}
 
 
 \end{Def}
 
 


@@ -383,21 +409,16 @@ Tout nombre non nul est au moins divisible par 1 et par lui-même ($a=a\times 1+
 
 \begin{Exo}
 Quels sont le quotient et le reste de la division euclidienne de $m$ par $n$ dans le cas où :
 
 \begin{Exo}
 Quels sont le quotient et le reste de la division euclidienne de $m$ par $n$ dans le cas où :

-

 \begin{enumerate}
  \item $m = -38$ et $n=6$,
 \item $m=165$ et $n=-14$.
 \end{enumerate}
 \begin{enumerate}
  \item $m = -38$ et $n=6$,
 \item $m=165$ et $n=-14$.
 \end{enumerate}

-
-Réponses : (-7,4) et (-11,11).
-

 \end{Exo}
 
 
 
 \end{Exo}
 
 
 

-\begin{Exo}[Divisibilité dans $\N$]
+\begin{Exo}

 On se place dans l'ensemble $\N$.
 On se place dans l'ensemble $\N$.

-

 \begin{enumerate}
 \item Trouver les restes dans la division par 5 du carré d'un entier.
 \item Trouver les restes dans la division par 8 du carré d'un entier impair.
 \begin{enumerate}
 \item Trouver les restes dans la division par 5 du carré d'un entier.
 \item Trouver les restes dans la division par 8 du carré d'un entier impair.


@@ -407,29 +428,24 @@ On se place dans l'ensemble $\N$.
 \end{Exo}
 
 
 \end{Exo}
 
 

-\subsection{Représentation des nombres entiers}
+\section{Représentation des nombres entiers}
+

 
 

-\subsubsection{Définition}

 
 \begin{Def}[Principe de la numération de position]
 \index{Principe de la numérotation de position}
 Il consiste à choisir une base $b$ de numération, et $b$ symboles qui constitueront les chiffres dans la représentation d'un entier positif en base $b$.
 
 \begin{Def}[Principe de la numération de position]
 \index{Principe de la numérotation de position}
 Il consiste à choisir une base $b$ de numération, et $b$ symboles qui constitueront les chiffres dans la représentation d'un entier positif en base $b$.

-

 Celle-ci s'écrira alors
 $$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$ 
 Celle-ci s'écrira alors
 $$n=n_{p}b^p+n_{p-1}b^{p-1}+\cdots+n_{1}b^1+n_{0}$$ 

-\end{Def}
-

 
 

-\begin{Notation}

 Cette écriture est abrégée en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.
 Cette écriture est abrégée en ${\left(\overline{n_{p}n_{p-1}\ldots n_{0}}\right)}_{b}$.

-\end{Notation}
+\end{Def}

 
 

-\begin{Rem}

 En informatique, on utilise couramment les bases 2, 8 et 16.
 En informatique, on utilise couramment les bases 2, 8 et 16.

-\end{Rem}

 
 
 
 

-\subsubsection{Obtention de cette représentation}
+
+

 
 L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
 
 
 L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
 


@@ -439,26 +455,20 @@ 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}
 
 \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}
 

-
-\subsubsection{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}

 
 
 
 

-\subsubsection{Exercices}

 
 \begin{Exo}[Numération, changements de base]
 \begin{enumerate}
 
 \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 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}
 
 \end{enumerate}
 \end{Exo}
 


@@ -486,7 +496,7 @@ considère un rationnel $x=\fr pq$ , avec $q>0$, $p\in
 \Z$, $p$ et $q$ premiers entre eux, et on étudiera successivement
 les cas suivants:
 \begin{itemize}
 \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]$).
 \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]$).


@@ -497,20 +507,32 @@ $k$, non nul, tel que $10^k\equiv 1\ [q]$).
 \end{Exo}
 
 
 \end{Exo}
 
 

-\subsection{Arithmétique modulo $n$} 
+\section{Arithmétique modulo $n$} 

 
 On rappelle ici la définition de la relation dite de \og congruence modulo n\fg{} définie dans $\Z$ étudiée dans le chapitre consacré aux relations entre ensembles.
 
 \begin{Def}[Congruence modulo $n$]
 Soit $n$ un entier strictement supérieur à 1 et $x$ et $y$ deux éléments de $\Z$.
 
 On rappelle ici la définition de la relation dite de \og congruence modulo n\fg{} définie dans $\Z$ étudiée dans le chapitre consacré aux relations entre ensembles.
 
 \begin{Def}[Congruence modulo $n$]
 Soit $n$ un entier strictement supérieur à 1 et $x$ et $y$ deux éléments de $\Z$.

-

 On dit que \og $x$ est \emph{congru} à $y$ \emph{modulo}\index{congru}\index{modulo} $n$\fg{} lorsque $x$ et $y$ possèdent le même reste dans la division (euclidienne) par $n$ :
 $$x \equiv y [n] \Ssi \exi k \in \Z, x-y=k \cdot n $$
 \end{Def}
 
 
 On dit que \og $x$ est \emph{congru} à $y$ \emph{modulo}\index{congru}\index{modulo} $n$\fg{} lorsque $x$ et $y$ possèdent le même reste dans la division (euclidienne) par $n$ :
 $$x \equiv y [n] \Ssi \exi k \in \Z, x-y=k \cdot n $$
 \end{Def}
 
 

+\begin{Exo}
+ Calculez :
+\begin{enumerate}
+ \item $3*10^9 \mod 97$,
+\item $3^{1024} \mod 1037$.
+\end{enumerate}
+\end{Exo}
+
+%\noindent Réponses : 5 et 630.
+
+
+
+

 \begin{Th}
 \begin{Th}

-Il s'agit d'une relation d'équivalence dans $\Z$. 
+La relation de congruence modulo $n$ est une relation d'équivalence dans $\Z$. 

 \end{Th}
 
 \begin{Proof}
 \end{Th}
 
 \begin{Proof}


@@ -518,9 +540,9 @@ En effet :
 \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
 \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).
 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é).
 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é).


@@ -541,10 +563,11 @@ Si $n = 3$, il y a trois classes distinctes :
 On retrouve ensuite les mêmes éléments : $\dot 3=\dot 0$, etc... 
 \end{Ex}
 
 On retrouve ensuite les mêmes éléments : $\dot 3=\dot 0$, etc... 
 \end{Ex}
 

-

 D'une manière générale, pour $n$ quelconque, il y a exactement $n$ classes d'équivalence, notées de $\dot 0$ à $\dot {(n-1)}$, c'est-à-dire, il faut le remarquer, un nombre fini.
 
 
 D'une manière générale, pour $n$ quelconque, il y a exactement $n$ classes d'équivalence, notées de $\dot 0$ à $\dot {(n-1)}$, c'est-à-dire, il faut le remarquer, un nombre fini.
 
 

+
+

 \begin{Th}
 L'ensemble-quotient (ensemble des classes d'équivalence) de la relation de congruence modulo $n$ est un ensemble fini.
 \end{Th}
 \begin{Th}
 L'ensemble-quotient (ensemble des classes d'équivalence) de la relation de congruence modulo $n$ est un ensemble fini.
 \end{Th}


@@ -559,27 +582,51 @@ Il est noté $\Z/n\Z$.
 \end{Ex}
 
 
 \end{Ex}
 
 

+\begin{Def}
+On dit qu'une relation d'équivalence, notée  $\equiv$, 
+définie dans une structure algébrique $S$, 
+est compatible avec les lois de $S$  
+lorsque les résultats des opérations effectuées sur des éléments équivalents
+demeurent équivalents:
+\begin{itemize}
+\item pour l'addition: si $x \equiv x'$ et  $y \equiv y'$, 
+alors on doit avoir $x + y  \equiv x' + y'$;
+\item pour la multiplication $\times$:  si $x \equiv x'$ et  $y \equiv y'$, 
+alors on doit avoir $x \times y  \equiv x' \times y'$.
+\end{itemize}
+\end{Def}
+
+
+
+
+

 \begin{Th}
 La relation de \og congruence modulo $n$\fg{} est compatible avec l'addition et la multiplication des nombres entiers. 
 \end{Th}
 
 
 \begin{Proof}
 \begin{Th}
 La relation de \og congruence modulo $n$\fg{} est compatible avec l'addition et la multiplication des nombres entiers. 
 \end{Th}
 
 
 \begin{Proof}

-En effet, on suppose que :
+En effet, on suppose que:

 \begin{itemize}
 \begin{itemize}

-\item $x \equiv x' [n] \Ssi \exi k\in \Z,\ x-x'=k \cdot n$ et que
+\item $x \equiv x' [n] \Ssi \exi k\in \Z,\ x-x'=k \cdot n$;

 \item $y \equiv y' [n] \Ssi \exi l\in \Z, y-y'=l \cdot n$.
 \item $y \equiv y' [n] \Ssi \exi l\in \Z, y-y'=l \cdot n$.

-\item Alors, par addition, $(x+y)-(x'+y')=(k+l)\cdot n$; $(k+l)\in\Z$, donc $(x+y)\equiv(x'+y') [n]$ : la congruence modulo $n$ est compatible avec l'addition dans $\Z$.

 \end{itemize}
 \end{itemize}

-En multipliant la première égalité par y : $xy-x'y=(ky)\cdot n$ et la seconde par x' : $x'y-x'y'=(x'l)\cdot n$ .
-
-Alors, par addition, $xy-x'y'=(ky+lx')\cdot n$. $(ky+lx')\in\zmat$, donc $x\cdot y\equiv x'\cdot y' [n]$ : la congruence modulo $n$ est aussi compatible avec la multiplication dans $\Z$.
+Alors:
+\begin{itemize}
+\item par addition, $(x+y)-(x'+y')=(k+l)\cdot n$; $(k+l)\in\Z$, donc $(x+y)\equiv(x'+y') [n]$: la congruence modulo $n$ est compatible avec l'addition dans $\Z$
+\item en multipliant l'égalité $x-x'=k \cdot n$  par $y$, on a 
+  $xy-x'y=(ky)\cdot n$ et l'égalité 
+  $y-y'=l \cdot n$
+  par $x'$ on a $x'y-x'y'=(x'l)\cdot n$.
+  
+  Par addition, $xy-x'y'=(ky+lx')\cdot n$. $(ky+lx')\in\zmat$, donc $x\cdot y\equiv x'\cdot y' [n]$: la congruence modulo $n$ est aussi compatible avec la multiplication dans $\Z$.
+\end{itemize}

 \end{Proof}
 
 
 \end{Proof}
 
 

-\begin{Rem}
-C'est cette propriété qui permet de définir dans l'ensemble quotient $\Z/n\Z$ des opérations, dites \emph{induites} par celles qui existent dans $\Z$...
-\end{Rem}
+% \begin{Rem}
+% C'est cette propriété qui permet de définir dans l'ensemble quotient $\Z/n\Z$ des opérations, dites \emph{induites} par celles qui existent dans $\Z$...
+% \end{Rem}

 
 
 
 
 
 


@@ -620,14 +667,16 @@ On aperçoit la présence de \og diviseurs de zéro\fg{} ($\dot 2 \times \dot 2=
 
 
 \begin{Exo}
 
 
 \begin{Exo}

- Calculez :
+Résolvez modulo 18 les équations suivantes :
+

 \begin{enumerate}
 \begin{enumerate}

- \item $3*10^9 mod 97$,
-\item $3^{1024} mod 1037$.
+ \item $2x+17 = 15$,
+\item $3x+4 = 12$,
+\item $5x+13 = 16$.

 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 

-\noindent Réponses : 5 et 630.
+%\noindent Réponses : \{8,17\}, \{ \} et \{15\}.

 
 
 \begin{Exo}[Systèmes de congruences]
 
 
 \begin{Exo}[Systèmes de congruences]


@@ -642,7 +691,7 @@ Un tel système peut ne pas avoir de solution
 Une condition suffisante d'existence de
 solutions est que $p$ et $q$ soient premiers entre eux.
 
 Une condition suffisante d'existence de
 solutions est que $p$ et $q$ soient premiers entre eux.
 

-C'est le cas que nous traiterons ici; dans ce cas, il existe deux entiers $u$ et $v$ tels que $pu+qv=1$ (théorème de Bezout).
+C'est le cas que nous traiterons ici; dans ce cas, il existe deux entiers $u$ et $v$ tels que $pu+qv=1$ (théorème de Bézout).

 
 Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution du système (pourquoi??); les autres sont de la forme $x + kpq$, où $k$ est un entier quelconque.
 \begin{enumerate}
 
 Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution du système (pourquoi??); les autres sont de la forme $x + kpq$, où $k$ est un entier quelconque.
 \begin{enumerate}


@@ -650,8 +699,8 @@ Donc $pu \equiv 1\ [q]$ et $qv \equiv 1\ [p]$, et $x=bpu+aqv$ est une solution d
 $$\left\{\begin{array}{ccc}
 x & \equiv & 2\ [88] \\
 x & \equiv & 1\ [27] \\
 $$\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. 
 
 
 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. 
 


@@ -664,49 +713,37 @@ Quel est le plus petit nombre de pièces d'or qu'il espère lorsqu'il décide d'
 \end{Exo}
 
 
 \end{Exo}
 
 

-\begin{Exo}
-Résolvez modulo 18 les équations suivantes :
-
-\begin{enumerate}
- \item $2x+17 = 15$,
-\item $3x+4 = 12$,
-\item $5x+13 = 16$.
-\end{enumerate}
-\end{Exo}
-
-\noindent Réponses : \{8,17\}, \{ \} et \{15\}.

 
 
 \begin{Exo}
  Si $m$ est un entier naturel plus grand que 2, quel est l'inverse de $m-1$ modulo $m$ ?
 \end{Exo}
 
 
 
 \begin{Exo}
  Si $m$ est un entier naturel plus grand que 2, quel est l'inverse de $m-1$ modulo $m$ ?
 \end{Exo}
 

-\noindent Réponse : $m-1$.
+%\noindent Réponse : $m-1$.

 
 
 \begin{Exo}
 Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) mod p = 0$.
 
 
 \begin{Exo}
 Un nombre \og pseudo-premier de base $b$ \fg{}\index{pseudo-premier} est un entier naturel non premier $p$ tel que $(b^p-b) mod p = 0$.

-

 Vérifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de base 2.
 \end{Exo}
 
 
 Vérifier que 561 est pseudo-premier de base 3 et que 341 est pseudo-premier de base 2.
 \end{Exo}
 
 

-\subsection{Division \og entière\fg{} informatique et division euclidienne}
+\section{Arithmétique en informatique}

 
 
 
 

-La plupart des langages de programmation utilisés en informatique disposent d'un type de données pour représenter ce que les informaticiens appellent les entiers signés (les entiers relatifs) et possèdent des opérateurs pour effectuer les calculs classiques sur ces nombres.\\
+La plupart des langages de programmation utilisés en informatique disposent d'un type de données pour représenter ce que les informaticiens appellent les entiers signés (les entiers relatifs) et possèdent des opérateurs pour effectuer les calculs classiques sur ces nombres.

 
 

+\subsection{Division entière}

 
 

-En C ou java, par exemple, le symbole $/$ représente le quotient dans la \og division entière\fg{} et le symbole $\%$ représente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entière\fg{} ).\\
+En C ou java, par exemple, le symbole $/$ représente le quotient dans la \og division entière\fg{} et le symbole $\%$ représente ce que les informaticiens appellent improprement le modulo (le reste dans leur \og division entière\fg{} ).

 
 
 
 

-Pour des raisons pratiques de réalisation des micro-circuits des processeurs qui réalisent ces opérations, la \og division entière\fg{} ne donne pas exactement le même résultat que la division euclidienne.\\
+Pour des raisons pratiques de réalisation des micro-circuits des processeurs qui réalisent ces opérations, la \og division entière\fg{} ne donne pas exactement le même résultat que la division euclidienne.

 
 
 
 Considérons par exemple les 4 cas possibles de division euclidienne de $a$ par $b$ lorsque $|a|=29$ et $|b|=7$ (en n'oubliant pas que le reste d'une division euclidienne ne peut être que positif)
 
 
 
 
 Considérons par exemple les 4 cas possibles de division euclidienne de $a$ par $b$ lorsque $|a|=29$ et $|b|=7$ (en n'oubliant pas que le reste d'une division euclidienne ne peut être que positif)
 

-\bigskip

 
 \begin{center}
 \begin{tabular}{|c|c|c|c|c|c|c|}
 
 \begin{center}
 \begin{tabular}{|c|c|c|c|c|c|c|}


@@ -719,39 +756,37 @@ $-29$ &$-7$ & $-29=5\times (-7)+6$ & $5$ & $6$ & $4$ & $-1$ \\ \hline
 \end{tabular}
 \end{center}
 
 \end{tabular}
 \end{center}
 

-\bigskip

 
 

-Autrement dit, mathématiquement, le quotient est positif lorsque les deux nombres ont le même signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas être le quotient des valeurs absolues.\\
+
+Autrement dit, mathématiquement, le quotient est positif lorsque les deux nombres ont le même signe et le reste est toujours positif, et, pour que le reste soit toujours positif, le quotient peut ne pas être le quotient des valeurs absolues.

 
 
 
 

-Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le même signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.\\
+Informatiquement, le \og quotient\fg{} est positif lorsque les nombres ont le même signe, le \og reste\fg{} a le signe du dividende, et la valeur absolue du \og quotient\fg{} est toujours le quotient des valeurs absolues.

 
 
 Dans les applications de calcul arithmétique, par exemple un calcul de PGCD, ce n'est pas gênant parce que les restes \og informatiques\fg{} sont congrus aux restes mathématiques modulo la valeur absolue du
 
 
 Dans les applications de calcul arithmétique, par exemple un calcul de PGCD, ce n'est pas gênant parce que les restes \og informatiques\fg{} sont congrus aux restes mathématiques modulo la valeur absolue du

-diviseur, et qu'il ne s'agit alors que du choix d'un représentant de la classe concernée (addition et multiplication étant compatibles avec la congruence modulo $n$).\\
+diviseur, et qu'il ne s'agit alors que du choix d'un représentant de la classe concernée (addition et multiplication étant compatibles avec la congruence modulo $n$).

 
 Mais il faut quand même savoir que l'on peut obtenir un \og reste\fg{} négatif et prendre ses dispositions le cas échéant...
 
 
 
 Mais il faut quand même savoir que l'on peut obtenir un \og reste\fg{} négatif et prendre ses dispositions le cas échéant...
 
 

-\subsection{Arithmétique modulo $2^n$ dans les ordinateurs}
+\subsection{Arithmétique modulo $2^n$}

 
 

-\subsubsection{Présentation générale}
+ 

 
 

-Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, où $n$ est le nombre de bits utilisés dans la représentation de ces nombres.\\
+Les calculs sur les entiers, dans un ordinateur, se font dans $\Z/2^n\Z$, où $n$ est le nombre de bits utilisés dans la représentation de ces nombres.

 
 
 
 

-Dans la plupart des microprocesseurs, les entiers sont représentés sur 32 bits, les calculs se font donc dans $\Z/2^{32}\Z$ (et qu'ils le soient sur 64 bits ne change rien au problème).\\
+Dans la plupart des microprocesseurs, les entiers sont représentés sur 64 bits, les calculs se font donc dans $\Z/2^{64}\Z$.

 
 
 Disposer d'entiers signés ou d'entiers non signés est uniquement une question de choix du représentant dans les classes d'équivalence, mais
 
 
 Disposer d'entiers signés ou d'entiers non signés est uniquement une question de choix du représentant dans les classes d'équivalence, mais

-la représentation physique est la même.\\
+la représentation physique est la même.

 
 
 
 

-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.\\
+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
 \begin{center}\begin{tabular}{|c|c|c|c|} \hline
 code binaire & & a.s. & a.n.s. \\ \hline
 0000 & interprété par & 0 & 0 \\ \hline


@@ -773,7 +808,7 @@ code binaire & & a.s. & a.n.s. \\ \hline
 \end{tabular}\end{center}\vskip 10pt
 
 
 \end{tabular}\end{center}\vskip 10pt
 
 

-Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., représenté les entiers dans l'ordre croissant de 0000 (-8) à 1111 (7)?\\
+Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., représenté les entiers dans l'ordre croissant de 0000 (-8) à 1111 (7)?

 
 \begin{itemize}
  \item Tout simplement pour des raisons d'efficacité : 0 doit toujours être représenté par le code \og nul\fg{} 0000.
 
 \begin{itemize}
  \item Tout simplement pour des raisons d'efficacité : 0 doit toujours être représenté par le code \og nul\fg{} 0000.


@@ -782,27 +817,23 @@ Pourquoi ce choix ? Pourquoi ne pas avoir, en a.s., représenté les entiers dan
 
 \bigskip
 
 
 \bigskip
 

-Ces principes ont ainsi conduit à placer les codes interprétés comme entiers négatifs après ceux qui représentent les entiers positifs.\\
+Ces principes ont ainsi conduit à placer les codes interprétés comme entiers négatifs après ceux qui représentent les entiers positifs.

 
 
 Par ailleurs, on s'aperçoit que, de cette manière, les codes des entiers
 négatifs commencent tous par 1.
 On parle improprement de \og bit de signe\fg{}\index{bit de signe}: s'il s'agissait d'un véritable bit de signe, le code 1001 devrait être celui de -1, or c'est celui de -7.
 
 
 Par ailleurs, on s'aperçoit que, de cette manière, les codes des entiers
 négatifs commencent tous par 1.
 On parle improprement de \og bit de signe\fg{}\index{bit de signe}: s'il s'agissait d'un véritable bit de signe, le code 1001 devrait être celui de -1, or c'est celui de -7.

-Mais il n'en reste pas moins que tous les entiers négatifs commencent par 1).\\
-
-
-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 n'en reste pas moins que tous les entiers négatifs commencent par 1).

 
 
 
 

-Mais il y a quand même deux instructions assembleur distinctes pour la comparaison signée et pour la comparaison non signée.
+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.

 
 
 
 
 
 

-\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 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.
+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}
 
 
 \begin{Ex}
 


@@ -899,7 +930,7 @@ Opération binaire & Entiers non signés & Entiers signés \\
 
 
 
 
 
 

-\subsection{Théorème de Bézout}
+\section{Théorème de Bézout}

 
 
 On considère deux nombres entiers strictement positifs $a$ et $b$.
 
 
 On considère deux nombres entiers strictement positifs $a$ et $b$.


@@ -945,18 +976,18 @@ Montrez que, si on divise deux entiers naturels $a$ et $b$ par leur pgcd, alors
 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}
 
 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.

 
 
 
 \subsection{Algorithme d'Euclide généralisé}
 
 
 
 
 \subsection{Algorithme d'Euclide généralisé}
 

-\subsubsection{Idée de base.}

 
 

-Pour deux entiers positifs $a$ et $b$, on a vu que l'algorithme d'Euclide s'écrit : $a \et b = b \et r$, où $r$ est le reste dans la division euclidienne de $a$ par $b$.\\

 
 

+Pour deux entiers positifs $a$ et $b$, on a vu que l'algorithme d'Euclide s'écrit : $a \et b = b \et r$, où $r$ est le reste dans la division euclidienne de $a$ par $b$.

 
 

-En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on définit une famille finie $(r_0,r_1,\ldots,r_k,r_{k+1})$ par $r_i=q_{i+1}r_{i+1}+r_{i+2}$ (c'est-à-dire que $r_{i+2}$ est le reste dans la division euclidienne de $r_i$ par $r_{i+1}$).\\
+
+En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on définit une famille finie $(r_0,r_1,\ldots,r_k,r_{k+1})$ par $r_i=q_{i+1}r_{i+1}+r_{i+2}$ (c'est-à-dire que $r_{i+2}$ est le reste dans la division euclidienne de $r_i$ par $r_{i+1}$).

 
 
 \noindent Cette famille...
 
 
 \noindent Cette famille...


@@ -968,14 +999,14 @@ En supposant $a>b$, si on pose $a=r_0$ et $b=r_1$, on définit une famille finie
 
 \bigskip
 
 
 \bigskip
 

-On remarque que $r_{k-1}$ est un multiple de $r_k$, puisque la division euclidienne de $r_{k-1}$ par $r_k$ s'écrit $r_{k-1}=q_kr_k$.\\
+On remarque que $r_{k-1}$ est un multiple de $r_k$, puisque la division euclidienne de $r_{k-1}$ par $r_k$ s'écrit $r_{k-1}=q_kr_k$.

 
 

-Soit $d$ le PGCD de $a$ et de $b$ (évidemment, $d=r_k$), on peut écrire $1 \times r_k-0 \times r_{k-1} = d$ puis $1 \times r_{k-2} - q_{k-1} \times r_{k-1}=d$.\\
+Soit $d$ le PGCD de $a$ et de $b$ (évidemment, $d=r_k$), on peut écrire $1 \times r_k-0 \times r_{k-1} = d$ puis $1 \times r_{k-2} - q_{k-1} \times r_{k-1}=d$.

 
 
 
 

-D'une manière générale, si $(u,v)$ est un couple de Bézout pour $r_{i+1}$ et $r_{i+2}$, soit $u \cdot r_{i+1}+v \cdot r_{i+2}=d$, comme $r_i=q_{i+1}\cdot r_{i+1} + r_{i+2}$, on a $u\cdot r_{i+1}+v \cdot (r_i-q_{i+1}\cdot r_{i+1})=d$, soit $(u-q_{i+1}\cdot v)\cdot r_{i+1}+v \cdot r_i=d$.\\
+D'une manière générale, si $(u,v)$ est un couple de Bézout pour $r_{i+1}$ et $r_{i+2}$, soit $u \cdot r_{i+1}+v \cdot r_{i+2}=d$, comme $r_i=q_{i+1}\cdot r_{i+1} + r_{i+2}$, on a $u\cdot r_{i+1}+v \cdot (r_i-q_{i+1}\cdot r_{i+1})=d$, soit $(u-q_{i+1}\cdot v)\cdot r_{i+1}+v \cdot r_i=d$.

 
 

-\subsubsection{L'algorithme.}
+\subsection{L'algorithme.}

 \index{algorithme!d'Euclide!généralisé}
 Ceci donne l'idée de construire deux familles par les relations :
 \begin{itemize}
 \index{algorithme!d'Euclide!généralisé}
 Ceci donne l'idée de construire deux familles par les relations :
 \begin{itemize}


@@ -983,7 +1014,7 @@ Ceci donne l'idée de construire deux familles par les relations :
 \item $v_0=0$, $v_1=1$, $v_{i+2}=v_i-q_{i+1} \cdot v_{i+1}$.
 \end{itemize}
 
 \item $v_0=0$, $v_1=1$, $v_{i+2}=v_i-q_{i+1} \cdot v_{i+1}$.
 \end{itemize}
 

-C'est ce que l'on appelle algorithme d'Euclide généralisé. On a alors $(u_k,v_k,r_k)=(u,v,d)$, $u$ et $v$ tels que $a \cdot u+b \cdot v=d$.\\
+C'est ce que l'on appelle algorithme d'Euclide généralisé. On a alors $(u_k,v_k,r_k)=(u,v,d)$, $u$ et $v$ tels que $a \cdot u+b \cdot v=d$.

 
 \begin{Pre}
 Pour cela, il suffit de montrer par récurrence que $\qqs i \in
 
 \begin{Pre}
 Pour cela, il suffit de montrer par récurrence que $\qqs i \in


@@ -998,7 +1029,7 @@ v_{i+1})=r_i-q_{i+1}\cdot r_{i+1}=r_{i+2}$.
 \end{Pre}
 
 
 \end{Pre}
 
 

-\subsubsection{Exemple.}
+\subsection{Exemple.}

 
 Illustrons la mise en \oe{}uvre de cet algorithme...
 
 
 Illustrons la mise en \oe{}uvre de cet algorithme...
 


@@ -1017,7 +1048,7 @@ On a bien $3 \times 23-4 \times 17=1$.\psaut
 \begin{Rem}
 Il est possible d'obtenir -1 (ou $-d$ en général) comme résultat, donc $au-bv=-1$, cela dépend de la parité du nombre d'itérations effectuées dans l'algorithme précédent.
 
 \begin{Rem}
 Il est possible d'obtenir -1 (ou $-d$ en général) comme résultat, donc $au-bv=-1$, cela dépend de la parité du nombre d'itérations effectuées dans l'algorithme précédent.
 

-Ce n'est pas un résultat faux, puisqu'alors $bv-au=1$ et qu'on a quand même un couple de Bézout pour $(b,a)$.\\
+Ce n'est pas un résultat faux, puisqu'alors $bv-au=1$ et qu'on a quand même un couple de Bézout pour $(b,a)$.

 
 S'il est nécessaire d'obtenir un couple $(u,v)$ tel que $au-bv=1$
 et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un couple $(u',v')$ tel que $bv'-au'=1$, il suffit de prendre $u=b-u'$ et $v=a-v'$ et, dans ces conditions $au-bv=a(b-u')-b(a-v')= ab -au' -ab +bv'=bv'-au'=1$. 
 
 S'il est nécessaire d'obtenir un couple $(u,v)$ tel que $au-bv=1$
 et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un couple $(u',v')$ tel que $bv'-au'=1$, il suffit de prendre $u=b-u'$ et $v=a-v'$ et, dans ces conditions $au-bv=a(b-u')-b(a-v')= ab -au' -ab +bv'=bv'-au'=1$. 


@@ -1027,9 +1058,26 @@ et où $a$ et $b$ figurent dans cet ordre, et que l'algorithme a fourni un coupl
 Exprimer $pgcd(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602.
 \end{Exo}
 
 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
 \centerline{\x{Fin du Chapitre}}
\ No newline at end of file