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

Type de calculatrice

TI

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 TI

Algorithme recherche coefficients de Bezout-Ti-mathématiques-terminale S-schoolmouv

  • prgmentrer « Prompt » alphamath « A » alpha .  « : »
    prgmentrer « 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 »