algorithme d'Euclide

Imaginez 252 objets et 105 objets à répartir en groupes identiques, aussi grands que possible, sans rien laisser. L’algorithme d’Euclide évite de tester toutes les tailles de groupe. Il divise le plus grand nombre par le plus petit, conserve le reste, puis recommence avec le diviseur et ce reste. Quand le reste atteint 0, le dernier reste non nul donne la taille recherchée : ici, 21.

L’algorithme d’Euclide est une procédure qui calcule le plus grand commun diviseur, ou PGCD, de deux entiers. Pour deux entiers non tous deux nuls, on peut travailler avec leurs valeurs absolues. Si l’un vaut 0, le PGCD est l’autre valeur absolue. Sinon, on note a le plus grand entier et b le plus petit. La division euclidienne de a par b donne un quotient entier q et un reste r compris entre 0 inclus et b exclu.

L’identité utilisée à chaque étape est $a=bq+ra=bq+r$, et les diviseurs communs de a et b sont les mêmes que ceux de b et r. On remplace donc la paire (a, b) par (b, r) jusqu’à obtenir un reste nul. Les restes positifs diminuent strictement : avec des entiers, la procédure s’arrête toujours. Le dernier reste non nul est le PGCD. Il vaut 1 exactement lorsque les deux entiers sont premiers entre eux.

L’anthyphérèse, dont le nom signifie « enlever tour à tour », exprime le même principe par soustractions répétées. Euclide la présente dans les Éléments, au livre VII pour les nombres et au livre X pour les grandeurs géométriques. La version étendue suit aussi les quotients afin d’obtenir des coefficients de Bézout. Le même schéma s’étend aux anneaux euclidiens.

Soient a et b deux entiers positifs, avec a supérieur ou égal à b. Effectuez la division euclidienne de a par b, puis remplacez a par b et b par le reste obtenu. Répétez tant que ce reste n’est pas nul. Comme chaque reste positif est strictement inférieur au précédent, l’opération s’arrête ; le dernier reste non nul est le PGCD des deux entiers de départ.

Dans sa forme arithmétique, la méthode demande deux entiers qui ne sont pas tous deux nuls. Si l’un est négatif, son signe n’influe pas sur les diviseurs communs : on utilise sa valeur absolue. À chaque étape, le diviseur doit être non nul et le reste doit satisfaire la condition de la division euclidienne : il est positif ou nul et strictement inférieur au diviseur. Le résultat obtenu est un entier positif.

Le couple (0, 0) constitue un contre-cas : tout entier positif divise simultanément 0 et 0, donc aucun n’est le plus grand. L’algorithme ne fournit pas de PGCD au sens usuel ; il faut exclure ce couple ou annoncer explicitement une convention différente.

On cherche le PGCD de deux entiers : 252 et 105. Les seules données de départ sont donc le dividende 252 et le diviseur 105.

1. Divisez 252 par 105 : $252=2\times 105+42252=2\backslash times105+42$. Le nouveau couple est (105, 42).
2. Divisez 105 par 42 : $105=2\times 42+21105=2\backslash times42+21$. Le nouveau couple est (42, 21).
3. Divisez 42 par 21 : $42=2\times 21+042=2\backslash times21+0$. Le calcul s’arrête.

Le dernier reste non nul est 21, donc le PGCD de 252 et 105 vaut 21. Le diagramme associé matérialise la diminution des restes à chaque division. Pour contrôler le résultat, on vérifie d’abord que 252 = 12 × 21 et 105 = 5 × 21. Réciproquement, tout diviseur commun divise 252 − 2 × 105 = 42, puis 105 − 2 × 42 = 21. Ainsi, 21 divise les deux nombres et tout diviseur commun divise 21 : c’est bien le plus grand.

Pour partager deux quantités entières en paquets identiques aussi grands que possible, on calcule leur PGCD. Les divisions successives sont préférables à l’essai de tous les diviseurs dès que les nombres deviennent grands.

Pour déterminer si deux entiers sont premiers entre eux, on exécute le même algorithme. Le critère observable est simple : le dernier reste non nul doit être 1. Une recherche séparée de tous les facteurs n’est alors pas nécessaire.

Lorsqu’il faut aussi écrire le PGCD comme combinaison des deux nombres de départ, on choisit l’algorithme d’Euclide étendu. Il conserve l’information des quotients et produit les coefficients de Bézout, contrairement à la version qui ne renvoie que le PGCD.

Algorithme d’Euclide et division euclidienne. Une division euclidienne produit un quotient et un reste pour une paire d’entiers. L’algorithme en enchaîne plusieurs : avec 252 et 105, une seule division laisse 42, tandis que trois divisions conduisent au PGCD 21.

Algorithme ordinaire et algorithme étendu. Le premier suffit pour obtenir 21 et permet aussi de retrouver des coefficients de Bézout par remontée des divisions et substitutions. Le second est une méthode directe pour obtenir en plus ces coefficients, qui expriment 21 comme combinaison entière de 252 et 105.

PGCD et nombres premiers entre eux. Être premiers entre eux ne signifie pas que chaque nombre est premier. Le critère porte sur leur PGCD : deux entiers sont premiers entre eux exactement lorsque celui-ci vaut 1.

Un reste qui ne devient jamais nul n’est pas un cas entier. Pour deux entiers, les restes positifs forment une suite strictement décroissante, donc l’algorithme s’arrête toujours. Le bon test des entiers premiers entre eux n’est pas une poursuite infinie : leur dernier reste non nul vaut 1.

Le couple (0, 0) doit être écarté. Aucun plus grand diviseur commun usuel n’existe pour ce couple. Si un seul entier est nul, le PGCD est la valeur absolue de l’autre et aucune chaîne de divisions n’est nécessaire.

Soustractions et divisions n’ont pas le même coût. L’anthyphérèse retranche plusieurs fois la petite valeur ; la forme moderne regroupe ces retraits dans le quotient d’une division euclidienne. Il faut préférer cette dernière quand un quotient dépasse 1.

Le cadre géométrique change le sens d’un processus infini. Pour deux longueurs, le pavage par carrés peut ne jamais s’achever ; cela signale qu’elles sont incommensurables, et non que deux entiers ont un PGCD introuvable.

Le théorème de Lamé borne le nombre d’étapes de l’algorithme par cinq fois le nombre de chiffres, en base 10, du plus petit entier. Cette estimation relie la diminution des restes à la complexité du calcul.

PGCD. Approfondir le résultat calculé, ses diviseurs communs et le cas où il vaut 1.

Division euclidienne. Examiner l’opération qui fournit, à chaque étape, le quotient et le reste.

Anneau euclidien. Voir dans quel cadre algébrique le mécanisme des divisions successives se généralise.