Prove if a (mod n) has a multiplicative inverse, then it's unique

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.

If $\,b,b'$ are inverses of $\,a\,$ then $\ b\equiv b(ab')\equiv (ba)b'\equiv b'.\, $ Note that the proof uses only commutativity and associativity so it works more generally than for the integers mod $\,n.\,$

Note $ $ It's a slick way of cancelling $\,\color{#c00}a\,$ from $\,\color{#c00}ab\equiv 1\equiv \color{#c00}ab'$ by scaling by $\,\color{#c00}a^{-1},\,$ yielding $\,b\equiv 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 $\,bab'\,$ which can be reduced by both rules $\,ab\to 1,\ ab'\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.

For the first part note as $(n,a) = 1$, then there exist $x,y \in \mathbb{Z}$, s.t. $nx + ay = 1$. Multiply both sides by $b$ and you will get $nxb + (ab)y = b$. The LHS is obviously divisible by $n$, so then the RHS must be too. Hence $n \mid b$.

This thing proves that the inverse exist. To note that it's unique modulo $n$ assume that $aa_1 \equiv 1 \pmod n$ and $aa_2 \equiv 1 \pmod n$. Then we have that there exist integer $x,y$ s.t. $aa_1 + nx = 1$ and $aa_2 + ny = 1$. Subtracting the two equations we have that $a(a_1 - a_2) = n(y-x) \implies a(a_1 - a_2) \equiv 0 \pmod n \implies a_1 \equiv a_2 \pmod n$. Hence the multiplicative inverse is unique in $\mathbb{Z}_n$

What you have shown already is a technique that, using the Extended Euclidean Algorithm will give you the inverse (if it exists). Note also that you can determine if an element $a \mod n$ has an inverse by checking that they have no common divisors (that is, $\gcd(a,n)=1$).

Now to answer your question. Suppose that you have two multiplicative inverses $b,c$ such that $ab\equiv 1 \equiv ac \mod n$. (Then you also have $ba\equiv 1 \equiv ca \mod n$) Consider

$b \equiv b\cdot 1 \equiv bac \equiv 1\cdot c \equiv c \mod n$.

That shows that modulo $n$, there exists a unique inverse. This technique is very useful and you can also use it to show that: there exists exactly one $0$-vector in every vector space, group, ring... and every invertible element in a group, ring... has a unique inverse.

Note: For instance $2\cdot 3 \equiv 1 \mod 5$, but also $2\cdot 8 \equiv 1 \mod 5$ (Why is this not a contradiction to the above?)