Histoire des mathématiques Algorithme

algorithme d'Euclide

Algorithme

algorithme d'arithmétique calculant le PGCD de deux entiers

Pour comprendre

rédaction

Réduire par les restes

L'algorithme d'Euclide calcule le plus grand commun diviseur de deux entiers par divisions successives. On divise le plus grand nombre par le plus petit, puis on remplace le plus grand par le reste obtenu. Le même geste recommence jusqu'à ce que le reste soit nul ; le dernier reste non nul est le pgcd.

Voir les divisions dans un rectangle

La version géométrique, appelée anthyphérèse, consiste à paver un rectangle avec les plus grands carrés possibles. Le rectangle restant est traité de la même manière, et le côté du dernier carré donne le diviseur commun maximal. Ainsi, pour \(21\) et \(15\), les restes conduisent à \(\mathrm{pgcd}(21, 15) = 3\). C'est un algorithme ancien dont le principe reste directement utilisable aujourd'hui encore.

Repères historiques

  • décrit dans les Éléments d'Euclide vers -300 (livre VII)
  • version étendue et usages modernes en arithmétique et en cryptographie

La figure représente le rectangle \(21\) sur \(15\) pavé de carrés successifs jusqu'au carré de côté \(3\).

{ "boundingBox": [ -1.5, 17, 23, -1.5 ], "axis": false, "grid": true, "polygons": [ { "vertices": [ [ 0, 0 ], [ 15, 0 ], [ 15, 15 ], [ 0, 15 ] ], "fillColor": "#93c5fd", "color": "#1e3a8a" }, { "vertices": [ [ 15, 0 ], [ 21, 0 ], [ 21, 6 ], [ 15, 6 ] ], "fillColor": "#fca5a5", "color": "#7f1d1d" }, { "vertices": [ [ 15, 6 ], [ 21, 6 ], [ 21, 12 ], [ 15, 12 ] ], "fillColor": "#fca5a5", "color": "#7f1d1d" }, { "vertices": [ [ 15, 12 ], [ 18, 12 ], [ 18, 15 ], [ 15, 15 ] ], "fillColor": "#fde68a", "color": "#a16207" }, { "vertices": [ [ 18, 12 ], [ 21, 12 ], [ 21, 15 ], [ 18, 15 ] ], "fillColor": "#fde68a", "color": "#a16207" } ], "labels": [ { "x": 6, "y": 7, "text": "15 x 15", "color": "#1e3a8a" }, { "x": 16.6, "y": 2.6, "text": "6 x 6", "color": "#7f1d1d" }, { "x": 0.5, "y": 16, "text": "rectangle 21 x 15 : pgcd(21, 15) = 3", "color": "#1e3a8a" } ] }

Dates

premiere trace
Éléments d'Euclide, livre VII approximative

Liens

porte le nom de

Sources