Médaille
N°1 pour apprendre & réviser du collège au lycée.
Rechercher les coefficients de Bézout - Casio
Algorithme

Type de calculatrice

Casio

Prérequis

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

Description

Programme

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

Variables

$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

Algorithme

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

Programme Casio

Algorithme coefficients de Bezout-schoolmouv-terminale-s

  • 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 »