1. Regarde
  2. Manipule
  3. Écris
  4. Correction

Calculer un PGCD par l'algorithme d'Euclide

pgcd(a, b) = pgcd(b, r). Je descends jusqu'à un reste nul.

la méthode

  1. 1Diviser a par b, garder le reste r.
  2. 2Recommencer avec (b, r).
  3. 3Le dernier reste non nul est le PGCD.

le piège

Annoncer le dernier reste, qui vaut 0. Le PGCD est le DERNIER RESTE NON NUL de la descente.