Calculer un inverse modulo n et résoudre ax ≡ b [n] - Exercice 1

Appliquons l'algorithme d'Euclide à $$60$$ et $$17$$ :
Le dernier reste non nul vaut $$1$$ : $$\text{PGCD}\left(60;17\right)=1$$, donc $$17$$ est inversible modulo $$60$$.
On isole les restes non nuls obtenus : $$9=60-17\times 3$$ ; $$8=17-9\times 1$$ ; $$1=9-8\times 1$$.
Maintenant nous allons remonter l'algorithme d'Euclide en partant du dernier reste non nul :
$$1=9-8$$
$$1=9-\left(17-9\right)$$
$$1=2\times 9-17$$
$$1=2\times\left(60-17\times 3\right)-17$$
$$1=2\times 60-7\times 17$$
Ainsi $$17\times\left(-7\right)=1-2\times 60$$, donc $$17\times\left(-7\right)\equiv 1\left[60\right]$$ : $$-7$$ est un inverse de $$17$$ modulo $$60$$.
Comme $$-7+60=53$$, on a $$-7\equiv 53\left[60\right]$$.
Vérification : $$17\times 53=901=15\times 60+1$$

$$17x\equiv 5\left[60\right]$$ équivaut successivement à (on multiplie par $$53$$, et on revient en arrière en multipliant par $$17$$) :
$$53\times 17x\equiv 53\times 5\left[60\right]$$
$$x\equiv 265\left[60\right]$$ car $$53\times 17=901\equiv 1\left[60\right]$$
$$x\equiv 25\left[60\right]$$ car $$265=4\times 60+25$$
Vérification : $$17\times 25=425=7\times 60+5$$
Les solutions sont les entiers :

$$17x+4\equiv 11\left[60\right]$$ équivaut successivement à :
$$17x\equiv 7\left[60\right]$$
$$x\equiv 53\times 7\left[60\right]$$
$$x\equiv 371\left[60\right]$$
$$x\equiv 11\left[60\right]$$ car $$371=6\times 60+11$$
Vérification : $$17\times 11+4=191=3\times 60+11$$