Exercice 9 - Inversion dans $Z/11Z$

Compléter le tableau suivant

$k$	inversible ?	$k^{-1}$ dans $Z/11Z$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$7$
$8$
$9$
$10$

Etant donnés $n$ et $k$, on inverse $k$ en déterminant $k^\prime$ tel que $k \times k^\prime = 1$ dans $Z/nZ$. $k^\prime$ vérifie $k^\prime k = 1 \ mod\ n$, autrement dit $k^\prime k \equiv 1 \pmod n$. Cela équivaut à $n \vert k^\prime k - 1$. On recherche donc $\lambda$ tel que $\lambda n = k^\prime k - 1$, ce qui nous donne l'équation de deux inconnues $k^\prime$ et $\lambda$

$$k^\prime k - \lambda n = 1$$

Ce type d'équation se résout avec l'algorithme d'Euclide étendu si et seulement si $k$ est premier avec $n$. On en déduit la propriété suivante :

Propriété 15.2.2   $k$ est inversible dans $Z/nZ$ si et seulement si $k$ est premier avec $n$.