-\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.\\
-
-
-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}
-\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.
\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}
-\begin{Exo}
+\begin{Ex}
Tout nombre non nul est au moins divisible par 1 et par lui-même ($a=a\times 1+0$).
-\end{Exo}
+\end{Ex}
-\begin{Exo}
+\begin{Ex}
0 est divisible par tout nombre entier non nul $(0 = 0 \times b + 0 )$.
-\end{Exo}
+\end{Ex}
\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}
-
-Réponses : (-7,4) et (-11,11).
-
\end{Exo}
-\begin{Exo}[Divisibilité dans $\N$]
+\begin{Exo}
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.
\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$.
-
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}$.
-\end{Notation}
+\end{Def}
-\begin{Rem}
En informatique, on utilise couramment les bases 2, 8 et 16.
-\end{Rem}
-\subsubsection{Obtention de cette représentation}
+
+\subsection{Obtention de cette représentation}
L'algorithme pour obtenir la représentation en base $b$ d'un entier est :
\end{enumerate}
-\subsubsection{Algorithme de Hörner}
+% \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 :\\
+% 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})$
-$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})$
-\subsubsection{Exercices}
\begin{Exo}[Numération, changements de base]
\begin{enumerate}
\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 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}
-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}
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{Exo}
+\begin{Ex}
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{Exo}
-
+\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.
+
+
\begin{Th}
L'ensemble-quotient (ensemble des classes d'équivalence) de la relation de congruence modulo $n$ est un ensemble fini.
\end{Th}
\end{Notation}
-\begin{Exo}
+\begin{Ex}
$\Z/3\Z =\{ \dot 0,\dot 1,\dot 2\}$.
-\end{Exo}
+\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}
\begin{Proof}
-En effet, on suppose que :
+En effet, on suppose que:
\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 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}
-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}
-\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}
\end{Def}
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
\begin{Rem}
\begin{Exo}
- Calculez :
+Résolvez modulo 18 les équations suivantes :
+
\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}
-\noindent Réponses : 5 et 630.
+%\noindent Réponses : \{8,17\}, \{ \} et \{15\}.
\begin{Exo}[Systèmes de congruences]
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}
\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}
-\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$.
-
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)
-\bigskip
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\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
-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...
-\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
-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.
\subsubsection{Illustration dans le cas de 4 bits.}
\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.
\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.
-Mais il n'en reste pas moins que tous les entiers négatifs commencent par 1).\\
+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.\\
+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.\\
+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).
-\begin{Exo}
+\begin{Ex}
Premiers résultats, corrects :
1011 & 11 & (-5) \\
\end{tabular}
\end{center}
-\end{Exo}
+\end{Ex}
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
-\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$.
\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...
\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}
\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
\end{Pre}
-\subsubsection{Exemple.}
+\subsection{Exemple.}
Illustrons la mise en \oe{}uvre de cet algorithme...
-\begin{Exo}
+\begin{Ex}
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{Exo}
+\end{Ex}
\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$.
Exprimer $pgcd(1330,602)$ comme combinaison à coefficients entiers des nombres 1330 et 602.
\end{Exo}
-\noindent Réponse $14 = 1330*(-19)+602*42$.
+%\noindent Réponse $14 = 1330*(-19)+602*42$.
