PGCD, théorèmes de Bézout et de Gauss

Algorithme d'Euclide :
17 = 12×1 + 5.
12 = 5×2 + 2.
5 = 2×2 + 1.
2 = 1×2 + 0.
Dernier reste non nul : 1, donc PGCD(17, 12) = 1 (les entiers sont premiers entre eux).
On remonte pour écrire 1 en fonction de 17 et 12 :
1 = 5 − 2×2.
Or 2 = 12 − 5×2, donc 1 = 5 − 2×(12 − 5×2) = 5 − 2×12 + 4×5 = 5×5 − 2×12.
Or 5 = 17 − 12, donc 1 = 5×(17 − 12) − 2×12 = 5×17 − 7×12.
Ainsi 17×5 + 12×(−7) = 1 : (u, v) = (5, −7).
Vérification : 85 − 84 = 1.

Comme PGCD(5, 3) = 1, l'équation admet des solutions.
Solution particulière repérée à l'œil : x = 2, y = −3, car 5×2 + 3×(−3) = 10 − 9 = 1.
Soit (x, y) une solution quelconque. En soustrayant : 5x + 3y = 5×2 + 3×(−3), donc 5(x − 2) = −3(y + 3).
Ainsi 3 divise 5(x − 2) ; or PGCD(3, 5) = 1, donc par le théorème de Gauss 3 divise (x − 2) : x − 2 = 3k avec k ∈ ℤ.
Alors x = 2 + 3k, et en reportant : 5×3k = −3(y + 3), soit y + 3 = −5k, d'où y = −3 − 5k.
Réciproquement tout couple convient : 5(2 + 3k) + 3(−3 − 5k) = 10 + 15k − 9 − 15k = 1.
Solutions : (x, y) = (2 + 3k ; −3 − 5k), k ∈ ℤ.