Exercice 34

• Si $n$ est premier. Soit $a\in\{1,\dots,n-1\}$. Les seuls diviseurs positifs de $n$ sont $1$ et $n$, et $n$ ne divise pas $a$ puisque $0<a<n$. Donc $\mathrm{PGCD}(a,n)=1$, et le théorème de Bézout fournit $u$, $v$ entiers tels que $au+nv=1$. Ainsi $au\equiv 1\;[n]$ : $u$ est un inverse de $a$ modulo $n$.

• Si $n$ n'est pas premier. On écrit $n=rs$ avec $1<r<n$, de sorte que $r\in\{1,\dots,n-1\}$. Supposons que $rx\equiv 1\;[n]$ pour un entier $x$. Alors $n$ divise $rx-1$, donc $r$ aussi ; comme $r$ divise $rx$, il divise $rx-(rx-1)=1$, ce qui contredit $r>1$. L'entier $r$ n'a donc pas d'inverse modulo $n$.

$$\boxed{n \text{ est premier} \iff \text{tout élément de } \{1,\dots,n-1\} \text{ admet un inverse modulo } n}$$ Par exemple, modulo $26$, l'entier $13$ n'a pas d'inverse : c'est la question 3c de l'exercice 13.