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 - Casio
Algorithme

Type de calculatrice

Casio

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 Casio

Algorithme coefficients de Bezout-schoolmouv-terminale-s

  • SHIFTVARSF4 « ? » AlphaX,θ,TX,\theta,T « A »
    SHIFTVARSF6 « ▷ » F5 « : »
    SHIFTVARSF4 « ? » Alphalog « B » EXE « ↵ »
  • AlphaX,θ,TX,\theta,T « A »  - 
    OPTNF6 « ▷ » F4 « NUM » F2 « Int »
    ( AlphaX,θ,TX,\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 »
    ( AlphaX,θ,TX,\theta,T « A » ÷ Alphalog « B » )
     ×  Alphalog « B » Alpha7 « M » EXE « ↵ »
  • AlphaX,θ,TX,\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 » AlphaX,θ,TX,\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 « ↵ »
  • AlphaX,θ,TX,\theta,T « A » SHIFTVARSF5 « ◄ »
    Alphaln « C » SHIFTVARSF5 « ◄ »
    Alphasin « D »