PGCD(a,b)   [répertoire]

• problème : pour (a, b) donnés, trouver le Plus Grand Diviseur Commun à a et b : PGCD(a,b)
  (utile pour pour simplifier la fraction a/b)
  remarques : les diviseurs communs à a et b divisent également r = a − b q
    Tous les restes sont divisibles par le PGCD(a,b).
    Les restes forment une suite décroissante : l'avant-dernier reste non nul est le PGCD
  Première colonne : résultats de la division Euclidienne : a = b q + r   (avec r < b)
  Deuxième colonne : reste de la division précédente

  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)
  r0 = r1 q2 + r2	⇒ r2 = r0 − r1 q2
  r1 = r2 q3 + r3	⇒ r3 = r1 − r2 q3
  . . .	⇒ . . .
  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 : c'est le PGCD(a,b).

Calculatrice de PGCD : PGCD_Bezout.html
 
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