Commençons par trouver le plus grand diviseur commun de 527 et 341 en utilisant l’algorithme euclidien standard comme échauffement :
L’algorithme standard est succinct et simple et servira de petit guide agréable pour la mise en œuvre de l’algorithme étendu.
Pour l’algorithme euclidien étendu, nous allons prendre la troisième équation (en bleu), soustraire 155(1) des deux côtés, et faire un petit réarrangement pour faire une équation équivalente où 31 est isolé.
Puis nous remplacerons 155 par 341-186(1), qui peut être trouvé en résolvant la deuxième équation pour 155, ce qui nous donne ce qui suit :
Maintenant nettoyons cela. Assurez-vous de distribuer le signe négatif à travers les parenthèses et de remplacer 186 + 186 par 186-2.
Comme vous pouvez le remarquer, nous travaillons simplement à rebours à travers l’algorithme standard. Nous devrons exécuter ce processus une fois de plus pour obtenir une équation impliquant 527 et 341, ce qui est finalement notre objectif.
Pour ce faire, remplacez 186 par 527 – 341(1), qui provient de la première équation lorsque nous résolvons pour 186.
Simplifiez à nouveau l’équation en distribuant le 2 et en le combinant en groupes de 527 et 341.
Nous avons maintenant exprimé 31 comme une combinaison linéaire de 527 et 341. Plutôt cool, non ?
De plus, le nombre du côté opposé de la combinaison linéaire est le plus grand diviseur commun. Donc, dans ce cas, 31 est le plus grand diviseur commun de 527 et 341.
L’algorithme euclidien étendu est pratique car il donne l’identité de Bezout ainsi que la mise en évidence du pgcd.
Merci de lire!