1
$\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$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @JackNicholson, $$4\equiv1,7\equiv1\pmod3$$ Congruent values are considered as same in modular arithmetic $\endgroup$ – lab bhattacharjee Sep 20 '15 at 5:37
  • $\begingroup$ Oh my goodness I finally get it now thanks! $\endgroup$ – Jack Nicholson Sep 20 '15 at 5:38
5
$\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$

Your Answer

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

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