Algorithme : Rechercher les coefficients de Bézout - TI

TI

L’algorithme d’Euclide, partant de deux entiers $a=r_0$ et $b=r_1$ avec $r_0>r_1$, détermine d’abord un reste $r_2$, puis, partant de $r_1$ et de $r_2$, un autre reste $r_3$ et ainsi de suite, jusqu’au dernier reste non nul $r_n$ qui est le PGCD de $a$ et $b$.

Remonter à l’envers l’algorithme d’Euclide permet de construire les coefficients $a_n$ et $b_n$ dits de Bézout, tels que $r_n=a_n \times a+b_n \times b$.

Le programme prend deux entiers $a=r_0$ et $b=r_1$ et calcule les restes successifs $r_2$, …, $r_n$.
À chaque reste $r_k$ il considère des coefficients $a_k$ et $b_k$ tels que $r_k=a_k\times a+b_k \times b$.
Comme $r_0=a$, on a $a_0=1$ et $b_0=0$.
De même, vu que $r_1=b$, on a $a_1=0$ et $b_1=1$.

Ensuite, si l’on connaît $(a_k,b_k )$ et $(a_{k+1},b_{k+1})$ on peut en déduire $(a_{k+2},b_{k+2})$.
Posons $m_k$ le quotient de $r_k$ par $r_{k+1}$ alors :

• $r_k=m_k× r_{k+1}+r_{k+2}$ (principe de la division euclidienne de $r_k$ par $r_{k+1}$) ;
• $r_{k+2}=r_{k+1}-r_{k+1}\times r_{k+1}+1$ (on a isolé $r_{k+2}$) ;
• donc $(a_{k+2},b_{k+2}) =(a_k-m_k\times a_{k+1},b_k-m_k\times b_{k+1})$

$a>b$ deux entiers entrés par l’utilisateur
$r$ un entier calculé par le programme
$c$ et $d$ les coefficients correspondant à $(a_k,b_k)$ dans l’explication ci-dessus
$e$ et $f$ les coefficients correspondant à $(a_{k+1},b_{k+1})$ dans l’explication ci-dessus
$g$ et $h$ les coefficients correspondant à $(a_{k+2},b_{k+2})$ dans l’explication ci-dessus
$m$ le rapport correspondant à $m_k$ ci-dessus

|demander $a$ et $b$
|$r=$ le reste de la division euclidienne de $a$ par $b$
|$(c,d)=(1,0)$ et $(e,f)=(0,1)$
|tant que $r\not=0$
|$m$ prend la valeur du quotient euclidien de $(a\div b)$
|$r$ prend la valeur de $a-m\times b$
|$g$ prend la valeur de $c-m\times e$
|$h$ prend la valeur de $d-m\times f$
|$a$ prend la valeur de $b$, $b$ prend la valeur de $r$
|$c$ prend la valeur de $e$, $d$ prend la valeur de $f$
|$e$ prend la valeur de $g$, $f$ prend la valeur de $h$
|fin du tant que
|afficher $a$ (le PGCD)
|afficher $(c,d)$

• prgm►▼entrer « Prompt » alphamath « A » alpha .  « : »
  prgm►▼entrer « Prompt » alphaapps « B » entrer
• alphamath « A »  - 
  math► « NUM » ▼▼entrer « ent( »
  alphamath « A » ÷ alphaapps « B » )
   ×  alphaapps « B » sto ➔ «  ➔ » alpha$\times$ « R » entrer
•  1  sto ➔ «  ➔ » alphaprgm « C » alpha .  « : »
   0  sto ➔ «  ➔ » alpha$x^{-1}$ « D » alpha .  « : »
   0  sto ➔ «  ➔ » alphasin « E » alpha .  « : »
   1  sto ➔ «  ➔ » alphacos « F » entrer
• prgm▼▼▼▼ entrer « While » alpha$\times$ « R »
  2ndemath▼ « ≠ » 0 entrer
• math► « NUM » ▼▼entrer « ent( »
  alphamath « A » ÷ alphaapps « B » )
  sto ➔ «  ➔ » alpha$\div$ « M » entrer
• alphamath « A »  -  alpha$\div$ « M »  ×  alphaapps « B »
  sto ➔ «  ➔ » alpha$\times$ « R » entrer
  alphaprgm « C »  -  alpha$\div$ « M »  ×  alphasin « E »
  sto ➔ «  ➔ » alpha^ « G »
  alpha$x^{-1}$ « D »  -  alpha$\div$ « M »  ×  alphacos « F »
  sto ➔ «  ➔ » alpha ∧  « H »
• alphaapps « B » sto ➔ «  ➔ » alphamath « A » alpha .  « : »
  alpha$\times$ « R » sto ➔ «  ➔ » alphaapps « B » entrer
  alphasin « E » sto ➔ «  ➔ » alphaprgm « C » alpha .  « : »
  alphacos « F » sto ➔ «  ➔ » alpha$x^{-1}$ « D » entrer
  alpha^ « G » sto ➔ «  ➔ » alphasin « E » alpha .  « : »
  alpha ∧  « H » sto ➔ «  ➔ » alphacos « F » entrer
• prgm▼▼▼▼▼▼ « End » entrer entrer
• prgm►▼▼ « Disp » entrer alphamath « A » entrer
  prgm►▼▼ « Disp » entrer alphaprgm « C » entrer
  prgm►▼▼ « Disp » entrer alpha$x^{-1}$ « D »