L'algorithme de calcul du PGCD date au moins d'Euclide. Il a ensuite été perfectionné au cours des siècles.

 

Le théorème de la division euclidienne fournit un algorithme (précisément l'algorithme d'Euclide) permettant de calculer le plus grand commun diviseur, ou PGCD, de deux nombres. Pour des cas élémentaires, la valeur du PGCD saute aux yeux ! Ainsi, le PGCD de 21 et 15 vaut 3. Mais que dire du PGCD de 1 597 et 987 ? L'algorithme d'Euclide permet de calculer le PGCD de deux nombres entiers naturels non nuls a et b par des divisions successives : on divise a par b ; puis b par le reste trouvé ; puis le premier reste par le deuxième reste ; le deuxième par le troisième… et le dernier reste non nul est le PGCD. Ainsi, le PGCD de 1597 et 987 est 1 ; ces deux entiers sont premiers entre eux.

 

 

 

Dès que l'on dispose d'un algorithme, on s'intéresse à son efficacité. Comment la « mesurer » ? Quel est le « temps de calcul » ? C'est l'objet d'une note, chère aux informaticiens d'aujourd'hui, publiée en 1844 par Gabriel Lamé (1795- 1870). Regardons ce qu'écrit, dans les Comptes rendus hebdomadaires de l'Académie des sciences, cet académicien  fraîchement nommé : « Dans les traités d'Arithmétique, on se contente de dire que le nombre des divisions à effectuer, dans la recherche du plus grand commun diviseur entre deux entiers, ne pourra pas surpasser la moitié du plus petit. Cette limite, qui peut être dépassée si les nombres sont petits, s'éloigne outre mesure quand ils ont plusieurs chiffres. » Il établit ensuite : « Le nombre de divisions à effectuer, pour trouver le plus grand commun diviseur entre deux entiers A, et B < A, est toujours moindre que cinq fois le nombre des chiffres de B [le diviseur]. »

Il termine par un exemple marquant la force de son théorème : « Soient pris, pour exemple, les deux nombres 1597 et 987. La recherche de leur plus grand commun diviseur se composera de quatorze divisions. La limite assignée par le théorème actuel est quinze. La limite adoptée dans les traités d'Arithmétique serait quatre cent quatre-vingt-treize. »

En fait, il faut bien quinze divisions (et non quatorze), comme le stipule le tableau récapitulatif suivant :

 Moult contributeurs oubliés