Avec les mathématiciens grecs, Euclide en particulier, les nombres sont passés du concret à l'abstrait. Il en est resté un concept clé : la division euclidienne et son cortège de développements. Ces méthodes n'ont pas pris une ride puisque l'algorithme d'Euclide est utilisé de nos jours... par les informaticiens !

Euclide et Euler, voisins dans l'ordre alphabétique des dictionnaires, ont tous deux laissé une œuvre monumentale et leurs écrits, que vingt siècles séparent pourtant, ont marqué pour des générations l'histoire des mathématiques et de leur enseignement. C'est aujourd'hui Euclide et l'héritage qu'il nous offre en théorie des nombres qui nous intéresse : dans ce domaine, tout – division euclidienne, algorithme d'Euclide – porte son nom.

 

 

D'Euclide lui-même, on ne sait presque rien. Certains ont même douté de son existence, le confondant avec d'autres personnages, car le nom Euclide était courant à l'époque, ou insinuant que son œuvre est le fruit du travail d'un groupe de mathématiciens, un peu comme le groupe Bourbaki au XX^e siècle. Ératosthène dit cependant être son contemporain et on trouve chez Archimède des références – peut-être ajoutées a posteriori ? – à Euclide. Quoiqu'il en soit, environ entre –325 et –265, quelqu'un du nom d'Euclide, sans doute entouré par une école, a rassemblé sous le nom d'Éléments un corpus complet de savoirs mathématiques. Le tout tient en treize livres, qui constituent le plus merveilleux manuel de mathématiques de tous les temps.

 

Le philosophe Proclus est formel : « Pas beaucoup plus jeune que les élèves de Platon, Euclide a mis en ordre de nombreux théorèmes d'Eudoxe, perfectionné un certain nombre de ceux de Théétète, donnant une irréfutable démonstration aux résultats qui avaient été vaguement prouvés par ses prédécesseurs. » Euclide est, à n'en pas douter, plus qu'un compilateur ; il n'est pas un mathématicien-créateur, mais il a su, avec une clarté remarquable, ordonner les propositions, établir des théorèmes et les prouver avec rigueur, usant pour la première fois dans l'histoire des mathématiques d'une démarche axiomatique. Cette méthode confère aux Éléments, qui ont fait l'objet de huit cents éditions (à peine moins que la Bible !), le statut d'œuvre de référence pendant deux millénaires. Les autres ouvrages d'Euclide, dont certains se sont perdus, sont une preuve de sa vision organisée et philosophique des choses. Les Données, quatre-vingt-quatorze propositions en complément des Éléments ; De la division des figures, ou comment diviser une figure en deux parties dans un rapport donné, et Lieux et Surfaces traitent de géométrie. Les Phénomènes traitent d'astronomie mathématique, les Porismes et le Livre des arguments fallacieux de logique et raisonnement, Optique et Éléments de musique abordent l'application de la théorie des proportions.

Dans l'œuvre éclectique d'Euclide, les Livres VII, VIII et IX des Éléments traitent de théorie des nombres et nous intéressent tout particulièrement. Il procède, comme en géométrie, en commençant par les définitions : unité, nombre, pairs et impairs, multiples, nombres premiers, nombres premiers entre eux, et va même jusqu'aux nombres parfaits. Il poursuit par ses Propositions : l'algorithme d'Euclide (première proposition), les propriétés de proportionnalité, des nombres premiers entre eux, des nombres premiers, le PGCD et le PPCM, l'infinité des nombres premiers. Nous avons là un panorama complet de l'arithmétique !

 

 

Diviser un entier a par un entier b non nul, c'est trouver le couple d'entiers (q, r) tels que a = bq + r avec 0 ≤ r < b. Aujourd'hui, on appelle cette division avec reste division euclidienne, mais cette opération existait bien avant Euclide.

Au XX^e siècle avant notre ère, les Babyloniens alliaient tables d'inverses et tables de multiplication pour, déjà, effectuer des divisions. Leurs tables d'inverses n'étaient pas simples à utiliser : en effet, ils calculaient en base 60. Elles étaient du style suivant : « La deuxième partie est 30, la troisième partie est 20, la quatrième partie est 15, la cinquième partie est 12, la sixième partie est 10, la septième partie n'est pas. » Cela rendait, en pratique, certaines divisions impossibles à réaliser.

