Alors que l’algorithme euclidien ne calcule que le plus grand diviseur commun (PGCD) de deux entiers $a$ et $b$, la version étendue trouve également un moyen de représenter le PGCD en termes de $a$ et $b$, c’est-à-dire. coefficients $x$ et $y$ pour lesquels:

$$a \cdot x + b \cdot y = \gcd(a, b)$$

Il est important de noter, que nous pouvons toujours trouver une telle représentation, par exemple $\gcd(55, 80) = 5$ donc nous pouvons représenter $5$ comme une combinaison linéaire avec les termes $55$ et $80$ : $55 \cdot 3 + 80 \cdot (-2) = 5$

Une forme plus générale de ce problème est abordée dans l’article sur les équations diophantiennes linéaires.Il s’appuiera sur cet algorithme.

Algorithme

Nous désignerons le PGCD de $a$ et $b$ par $g$ dans cette section.

Les modifications apportées à l’algorithme original sont très simples.Si on rappelle l’algorithme, on constate qu’il se termine par $b = 0$ et $a = g$.Pour ces paramètres, on peut facilement trouver des coefficients, à savoir $g \cdot 1 + 0 \cdot 0 = g$.

En partant de ces coefficients $(x, y) = (1, 0)$, on peut remonter les appels récursifs.Il suffit de comprendre comment les coefficients $x$ et $y$ évoluent lors du passage de $(a, b)$ à $(b, a \bmod b)$.

Supposons que nous avons trouvé les coefficients $(x_1, y_1)$ pour $(b, a \bmod b)$:

$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$

et nous voulons trouver le couple $(x, y)$ pour $(a, b)$ :

$$ a \cdot x + b \cdot y = g$$

Nous pouvons représenter $a \bmod b$ comme:

$$ a \bmod b = a – \left\lfloor \frac{a}{b} \cdot b$$

Substituer cette expression dans l’équation du coefficient de $(x_1, y_1)$ donne :

$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a – \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1$$

et après réarrangement des termes :

$g = a \cdot y_1 + b \cdot \left( x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$

Nous avons trouvé les valeurs de $x$ et $y$ :

$$\begin{cases}x = y_1 \y = x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor\end{cases} $$

Implémentation

int gcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d;}

La fonction récursive ci-dessus renvoie le PGCD et les valeurs des coefficients à x et y (qui sont passés par référence à la fonction).

Cette implémentation de l’algorithme euclidien étendu produit des résultats corrects pour les entiers négatifs également.

Version itérative

Il est également possible d’écrire l’algorithme euclidien étendu de manière itérative.Parce qu’il évite la récursion, le code s’exécutera un peu plus rapidement que celui qui est récursif.

int gcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1;}

Si vous regardez de près la variable a1 et b1, vous pouvez remarquer qu’elles prennent exactement les mêmes valeurs que dans la version itérative de l’algorithme euclidien normal. Donc l’algorithme calculera au moins le PGCD correct.

Pour voir pourquoi l’algorithme calcule aussi les coefficients corrects, vous pouvez vérifier que les invariants suivants tiendront à tout moment (avant la boucle while, et à la fin de chaque itération) : $x \cdot a + y \cdot b = a_1$ et $x_1 \cdot a + y_1 \cdot b = b_1$.Il est trivial de voir, que ces deux équations sont satisfaites au début.Et vous pouvez vérifier que la mise à jour dans l’itération de la boucle gardera toujours ces égalités valides.

À la fin, nous savons que $a_1$ contient le PGCD, donc $x \cdot a + y \cdot b = g$.Ce qui signifie que nous avons trouvé les coefficients requis.

Vous pouvez même optimiser davantage le code, et supprimer la variable $a_1$ et $b_1$ du code, et juste réutiliser $a$ et $b$.Cependant, si vous faites cela, vous perdez la possibilité d’argumenter sur les invariants.

Problèmes pratiques

• 10104 – Problème d’Euclide
• GYM – (J) Il était une fois
• UVA – 12775 – Dilemme du cadeau

.