Algorithme d'Euclide étendu
dans Arithmétique
Bonjour.
Je cherche à comprendre la méthode employée ici pour déterminer les coefficients de Bézout à l'aide de produit matriciel. En particulier le sens a(div)b, qui n'est pas défini dans le livre.
Merci
Je cherche à comprendre la méthode employée ici pour déterminer les coefficients de Bézout à l'aide de produit matriciel. En particulier le sens a(div)b, qui n'est pas défini dans le livre.
Merci
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
-- Schnoebelen, Philippe
a priori, $a \, div \, b$ désigne le quotient entier dans la division euclidienne de $a$ par $b$. [edit : grillé par nicolas.patrois ]
Voici l'algorithme d'Euclide étendu "version suite", ça t'aidera peut-être à mieux comprendre :
Soient $a$ et $b$ deux entiers naturels non nuls.
On écrit l'algorithme d'Euclide
$a = b q_2 + r_2, \, \, 0 \, < \, r_2 \, < \, b$
$b = r_2 q_3 + r_3, \, \, 0 \, < \, r_3 \, < \, r_2$
$...$
$r_i = r_{i+1} q_{i+2} + r_{i+2}, \, \, 0 \, < \, r_{i+2} \, < \, r_{i+1}$
$...$
$r_{n-2} = r_{n-1} q_n + r_n, \, \, 0 \, < \, r_n \, < \, r_{n-1}$
$r_{n-1} = r_n q_{n+1} + 0$.
On constate que :
* $r_2 = a - b q_2$
* $r_3 = b - r_2 q_3$
* pour tout entier $i$ entre $2$ et $n-2$, on a : $r_{i+2} = r_i - r_{i+1} q_{i+2}$
En posant $a=r_0$ et $b=r_1$, on a donc :
* pour tout entier $i$ entre $0$ et $n-2$, on a : $r_{i+2} = r_i - r_{i+1} q_{i+2}$.
De plus, $a = 1 \times a + 0 \times b$ et $b=0 \times a + 1 \times b$, on montre donc facilement par récurrence que :
* pour tout entier $i$ entre 0 et $n$, il existe des entiers (relatifs) $u_i$ et $v_i$ tels que $r_1 = a \times u_i + b \times v_i$.
* les suites $(u_i)_i$ et $(v_i)_i$ sont définies par récurrence de la même manière que la suite $(r_i)_i$ :
pour tout entier $i$ entre $0$ et $n-2$, $u_{i+2}=u_i - u_{i+1} q_{i+2}$ et $v_{i+2}=v_i - v_{i+1} q_{i+2}$.
Ci-joint une présentation "pratique" de l'algorithme sous forme de tableau (avec les exemples de ton papier), avec les commentaires pour que tu puisses à ton tour le programmer sur un tableur (ça permet de bien comprendre le truc, je pense).
Au passage, il y a une erreur dans ton document : $-151 \times 522 + 174 \times 453 = 0$ et non $3$. Le couple de Bézout trouvé par l'algorithme est $(46,-53)$ : $46 \times 522 + (-53) \times 453 = 3$.
Les avantages de cette méthode sont:
- définir un calcul du pgcd indépendamment du calcul des coefficients de Bézout
- déterminer directement par normalisation le premier élément de l'ensemble solution des coefficients de Bézout
- relier les coefficients de Bézout aux paramètres (a,b,c) sous certaines conditions
- un calcul plus performants pour le pgcd et les coefficients de Bézout