Exercice : PGCD, Algorithme d'Euclide et Théorème de Bézout

Étape 1

On effectue les divisions euclidiennes successives de l'algorithme d'Euclide : $$122 = 35 \times 3 + 17$$ $$35 = 17 \times 2 + 1$$ $$17 = 1 \times 17 + 0$$ Le dernier reste non nul est $1$, donc $$\text{PGCD}(122, 35) = 1$$

Étape 2

On remonte les égalités pour exprimer $1$ en fonction de $122$ et $35$ : $$1 = 35 - 17 \times 2$$ En remplaçant $17$ par $122 - 35 \times 3$, on obtient : $$1 = 35 - (122 - 35 \times 3) \times 2$$ $$1 = 122 \times (-2) + 35 \times 7$$ Un couple de solutions particulières de l'équation $122 x + 35 y = 1$ est donc $(x_0, y_0) = (-2, 7)$.

Étape 3

Soit $(x, y)$ un couple d'entiers relatifs vérifiant $122 x + 35 y = 1$. Par soustraction membre à membre avec $122(-2) + 35(7) = 1$, on obtient $$122(x + 2) + 35(y - 7) = 0$$ ce qui équivaut à $$122(x + 2) = 35(7 - y)$$ Comme $\text{PGCD}(122, 35) = 1$, d'après le théorème de Gauss, $35$ divise $122(x + 2)$ donc $35$ divise $x + 2$. Il existe ainsi un entier relatif $k$ tel que $x + 2 = 35k$, soit $$x = -2 + 35k$$

Étape 4

On cherche la plus petite valeur entière $x$ strictement positive, c'est-à-dire $x > 0$ : $$-2 + 35k > 0$$ ce qui donne $35k > 2$, soit $k \ge 1$ pour tout entier $k$. La valeur minimale strictement positive de $x$ est obtenue pour $k = 1$ : $$x = -2 + 35 \times 1 = 33$$