Étape 1
On commence par effectuer les divisions euclidiennes successives pour déterminer le PGCD de $348$ et $129$ par l'algorithme d'Euclide :$$348 = 2 \times 129 + 90$$$$129 = 1 \times 90 + 39$$$$90 = 2 \times 39 + 12$$$$39 = 3 \times 12 + 3$$$$12 = 4 \times 3 + 0$$Le dernier reste non nul est $3$, donc $\text{PGCD}(348, 129) = 3$.
Étape 2
On isole chaque reste non nul afin de préparer la remontée de l'algorithme :$$90 = 348 - 2 \times 129$$$$39 = 129 - 1 \times 90$$$$12 = 90 - 2 \times 39$$$$3 = 39 - 3 \times 12$$
Étape 3
On exprime le PGCD (c'est-à-dire $3$) en remplaçant successivement les restes de bas en haut. En remplaçant d'abord $12$ par $90 - 2 \times 39$, on obtient :$$3 = 39 - 3 \times (90 - 2 \times 39) = 7 \times 39 - 3 \times 90$$En remplaçant ensuite $39$ par $129 - 90$, on obtient :$$3 = 7 \times (129 - 90) - 3 \times 90 = 7 \times 129 - 10 \times 90$$En remplaçant enfin $90$ par $348 - 2 \times 129$, on obtient :$$3 = 7 \times 129 - 10 \times (348 - 2 \times 129) = -10 \times 348 + 27 \times 129$$
Étape 4
On en déduit que le couple d'entiers relatifs issu de la remontée de l'algorithme est $x = -10$ et $y = 27$.
Étape 5
On calcule enfin la valeur du paramètre $k$ :$$k = 2x + y = 2 \times (-10) + 27 = -20 + 27 = 7$$
Méthode clé
Isoler le reste de chaque division euclidienne $r = a - bq$, puis substituer les restes de bas en haut pour obtenir le PGCD en fonction des entiers de départ.
Piège à éviter
Confondre les quotients et les restes lors des substitutions successives, ou commettre des erreurs de signe lors du développement des parenthèses.
