Déterminer un PGCD

Dans cet exercice, l'objectif est de calculer le Plus Grand Commun Diviseur (PGCD) des nombres 18840 et 9828 en utilisant l'algorithme d'Euclide. L'algorithme d'Euclide consiste en une série de divisions euclidiennes successives. On commence par diviser le plus grand nombre par le plus petit. Dans ce cas, 18840 peut être divisé par 9828 une fois, avec un reste de 9012. Ensuite, on effectue la division euclidienne du diviseur précédent par ce reste. On répète ce processus jusqu'à obtenir un reste de 0. Ainsi, 9828 divisé par 9012 donne un résultat de 1, avec un reste de 816. On continue avec cette division, donc 9012 divisé par 816 donne un résultat de 11, avec un reste de 36. On répète une fois de plus, donc 816 divisé par 36 donne un résultat de 22, avec un reste de 24. On continue, 36 divisé par 24 donne un résultat de 1, avec un reste de 12. Enfin, 24 divisé par 12 donne un résultat de 2, avec un reste de 0. Le reste de 0 indique que nous avons atteint un multiple commun. En utilisant l'algorithme d'Euclide, le PGCD entre 18840 et 9828 est donc 12, qui correspond au dernier reste non nul obtenu.