Comme nous l'avons déjà mentionné, il n'est pas toujours permis de diviser les deux membres d'une égalité modulo $n$ par un nombre entier. Nous perdons par exemple l'égalité lorsque l'on divise les deux membres de l'expression $6 \equiv 16 \pmod{10}$ par $2$.
Il existe cependant certains cas où la division est permise. Pour trouver dans quels cas cela nous est permis, il nous faut revenir à la définition première de division. Lorsque nous travaillions sur les réels, nous savions que tout nombre non-nul admettait un inverse (pour tout $x \in \mathbb{R}_0$, il existe $y \in \mathbb{R}_0$ tel que $x\cdot y = 1$). Il nous était alors permis de diviser les deux membres d'une équation par $x$, puisque cela revenait à les multiplier par $y$. S'il nous était possible de diviser par les nombres $x$ non nuls, c'était en fait parce que chacun d'eux possédait un inverse.
Il est donc naturel de définir une notion d'inverse modulo $n$.
Dès lors, si $n$ est fixé et $x$ possède un inverse modulo $n$, il nous est autorisé de diviser les deux membres d'une égalité modulo $n$ par le nombre $x$ (puisque cela revient à mutliplier chacun d'eux par $y$). Dans notre contre-exemple, $n$ était égal à $10$ et nous souhaitions diviser par $2$. Nous ne pouvions pas le faire car $2$ ne possède pas d'inverse modulo $10$. En effet, $2 \cdot y$ est toujours pair et ne saurait être égal à $1$ modulo $10$.
Existence d'inverse
Pour diviser par $x$, il suffit donc que $x$ possède un inverse modulo $n$. Le mieux serait donc de trouver un critère nous permettant de décider si $x$ possède un inverse modulo $n$ ou non. Il existe en fait un tel critère, dont la démonstration est preque immédiate grâce au théorème de Bézout :
Proposition (existence d'un inverse)
Le nombre $x$ possède un inverse modulo $n$ si et seulement si $(x, n) = 1$.
Démonstration
On a la suite d'équivalences suivante :
$$\begin{align}
& x \text{ possède un inverse modulo } n\\
\Leftrightarrow \ & \exists\ y \quad\text{tel que} \quad x\cdot y \equiv 1 \pmod n\\
\Leftrightarrow \ & \exists\ y \quad\text{tel que} \quad x\cdot y - 1 \quad \text{est divisible par } n\\
\Leftrightarrow \ & \exists\ y, k \quad\text{tels que} \quad x\cdot y - 1 = n\cdot k \\
\Leftrightarrow \ & \exists\ y, k \quad\text{tels que} \quad x\cdot y - n\cdot k = 1
\end{align} $$ Or, par le théorème de Bézout, de tels $y$ et $k$ existent si et seulement si $1$ est divisible par $(x, n)$. Autrement dit, on doit avoir $(x, n) = 1$ ce qui signifie que $x$ possède un inverse si et seulement si il est premier avec $n$.
Dans notre contre-exemple, on avait $(2,10) = 2 \neq 1$ et $2$ ne possédait donc pas d'inverse modulo $10$.
Construction de l'inverse
Dans notre contexte (pour diviser les deux membres d'une égalité), il n'est pas nécessaire de connaître l'inverse de $x$, il suffit de savoir qu'il existe. Cependant, il arrive que connaître l'inverse d'un nombre modulo $n$ soit utile, comme ce sera le cas pour résoudre des équations modulaires.
Pour le trouver, au vu de la démonstration concernant l'existence d'un inverse, il suffit de trouver des nombres $y$ et $k$ tels que $x\cdot y - n \cdot k = 1$. Cela se fait exactement comme nous cherchions les coefficients intervenant dans le théorème de Bézout (en remontant l'algorithme d'Euclide). Le nombre $y$ est alors l'inverse de $x$ modulo $n$ (en effet, vu que $n \cdot k \equiv 0 \pmod n$, on a $x\cdot y \equiv 1 \pmod n$)
Cherchons par exemple l'inverse de $17$ modulo $59$. On calcule d'abord $(17, 59)$ à l'aide de l'algorithme d'Euclide :
$$\begin{align}
59 &= 3\cdot 17 + 8 \\
17 &= 2 \cdot 8 + \boxed{1} \\
8 &= 8\cdot 1 + 0
\end{align}$$ On a donc $(17, 59) = 1$, ce qui signifie que $17$ possède bien un inverse modulo $59$. Pour le trouver, on remonte l'algorithme. On a :
$$\begin{align}
1 &= 17 - 2\cdot 8\\
&= 17 - 2\cdot(59 - 3\cdot 17)\\
&= 7\cdot 17 - 2\cdot 59
\end{align}$$ Et l'inverse de $17$ est donc $7$. On peut le vérifier aisément puisque $7\cdot 17 \equiv 119 \equiv 1 \pmod{59}$.
Unicité de l'inverse
L'inverse d'un nombre modulo $n$ ne semble a priori pas unique vu que nous avions remarqué que les coefficients intervenant dans le théorème de Bézout ne l'étaient pas. D'ailleurs, tous les nombres égaux à $7$ modulo $59$ sont également des inverses de $17$. Cela dit, n'oublions pas que nous travaillons modulo $n$. L'inverse d'un nombre est en fait bien unique modulo $n$ (c'est-à-dire que parmi les nombres entre $0$ et $58$, seul $7$ est inverse de $17$ modulo $59$).
Proposition (unicité de l'inverse)
Si $x$ possède un inverse modulo $n$, alors cet inverse est unique modulo $n$.
Démonstration
Si $y_1$ et $y_2$ sont des inverses de $x$ modulo $n$, alors par définition on a
$$ x \cdot y_1 \equiv 1 \equiv x \cdot y_2 \pmod n.$$ Mais nous pouvons à présent diviser les deux membres extrêmes de l'égalité par $x$ puisque celui-ci possède un inverse modulo $n$, d'où
$$ y_1 \equiv y_2 \pmod n.$$