Déterminer un PGCD

Dans cet exercice, nous utilisons l'algorithme d'Euclide pour calculer le PGCD de 18840 et 9828. L'algorithme d'Euclide consiste en une série de divisions euclidiennes. Nous commençons en divisant le plus grand nombre par le plus petit. Ainsi, nous obtenons 18840 divisé par 9828, ce qui donne 9828 multiplié par 1, plus 9012 comme reste. Ensuite, nous divisons le diviseur (9828) par le reste (9012). Nous répétons ce processus jusqu'à obtenir un reste de 0. Ainsi, nous avons 9828 divisé par 9012, ce qui donne 9012 multiplié par 1, plus 816 comme reste. Nous continuons avec 9012 divisé par 816, ce qui donne 816 multiplié par 11, plus 36 comme reste. Nous poursuivons avec 816 divisé par 36, ce qui donne 36 multiplié par 22, plus 24 comme reste. Ensuite, nous avons 36 divisé par 24, ce qui donne 24 multiplié par 1, plus 12 comme reste. Enfin, nous divisons 24 par 12, ce qui donne 12 multiplié par 2, plus 0 comme reste (qui est un multiple de 12). À ce stade, nous avons atteint un reste de 0, nous arrêtons donc l'algorithme d'Euclide. Le dernier reste non nul (12) est le PGCD de 18840 et 9828. Ainsi, le PGCD de 18840 et 9828 est 12.