I was given a hint that proving this Lemma:

enter image description here

should help me in finding the answer.

Here are my steps in trying to solve the problem:

enter image description here

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 enter image description here with and how it helps prove the multiplicative inverse is unique.

up vote 1 down vote accepted

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$

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.\,$

Remark $\ $ The above proof can 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.

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?)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.