Médaille
N°1 pour apprendre & réviser du collège au lycée.
Marianne

Conforme au programme
officiel 2018 - 2019

Rechercher les coefficients de Bézout - TI
Algorithme

Type de calculatrice

TI

Prérequis

L’algorithme d’Euclide, partant de deux entiers a=r0a=r0 et b=r1b=r1 avec r0>r1r0>r1, détermine d’abord un reste r2r2, puis, partant de r1r1 et de r2r2, un autre reste r3r3 et ainsi de suite, jusqu’au dernier reste non nul rnr_n qui est le PGCD de aa et bb.

Remonter à l’envers l’algorithme d’Euclide permet de construire les coefficients anan et bnbn dits de Bézout, tels que rn=an×a+bn×brn=an \times a+b_n \times b.

Description

Programme

Le programme prend deux entiers a=r0a=r0 et b=r1b=r1 et calcule les restes successifs r2r2, …, rnrn.
À chaque reste rkrk il considère des coefficients akak et bkbk tels que rk=ak×a+bk×brk=ak\times a+bk \times b.
Comme r0=ar0=a, on a a0=1a0=1 et b0=0b0=0.
De même, vu que r1=br
1=b, on a a1=0a1=0 et b1=1b1=1.

Ensuite, si l’on connaît (ak,bk)(ak,bk ) et (ak+1,bk+1)(a{k+1},b{k+1}) on peut en déduire (ak+2,bk+2)(a{k+2},b{k+2}).
Posons mkmk le quotient de rkrk par rk+1r_{k+1} alors :

  • rk=mk×rk+1+rk+2rk=mk× r{k+1}+r{k+2} (principe de la division euclidienne de rkrk par rk+1r{k+1}) ;
  • rk+2=rk+1rk+1×rk+1+1r{k+2}=r{k+1}-r{k+1}\times r{k+1}+1 (on a isolé rk+2r_{k+2}) ;
  • donc (ak+2,bk+2)=(akmk×ak+1,bkmk×bk+1)(a{k+2},b{k+2}) =(ak-mk\times a{k+1},bk-mk\times b{k+1})

Variables

a>ba>b deux entiers entrés par l’utilisateur
rr un entier calculé par le programme
cc et dd les coefficients correspondant à (ak,bk)(ak,bk) dans l’explication ci-dessus
ee et ff les coefficients correspondant à (ak+1,bk+1)(a{k+1},b{k+1}) dans l’explication ci-dessus
gg et hh les coefficients correspondant à (ak+2,bk+2)(a{k+2},b{k+2}) dans l’explication ci-dessus
mm le rapport correspondant à mkm_k ci-dessus

Algorithme

|demander aa et bb
|r=r= le reste de la division euclidienne de aa par bb
|(c,d)=(1,0)(c,d)=(1,0) et (e,f)=(0,1)(e,f)=(0,1)
|tant que r0r\not=0
|mm prend la valeur du quotient euclidien de (a÷b)(a\div b)
|rr prend la valeur de am×ba-m\times b
|gg prend la valeur de cm×ec-m\times e
|hh prend la valeur de dm×fd-m\times f
|aa prend la valeur de bb, bb prend la valeur de rr
|cc prend la valeur de ee, dd prend la valeur de ff
|ee prend la valeur de gg, ff prend la valeur de hh
|fin du tant que
|afficher aa (le PGCD)
|afficher (c,d)(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 ➔ «  ➔ » alphax1x^{-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 »
    alphax1x^{-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 ➔ «  ➔ » alphax1x^{-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 alphax1x^{-1} « D »