Calcul de PGCD : diviser encore et encore
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.
Le théorème de Lamé : peu de divisions à effectuer en pratique
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, ...
Lire la suite