Au XVI^e siècle avant notre ère, les Égyptiens la pratiquaient en procédant par duplication et médiation, c'est-à-dire « partage en deux ». Pour diviser par exemple 23 par 8, ils écrivaient successivement 2  \( \times\) 8 = 16 (duplication), puis (1 / 2) \( \times\) 8 = 4, (1 / 4) \( \times\) 8 = 2, (1 / 8) \( \times\) 8 = 1 (médiation), pour obtenir : 23 = 16 + 4 + 2 + 1, d'où 23 divisé par 8 donne 2 + 1/2 + 1/ 4 + 1/ 8, avec les fameuses fractions égyptiennes, de numérateurs tous égaux à 1.

Le système grec, décimal avec des symboles de numération alphabétiques, se prête difficilement à l'écriture des fractions, même s'il existait un symbole pour 1 / 2.

On peut y opérer des divisions, mais seulement pour des nombres « pas trop longs ». Euclide, quant à lui, fidèle à sa représentation géométrique des nombres, pour diviser A par B, procède par soustraction d'autant de fois B qu'il est nécessaire, jusqu'à ce qu'il ne puisse plus le faire et qu'il reste… le reste.

 

 

Cette action d'enlever successivement était chez les Grecs une pratique déjà connue sous le nom d'anthyphérèse (« soustraire alternativement ») et c'est avec cette technique qu'Euclide va inventer et décrire l'algorithme qui va, à juste titre cette fois, porter son nom.

Le procédé tient en deux propositions :

Il s'agit là, ni plus ni moins, de déterminer le plus grand commun diviseur (PGCD) des deux nombres, représentés par les segments [AB], le plus grand, et [CD]. Euclide procède d'abord par disjonction des cas : ou bien CD « mesure » AB, et alors il est lui-même le PGCD, ou CD ne mesure pas AB. Dans ce cas, après avoir retiré CD autant de fois que l'on pouvait de AB, l'opération laisse EA plus petit que lui-même. Et on recommence l'opération : soustraire EA autant de fois qu'on le peut de CD, pour laisser un reste CF, qui « mesure » EA, tout comme il mesure aussi AB et CD : c'est donc une mesure commune. Euclide termine en démontrant par l'absurde que cette mesure est la plus grande.

L'algorithme n'est pas bien long : il se termine en trois étapes (voir l'encadré).

L'algorithme est transposable en de plus nombreuses étapes. Pour déterminer le PGCD de deux nombres a et b (par exemple a > b), on opère par divisions en cascade, le reste de la précédente servant de diviseur à la suivante : on commence à diviser a par b (quotient q₁, reste r₁), puis on divise b par r₁, etc. Ces restes successifs sont tels que 

PGCD(a, b) = PGCD(b, r₁) car leurs ensembles de diviseurs sont les mêmes,

PGCD(b, r₁) = PGCD(r₁, r₂). On définit ainsi la suite (r_k)_k des restes successifs, tels que

 b > r₁ > r₂ > … > r_n-1 > r_n ≥ 0, strictement décroissante, et dont le nombre de termes non nuls est fini. Si n est le plus petit entier tel que r_n = 0, r_n-1, le dernier reste non nul vérifie que

PGCD(a, b) = PGCD(b, r₁) = PGCD(r₁, r₂) = …= PGCD(r_n-2, r_n-1) = r_n-1.

Le PGCD de a et b est donc r_n-1, le dernier reste non nul.

La méthode d'anthyphérèse a survécu à Euclide jusqu'à aujourd'hui et n'a pas pris une ride puisque l'algorithme est utilisé par les informaticiens ! Cette longévité est une preuve de la force d'Euclide, que l'historien des mathématiques grecques David Herbert Fowler a fort bien exprimée à la lecture des manuscrits d'Euclide : « Ils montrent d'évidence quelqu'un, au III^e siècle avant J.-C., à plus de 500 miles au sud d'Alexandrie, travaillant sur ce matériel difficile… Cela ne pouvait être qu'une tentative de comprendre les mathématiques, et non pas une copie de scribe. »