PGCD, Bézout et équation diophantienne

Exercice 2 — PGCD, identité de Bézout et équation diophantienne

On considère les entiers $a=252$ et $b=180$.

1. Appliquer l'algorithme d'Euclide pour calculer $d=\text{pgcd}(252,180)$. Détailler toutes les étapes.
2. En remontant les étapes de l'algorithme, exprimer $d$ sous la forme $252u+180v$ avec $(u,v)\in {\mathbb{Z}}^2$ (identité de Bézout).
3. En déduire toutes les solutions entières de l'équation $(E):252x+180y=36$.
4. Un commerçant de Casablanca dispose de billets de 252 dirhams (bons d'achat) et de bons de réduction de 180 dirhams. Il souhaite obtenir exactement 36 dirhams de remise nette (en combinant gains et remboursements). Interpréter les solutions de (E) dans ce contexte et donner la solution avec la plus petite valeur positive de $x$.