Description de l'exemple
À quoi peut servir de savoir calculer le plus grand commun diviseur (pgcd) de deux nombres ? À plusieurs choses, dont à• réduire une fraction à sa plus simple expression : il suffit de diviser le numérateur et le dénominateur par leur pgcd
• calculer le plus petit commun multiple (ppcm) de deux nombres : il suffit de diviser leur produit par leur pgcd
• établir que deux nombres n'ont pas de diviseur commun autre que 1 : il suffit de calculer leur pgcd et de constater qu'il vaut 1.
Il existe plusieurs façons de calculer le pgcd : un certain nombre d'entre elles sont décrites sur le site d'alloprof. Toutes les façons décrites sur ce site ont le mérite de découler assez directement de la définition du pgcd, alors que ce n'est pas le cas de l'algorithme d'Euclide, utilisé dans le programme ci-dessus.
Alors, pourquoi même parler de cet algorithme, qui date de plus de deux mille ans ? Une raison importante est que cet algorithme est beaucoup plus rapide quand les nombres dont on veut calculer le pgcd sont grands : pour vous en convaincre, comparez tous ces algorithmes pour calculer le pgcd de 2323111111117 et de 7034534219177. En effet, on sait qu'il n'est pas facile de factoriser de grands nombres, mais l'algorithme d'Euclide n'a pas besoin de factoriser quoi que ce soit pour trouver le pgcd.
C'est ce qui permet d'utiliser l'algorithme d'Euclide dans le chiffrement RSA, qui facilite l'échange d'informations confidentielles (comme des numéros de cartes de crédit) sur internet. Parions qu'Euclide aurait été ravi d'apprendre que son algorithme possède de telles applications pratiques !
Notez que la taille des entiers acceptés par p5Visuel est de 53 chiffres binaires (soit environ 16 chiffres décimaux) : notre programme fonctionne correctement tant que cette limite n'est pas atteinte. Mais si vous essayez de donner un nombre avec plus de 16 décimales, il sera arrondi et converti sous forme exponentielle : les calculs de notre programme cesseront alors d'être fiables.