Assume that an integer $a$ has a multiplicative inverse modulo an integer $n$. Prove that this inverse is unique modulo $n$.
I was given a hint that proving this Lemma:
\begin{align}
n \mid ab \ \wedge \ \operatorname{gcd}\left(n,a\right) = 1
\qquad \Longrightarrow \qquad
n \mid b
\end{align}
should help me in finding the answer.
Here are my steps in trying to solve the problem:
\begin{align}
\operatorname{gcd}\left(n,a\right) = 1
& \qquad \Longrightarrow \qquad
sn + ta = 1
\qquad \Longrightarrow \qquad
sn = 1 – ta \\
& \qquad \Longrightarrow \qquad
1 \equiv ta \mod n
\qquad \Longrightarrow \qquad
ta \equiv 1 \mod n .
\end{align}
I know that having the GCD of m and a equal to 1 proves there is a multiplicative inverse mod n, but I'm not sure on how to prove $n \mid b$ with and how it helps prove the multiplicative inverse is unique.
Best Answer
If $\,b,\bar b$ are inverses of $\,a\,$ then $\ b\equiv b(a\bar b)\equiv (ba)\bar b\equiv \bar b\, $ by Congruence Product Rule. We used only commutativity & associativity of products so the proof works in any commutative ring or monoid.
Note $ $ The proof is just a slick way of cancelling $\,\color{#c00}a\,$ from $\,\color{#c00}ab\equiv 1\equiv \color{#c00}a\bar b\,$ by scaling by $\,\color{#c00}a^{-1},\,$ yielding $\,b\equiv \bar b.\,$ Hence we see that the uniqueness of inverses is simply a special case of the general fact that invertible elements are cancellable, via scaling by the inverse.
Proofs like this can often be discovered by a general method of "overlapping" equations to find a term that both equations apply to (above the overalapped term is $\,ba\bar b\,$ which can be reduced by both rules $\,ab\to 1,\ a\bar b\to 1).\, $ Below is another example with further explanation.
Below I will explain a general way to discover a simpler proof (vs. pulling it out of a hat like magic). The key idea is very simple: one can discover consequences of identities (axioms) by "overlapping" them: $ $looking for a "unified" term that they both apply to. Let's try that to prove the uniqueness of additive identity elements. Suppose that $\,0\,$ and $\,0'$ are both additive identities. This means that
$$\begin{eqnarray} x = && \color{#0a0}0 + \color{#c00}x\\ && \color{#0a0}y + \color{#c00}{0'} = y\\ \hline \Rightarrow\ \ 0' = && 0 + 0' = 0\end{eqnarray}$$
where we chose the values of the specialization $\,\color{#0a0}{y=0},\ \color{#c00}{x = 0'}\,$ in order unify $\,0+x\,$ with $\,y+0', \,$ yielding the "unified" term $\,0+0'\,$ that both axioms apply to. Applying both axioms to the unified term we can rewrite it in two different ways, deducing the new consequence $\,0' = 0.\,$ Presto!
This is a very widely applicable method of deriving consequences of axioms, i.e. by "unifying" or "overlapping" terms of both so that both axioms apply, yielding a rewriting of the term in two different ways (e.g. another example). In fact in some cases it can be used to algorithmically derive all of the consequences of the axioms, so yielding algorithms for deciding equality, e.g. see the Knuth-Bendix equational completion algorithm and the Grobner basis algorithm, and see George Bergman's classic paper The Diamond Lemma in Ring Theory.