Algorithme d'Euclide et identité de Bézout pour 23 et 8

On considère les entiers $a=23$ et $b=8$.

1. Effectuer la division euclidienne de $a$ par $b$ : déterminer le quotient $q$ et le reste $r$ tels que $a=bq+r$ avec $0\le r<b$.

2. À l'aide de l'algorithme d'Euclide, déterminer $\mathrm{PGCD}(23,8)$.

3. En remontant l'algorithme d'Euclide, déterminer un couple d'entiers relatifs $(u,v)$ tel que $23u+8v=1$.

4. Qu'en déduit-on pour les entiers $23$ et $8$ ?