\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:
\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é.
+Ceci se déduit du fait que $\N$ est un ensemble complètement ordonné.
\begin{Exo}
\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}
\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{Exo}
\begin{Exo}
-Poursuivre le raisonnement pour $S_3(n)$. Cette méthode permet-elle de calculer $S_k(n), \forall k,n$ ?
+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 $\forall n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
+Montrer que pour tout $n \in \N$, 7 divise $3^{2n+1}+2^{n+2}$.
\end{Exo}
\begin{Exo}
-Soit $(u_n)_{n \in \N}$ une suite réelle telle que $\forall n \in \N$,
+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 $\forall n \in \N, u_n = \alpha 3^n + \beta 2^n$.
+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}
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}
-
\begin{Exo}
Soit $m = 2^3 * 5 * 7^2 * 13^3$. Combien le nombre $m$ a-t-il de diviseurs naturels ?
\end{Exo}
\end{Def}
-\begin{Ex}
+\begin{Exo}
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.
\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$.
-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}
\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.
+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 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.
-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]
-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.
+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.
+
+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}
-\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}
\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 $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.
-\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$.
-\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 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$, 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.
-
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}
}\}}
-
-
-
-\begin{Ex}
-Comme $48=2^43$ et que $56=2^37$, on voit aisément que $48\et 56=2^3$.
-\end{Ex}
-
\begin{Exo}
- Calculez $102 \ou 138$.
+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 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$.
+\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$.
+\end{enumerate}
+\end{enumerate}
\end{Exo}
-\noindent Réponse : 2346.
+% \begin{Exo}
+% Comme $48=2^43$ et que $56=2^37$, on voit aisément que $48\et 56=2^3$.
+% \end{Exo}
+
+% \begin{Exo}
+% Calculez $102 \ou 138$.
+% \end{Exo}
+
+% \noindent Réponse : 2346.
% \begin{Th}
% $\Net$ est un treillis pour la divisibilité.
-\subsection{Entiers relatifs}
+\section{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.\\
\end{Def}
-\begin{Ex}
+\begin{Exo}
Tout nombre non nul est au moins divisible par 1 et par lui-même ($a=a\times 1+0$).
-\end{Ex}
+\end{Exo}
-\begin{Ex}
+\begin{Exo}
0 est divisible par tout nombre entier non nul $(0 = 0 \times b + 0 )$.
-\end{Ex}
+\end{Exo}
\begin{Exo}
La classe d'équivalence d'un entier donné comprend donc cet entier et tous ceux qui ont le même reste que lui dans la division euclidienne par $n$.
-\begin{Ex}
+\begin{Exo}
Si $n = 3$, il y a trois classes distinctes :
\begin{itemize}
\item $\dot 0=\{\ldots,-6,-3,0,3,6,9,\ldots\}$,
\end{itemize}
On retrouve ensuite les mêmes éléments : $\dot 3=\dot 0$, etc...
-\end{Ex}
+\end{Exo}
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.
\end{Notation}
-\begin{Ex}
+\begin{Exo}
$\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.
-\end{Ex}
+\end{Exo}
\begin{Th}
\end{Def}
-\begin{Ex}
+\begin{Exo}
C'est ainsi qu'on obtient les tables d'opérations suivantes dans $\Z/4\Z$ :\\
\dot 3 & \dot 0 & \dot 3 & \dot 2 & \dot 1 \\ \hline \end{array}$
\end{center}
\vskip 10pt
-\end{Ex}
+\end{Exo}
\begin{Rem}
\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).
-\begin{Ex}
+\begin{Exo}
Premiers résultats, corrects :
1011 & 11 & (-5) \\
\end{tabular}
\end{center}
-\end{Ex}
+\end{Exo}
-\begin{Ex}
+\begin{Exo}
Un résultat correct en arithmétique non \break signée, et négatif en arithmétique signée, mais correct modulo 16 (-6 et 10 sont dans la même classe, mais cette classe est représentée par 10 en a.n.s. et par -6 en a.s.) :
\begin{center}
\begin{tabular}{r | r | r}
1010 & 10 & (-6) \\
\end{tabular}
\end{center}
-\end{Ex}
+\end{Exo}
-\begin{Ex}
+\begin{Exo}
Un dépassement de capacité dans les deux cas, mais le résultat est correct modulo 16 : les classes de 21, de -11 et de 5 sont les mêmes :
\begin{center}
\begin{tabular}{r | r | r}
\end{tabular}
\end{center}
Le résultat (correct modulo 16) est disponible dans tous les cas, les \og dépassement de capacité\fg{} et \og résultat négatif\fg{} sont signalés par le positionnement d'un bit dans un registre spécial.
-\end{Ex}
+\end{Exo}
-\begin{Ex}
+\begin{Exo}
Un résultat correct en a.n.s., résultat négatif en a.s., mais correct modulo 16 :
\begin{center}
\begin{tabular}{r | r | r}
\underline{$\times$ 2} \\ 1010 & 10 & (-6) \\
\end{tabular}
\end{center}
-\end{Ex}
+\end{Exo}
-\begin{Ex}
+\begin{Exo}
Dépassement de capacité dans les deux cas, résultat négatif en a.s., mais résultat correct modulo 16, compte tenu du choix des représentants dans les deux arithmétiques:
\begin{center}
\begin{tabular}{r | r | r}
(1)1110 & 14 & (-2) \\
\end{tabular}
\end{center}
-\end{Ex}
+\end{Exo}
-\begin{Ex}
+\begin{Exo}
Dépassement de capacité dans les deux cas, résultat correct en a.s., correct modulo 16 en a.n.s.
\begin{center}
\begin{tabular}{r | r | r}
(-2)} \\ (1011)0110 & 6 & 6 \\
\end{tabular}
\end{center}
-\end{Ex}
+\end{Exo}
Illustrons la mise en \oe{}uvre de cet algorithme...
-\begin{Ex}
+\begin{Exo}
Soit à obtenir un couple de Bézout pour (23,17) :\vskip 10pt
\begin{center}\begin{tabular}{c c c c}
(23,1,0) & (17,0,1) & $\longrightarrow$ & $q=1$ \\
(1,3,-4) & (0,-17,23) & $\longrightarrow$ & FIN
\end{tabular}\end{center}\vskip 10pt
On a bien $3 \times 23-4 \times 17=1$.\psaut
-\end{Ex}
+\end{Exo}
\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.
