Multiplicative Inverse of Modulo n is UNIQUE

Question

I am trying to prove this: $x,b,n\in \mathbb{Z}, \space xb\;(\mod{n}\;) = 1 \implies $ b is unique.

I have tried by using proof by contradiction. That is, assume there are integers $b,c$ where the above first condition is satisfied. Then we know that $xb \equiv xc\equiv 1 \;(\mod{n}\;)$ meaning $n|(x(b-c))$ and $xb = xc + k_1n, k_1 \in \mathbb{Z}$ and $xb + k_2n = 1, k_2 \in \mathbb{Z}$ and $xc + k_3n = 1, k_3 \in \mathbb{Z}$. That's all I got. I don't know how to proceed. Can anybody help? Thanks.

score 10 · Answer 1 · answered Sep 20 '15 at 06:39

10

Assume $xb\equiv xc\equiv1\pmod n$. Then:
\begin{align} b&\equiv 1b\\ &\equiv xcb\\ &\equiv xbc\\ &\equiv1c\\ &\equiv c\pmod n \end{align}

answered Sep 20 '15 at 06:39

Akiva Weinberger

23,062

score 3 · Accepted Answer · edited Mar 17 '23 at 01:51

3

Because $\gcd(x,n)=1$ and $n| x(b-c)\implies n|(b-c)\iff b\equiv c\pmod n$

edited Mar 17 '23 at 01:51

BakedPotato66

5

answered Sep 20 '15 at 05:20

lab bhattacharjee

274,582

@JackNicholson, $$4\equiv1,7\equiv1\pmod3$$ Congruent values are considered as same in modular arithmetic – lab bhattacharjee Sep 20 '15 at 05:37
Oh my goodness I finally get it now thanks! – Jack Nicholson Sep 20 '15 at 05:38
I'm new to finite field arithmetic, can you please explain to me why $n$ divides $b-c$ ? – Aravind A Apr 23 '20 at 04:29
1

@VivekanandV, https://en.wikipedia.org/wiki/Euclid%27s_lemma – lab bhattacharjee Apr 23 '20 at 04:51
@labbhattacharjee Thankyou very much !!! – Aravind A Apr 23 '20 at 04:55

Multiplicative Inverse of Modulo n is UNIQUE

2 Answers2

Linked