Rechercher les coefficients de Bézout - TI

L’algorithme d’Euclide, partant de deux entiers $a=r$0a=r0​ et $b=r$1 avec $r$0>r1, détermine d’abord un reste $r$2r2​, puis, partant de $r$1 et de $r$2r2​, 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$nan​ et $b$n dits de Bézout, tels que $r$n=an \times a+b_n \times b.

Le programme prend deux entiers $a=r$0a=r0​ et $b=r$1 et calcule les restes successifs $r$2r2​, …, $r$n.
À chaque reste $r$krk​ il considère des coefficients $a$k et $b$kbk​ tels que $r$k=ak\times a+bk \times b.
Comme $r$0=ar0​=a, on a $a$0=1 et $b$0=0b0​=0.
De même, vu que $r$1=b, on a $a$1=0a1​=0 et $b$1=1.

Ensuite, si l’on connaît $(a$k,bk ) et $(a${k+1},b{k+1}) on peut en déduire $(a${k+2},b{k+2}).
Posons $m$kmk​ le quotient de $r$k par $r_{k+1}$ alors :

• $r$k=mk× r{k+1}+r{k+2} (principe de la division euclidienne de $r$krk​ 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}) =(ak-mk\times a{k+1},bk-mk\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,bk) 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 »