Algorithme : Rechercher les coefficients de Bézout - Casio

Casio

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)$

• SHIFTVARSF4 « ? » ➔ Alpha$X,\theta,T$ « A »
  SHIFTVARSF6 « ▷ » F5 « : »
  SHIFTVARSF4 « ? » ➔ Alphalog « B » EXE « ↵ »
• Alpha$X,\theta,T$ « A »  - 
  OPTNF6 « ▷ » F4 « NUM » F2 « Int »
  ( Alpha$X,\theta,T$ « A » ÷ Alphalog « B » )
   ×  Alphalog « B » ➔ Alpha6 « R » EXE « ↵ »
• 1 ➔ Alphaln « C » SHIFTVARSF6 « ▷ » F5 « : »
  0 ➔ Alphasin « D » SHIFTVARSF6 « ▷ » F5 « : »
  0 ➔ Alphacos « E » SHIFTVARSF6 « ▷ » F5 « : »
  1 ➔ Alphatan « F » EXE « ↵ »
• SHIFTVARSF1 « COM » F6 « ▷ » F6 « ▷ » F1 « While » Alpha6 « R » SHIFTVARSF6 « ▷ » F3 « REL » F2 « ≠ » 0 EXE « ↵ »
• OPTNF6 « ▷ » F4 « NUM » F2 « Int »
  ( Alpha$X,\theta,T$ « A » ÷ Alphalog « B » )
   ×  Alphalog « B » ➔ Alpha7 « M » EXE « ↵ »
• Alpha$X,\theta,T$ « A »  -  Alpha7 « M »
   ×  Alphalog « B » ➔ Alpha6 « R » EXE « ↵ »
  Alphaln « C »  -  Alpha7 « M »
   ×  Alphacos « E » ➔ Alphaa+b/c « G »EXE « ↵ »
  Alphasin « D »  -  Alpha7 « M »
   ×  Alphatan « F » ➔ AlphaF↔D « H »EXE « ↵ »
• Alphalog « B » ➔ Alpha$X,\theta,T$ « A »
  SHIFTVARSF6 « ▷ » F5 « : »
  Alpha6 « R » ➔ Alphalog « B » EXE « ↵ »
  Alphacos « E » ➔ Alphaln « C »
  SHIFTVARSF6 « ▷ » F5 « : »
  Alphatan « F » ➔ Alphasin « D » EXE « ↵ »
  Alphaa+b/c « G » ➔ Alphacos « E »
  SHIFTVARSF6 « ▷ » F5 « : »
  AlphaF↔D « H » ➔ Alphatan « F » EXE « ↵ »
• SHIFTVARSF1 « COM » F6 « ▷ » F6 « ▷ » F2 « WhileEnd » EXE « ↵ »
• Alpha$X,\theta,T$ « A » SHIFTVARSF5 « ◄ »
  Alphaln « C » SHIFTVARSF5 « ◄ »
  Alphasin « D »