#154 / 200•Foundations•MathTCG #154 / 500•★★Peu commune•ℤArithmétique•Méthode & Idée

Algorithme d'Euclide

Période historique : env. 300 av. J.-C.

Le plus ancien algorithme de l'histoire : calculer le plus grand commun diviseur (PGCD) par divisions successives.

Contenu & Formulation mathématique

Principe de la démarche

Remplacer itérativement le couple d'entiers (a, b) par le couple (b, a mod b) jusqu'à ce que le reste devienne zéro.

Champs d'application canoniques

Simplification de fractions, résolution d'équations diophantiennes et calcul des clés privées en cryptographie RSA.

\text{pgcd}(a, b) = \text{pgcd}(b, a \bmod b)

Genèse & Portée historique

Méthode arithmétique ancestrale trouvant le PGCD de deux entiers en effectuant des divisions euclidiennes successives jusqu'à obtenir un reste nul. Sa variante étendue calcule également les coefficients de Bézout u et v tels que au + bv = pgcd(a, b).

Présenté dans les livres VII et X des Éléments d'Euclide, Donald Knuth le considère comme le patriarche absolu de tous les algorithmes informatiques en raison de sa concision et de son efficacité logarithmique.

« Retrancher le reste jusqu'à ce que la mesure commune se dévoile dans sa simplicité. »

Filiations & Relations conceptuelles (1)

Établi / Formulé par#104

Euclide

Exposa l'algorithme du PGCD par divisions successives dans les Éléments.

Objet de collection MathTCG

#154

★★Peu commune

ℤ

Algorithme d'Euclide

Arithmétique•MÉTHODE

Principe : Remplacer itérativement le couple d'entiers (a, b) par le couple (b, a mod b) jusqu'à ce que le reste devienne zéro.

\text{pgcd}(a, b) = \text{pgcd}(b, a \bmod b)

env. 300 av. J.-C.

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Foundations.

Extension : Foundations (#154 / 200)

Numéro global MathTCG : MathTCG #154 / 500

Rareté officielle : Peu commune (★★)

Domaine théorique : Arithmétique

Identifiant pérenne : algorithme-d-euclide

Consulter mon classeur Explorer tout le recueil