Médaille
N°1 pour apprendre & réviser du collège au lycée.
Rechercher les coefficients de Bézout - TI
Découvrez, sur SchoolMouv, des milliers de contenus pédagogiques, du CP à la Terminale, rédigés par des enseignants de l’Éducation nationale.
Les élèves de troisième, de première ou de terminale bénéficient, en plus, de contenus spécifiques pour réviser efficacement leur brevet des collèges, leur bac de français ou leur baccalauréat édition 2023.
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 »