L'algorithme d'Euclide pour déterminer le pgcd de deux entiers

Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

Définitions et théorèmes

L'algorithme d'Euclide calcule le PGCD de deux entiers naturels non nuls a\ge b par divisions euclidiennes successives. Il repose sur la propriété suivante.

Propriété (clé de l'algorithme). Si a=bq+r est la division euclidienne de a par b, alors \mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,r).

Démonstration. Tout diviseur commun de a et b divise r=a-bq (combinaison linéaire), donc divise b et r. Réciproquement, tout diviseur commun de b et r divise a=bq+r, donc divise a et b. Les deux couples (a,b) et (b,r) ont exactement les mêmes diviseurs communs, donc le même plus grand : leurs PGCD sont égaux.

Formules

  • a=bq+r avec 0\le r<b, puis on recommence avec (b,r).
  • \mathrm{PGCD}(a,0)=a (cas d'arrêt).
  • Le PGCD est le dernier reste non nul.

Méthodes type bac

  • Dérouler l'algorithme : écrire chaque division a=bq+r, recopier (b,r) comme nouvelle ligne, s'arrêter au reste 0. Le PGCD est le reste précédent.
  • Rendre une fraction irréductible : calculer d=\mathrm{PGCD}(a,b) puis simplifier \dfrac{a}{b}=\dfrac{a/d}{b/d}.
  • Tester si deux entiers sont premiers entre eux : l'algorithme s'arrête sur un dernier reste non nul égal à 1.
  • Version étendue (Euclide remonté) : une fois les divisions écrites, on remonte les égalités en exprimant chaque reste comme combinaison de a et b. On obtient ainsi les coefficients de Bézout u,v tels que au+bv=\mathrm{PGCD}(a,b).
  • Estimer le nombre d'étapes : l'algorithme converge très vite (en un nombre d'étapes logarithmique), ce qui le rend praticable même pour de très grands entiers.

Pièges

  • Confondre quotient et reste à chaque étape : seul le reste est reporté à la ligne suivante.
  • S'arrêter au reste 0 et croire que le PGCD vaut 0 : c'est le dernier reste non nul qu'il faut lire.
  • Oublier une étape : la suite des restes doit être strictement décroissante jusqu'à 0.
  • Recopier le quotient au lieu du reste : l'erreur classique qui fausse tout le calcul.

Exemple détaillé

Calcul de \mathrm{PGCD}(4539,1958) : 4539=1958\times2+623, puis 1958=623\times3+89, puis 623=89\times7+0. Le dernier reste non nul est 89, donc \mathrm{PGCD}(4539,1958)=89. La suite des restes 623>89>0 est bien strictement décroissante.

Pour l'épreuve

L'algorithme d'Euclide est l'outil de calcul le plus efficace pour un PGCD, surtout avec de grands nombres où la décomposition en facteurs premiers est impraticable. Sa version étendue (chapitre Bézout) donne en prime les coefficients u et v de l'identité de Bézout. Présente proprement la suite des divisions, une par ligne, et conclus toujours par « le dernier reste non nul est ... ». Sache aussi justifier l'algorithme par l'égalité \mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,r) : c'est une question de cours fréquente, dont la démonstration repose sur l'égalité des ensembles de diviseurs communs.