PGCD, Bézout et équation diophantienne — Niveau intermédiaire

Exercice 3

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

1. Calculer d = $\text{pgcd}(252,180)$ en appliquant l'algorithme d'Euclide. Détailler chaque étape.
2. En remontant l'algorithme d'Euclide, déterminer deux entiers u, v $\in$ $\mathbb{Z}$ tels que $252u+180v=d$ (relation de Bézout).
3. Résoudre dans ${\mathbb{Z}}^2$ l'équation diophantienne : $252x+180y=36$. Donner l'ensemble des solutions.
4. Un commerçant de Casablanca dispose de billets de $252$ dirhams et de billets de $180$ dirhams (fictifs). Peut-il constituer une somme exacte de $900$ dirhams en utilisant ces deux types de billets (le nombre de billets de chaque type pouvant être négatif, i.e. il peut rendre la monnaie) ? Si oui, donner une solution.