Multiplicative Inverse of Modulo n is UNIQUE

$\begingroup$

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.

$\endgroup$

2 Answers

$\begingroup$

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

$\endgroup$ $\begingroup$

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

$\endgroup$ 5

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy