algorithme d’Euclide

anthyphérèse
anthyphaïrèse
méthode d’antyphérèse
méthode d’anthyphaïrèse
algorithme du PGCD
calcul du PGCD par divisions successives

ARITHMETIQUE
CALCUL

L’anthyphérèse, ou anthyphaïrésis, ou antiphérèse, est une méthode décrite par Euclide , et qui est ce qu’on appelle aussi l’algorithme d’Euclide.
Etymologiquement, anthyphérèse signifie « enlever tour à tour ». Elle consiste, pour deux grandeurs inégales, à enlever la plus petite de la plus grande, et à itérer le processus.

Elle est décrite par Euclide dans le livre VII des Eléments pour des nombres et dans le livre X pour des grandeurs.
Pour les nombres, on retranche le plus petit du plus grand et on itère en alternance, si le reste n’est jamais égal au reste précédent jusqu’à ce qu’il reste une unité, les nombres initiaux sont premiers entre eux.
On calcule ainsi le pgcd sans passer par la décomposition en facteurs premiers, en se basant sur le fait que le pgcd de deux nombres a et b est aussi le pgcd de b et du reste de la division de a par b (ce qui est plus rapide que d’effectuer les soustractions). On construit alors une suite de nombres, le terme an+2 étant le reste de la division de an par an+1. Le dernier reste non nul est le pgcd de a et b.
La formulation géométrique d’Euclide consiste à construire une suite de carrés à l’intérieur du rectangle de départ. Chacun a pour côté la largeur du rectangle précédent. Si le dernier reste ne mesure jamais le reste précédent, les grandeurs sont incommensurables. Le pgcd de la longueur et la largeur du rectangle est alors la longueur du plus grand carré avec lequel on peut paver le rectangle.
Basé sur la structure d’anneau euclidien, cet algorithme se généralise à d’autres anneaux .
L’algorithme d’Euclide permet de calculer les coefficients de Bézout , on l’appelle algorithme d’Euclide étendu .
Le théorème de Lamé montre que le nombre d’étapes de l’algorithme d’Euclide exécuté sur deux entiers est majoré par cinq fois le nombre de chiffres nécessaire à écrire (en base 10) le plus petit de ces deux entiers.