a x + b y = PGCD(a,b)

• problème : pour ( a , b ) donnés, calculer ( x , y ) tels que a x + b y = PGCD(a,b)
  Première colonne : résultats de la division Euclidienne : a = b q + r
  Troisième colonne : on exprime le reste sous la forme : r = a x + b y
  Les restes forment une suite décroissante
  Tous les restes sont divisibles par le PGCD(a,b).

  a = b q0 + r0	=> r0	= a − b q0   (les diviseurs de a et b divisent aussi r0 . . .)
  b = r0 q1 + r1	=> r1	= b − r0 q1   (les diviseurs de b et r0 divisent aussi r1 . . .) = b − ( a − b q0 ) q1 = − a q1 + b ( 1 + q0 q1 )
  r0 = r1 q2 + r2	=> r2	= r0 − r1 q2 = ( a − b q0 ) − ( − a q1 + b ( 1 + q0 q1 )) q2 = a ( 1 + q1 ) − b ( q0 + q2 + q0 q1 q2 )
  r1 = r2 q3 + r3	=> r3	= r1 − r2 q3 = ( − a q1 + b ( 1 + q0 q1 ) ) − ( a ( 1 + q1 ) − b ( q0 + q2 + q0 q1 q2 ) ) q3 = − a ( 1 + 2 q1 ) + b ( 1 + q0 q1 + q0 q3 + q2 q3 + q0 q1 q2 q3 )
  r2 = r3 q4 + r4	=> r4	= r2 − r3 q4 = . . .
  rn−2 = rn−1 qn + rn	=> rn	= rn−2 − rn−1 qn
  rn−1 = rn qn+1 + 0		rn−1 est multiple de rn . . . ⇒ a et b sont multiples de rn

  Quand un reste est nul, c'est que le reste précédent était le PGCD(a,b) :
  r_n est le plus petit reste non nul divisible par le PGCD(a,b).

Méthode itérative : algorithme du PGCD

• Amorçage de l'itération (r₀, r₁)
  r₀ = a
  r₁ = b
  remarque : si a < b : ils vont être échangés au premier passage
• répéter les instructions suivantes dans une boucle
  q = Partie_Entière( r₀ / r₁ )
  r = r₀ − q r₁
  si r = 0 : terminé : r1 est le pgcd(a,b)
  r₀ = r₁
  r₁ = r

retour au menu :   Arithmétique   Math