On va démonter l'équivalence en deux étapes:
- Condition nécessaire:
On suppose que $~~a~~$ est inversible dans $~~\mathbb Z/n\mathbb Z$.
$\Rightarrow \exists m\in \mathbb Z~~ \mbox{tel que:}~~\bar a\bar m=\bar 1\Rightarrow \exists k\in \mathbb Z:~~am=1+kn$
$$\Rightarrow am-kn=1\qquad (1)$$ $\Rightarrow a\land n=1~~$ (~car le couple $~~(a,m)~~$ vérifie l'identité de Bezout $~~(1)~~$ ci dessus ) - Condition suffisante:
Maintenant on suppose $~(~a\land n=1~)~$.
Considérons la fonction suivante: \begin{align*} \qquad f&: E\longrightarrow E\\ \qquad \bar x&:~\mapsto~ \bar a\bar x \end{align*} On va montrer que $~~f~~$ est injective:
En effet : soit $~~(x,y)\in\mathbb Z^2~~:$ $$f(\bar x)=f(\bar y)$$ $$\Rightarrow \bar a\bar x=\bar a\bar y\Rightarrow \bar a(\bar x-\bar y)=\overline{a(x-y)}=0$$ $$\Rightarrow a(x-y)=kn\Rightarrow n|a(x-y)$$ Donc nous avons deux choses: $$\begin{cases} n|a(x-y) \\ a\land n=1 \end{cases}\qquad~~$$ D'après le théorème de Gauss on en déduit: $$~~n|(x-y)$$ $$\Rightarrow \bar x =\bar y~~ $$ Et par la suite $~~f~~$ est injective. et puisque $~~E~~$ est un ensemble fini, alors $~~f~~$ est bijective.
$\bar 1~$ est dans $~E~$ donc il existe $~\bar x~$ dans $~E~$ tel que: $~f(\bar x)=1~~$ (d'après la surjection de $~f~$).
Ce qui implique: $~~\bar a\bar x=1~~$
Donc $~a~$ est inversible dans $~E~$.
Conclusion: $$a~\mbox{est inversible dans}~\mathbb Z/n\mathbb Z\Longleftrightarrow a\land n=1$$