How to prove the uniqueness of multiplicative inverse modulo n?

Question

From here, I have learned

However, I can't figure out why can it replace $1$ with $xc$, there is no such property here

Um, if $M\equiv N\mod n $ then $Mv\equiv Nv\mod n $ for all $v $. That's a basic property of multiplication. So as $xc \equiv 1\mod n $ we know $xcb\equiv 1b\mod n $. The thing that makes this specific to 1, is $1b=b$. If we had $xc=xb=2\mod n$ we could conclude $2b\equiv xcb\equiv 2c\mod n $ but we could not conclude $b=c\mod n$. — fleablood, Sep 27 '17 at 06:47
@fleabloodI also agree $xc≡1\mod n\ \ \ \ \ \ xb≡1\mod n \ \ \ \ \ \ $ we know $ xcb≡1b\mod \ \ \ \ n$ but it can't explain $xcb \equiv (xc)b \equiv (1)b \mod n$ — Chen Li, Sep 27 '17 at 09:00
Of course it can!!! $M\equiv N \mod n \implies Mv \equiv Nv \mod n$. So let M = 1, N = xc and v= b. So $1b \equiv xcb \mod n$. Then let M= xb; N=1 and v = c So $xbc \equiv 1c$. $1b = b$ and $xcb = xbc$ and $1c=c$ and $A\equiv B \mod n; A=C; B=D\implies C\equiv D \mod n$ take care of the rest.. — fleablood, Sep 27 '17 at 15:18

score 1 · Accepted Answer · answered Sep 27 '17 at 15:42

Steps:

$1*b \equiv 1*b \mod n$. (Reflexivity)

$1*b = b$. (Basic algebra: Multiplicative identity)

$b \equiv 1*b \mod n$. (Meaning of equality. $1*b$ and $b$ are the same thing.)

$xc \equiv 1 \mod n$ (Given)

$(xc)*b \equiv (1)*b \mod n$. ($ka \equiv kb \mod n$)

$(xc)*b = xcb = xbc=(xb)c;$ (Basic algebra: associativity and commutivity of multiplication.)

$(xb)c \equiv b \mod n$. (Meaning of equality: $(xb)*c = (xc)*b$ and $b=(1)*b$ and we already kknow $(xc)*b \equiv (1)*b \mod n$.)

$xb \equiv 1 \mod n$. (Given)

$(xb)c \equiv (1)c$ ($ka \equiv kb \mod n$)

$1*c = c$. (Basic algebra: multiplicative identity)

$(xb)c \equiv c \mod n$. (Meaning of equality)

$b \equiv (xb)c \mod n$. (Symmetry: $a \equiv b \mod n \implies b \equiv a \mod n$)

$(xb)c \equiv c \mod n$. (Just repeating the line above the last one again.)

$b \equiv c \mod n$ (Transitivity: $a \equiv b \mod n; b\equiv c \mod n\implies a \equiv c \mod n$.

That's the answer I want!!! thanks – Chen Li Sep 27 '17 at 16:55 — Chen Li, Sep 27 '17 at 16:55

score 0 · Answer 2 · answered Sep 27 '17 at 00:57

0

The property you are using is on the webpage linked. It is in the second set of bullet points. It reads:

If $a \equiv b\pmod{n}$ and $k$ is an integer, then $ka\equiv kb\pmod{n}$.

From $1\equiv xc \pmod{n}$ we can conclude $1b \equiv xcb \pmod{n}$.

answered Sep 27 '17 at 00:57

Jagriff

but how to explain $xbc \equiv 1c$, there is no property about division. – Chen Li Sep 27 '17 at 04:27
There's no property for division. But there sire as heck is one for multiplicTion. And for 1, multiplication is enough. – fleablood Sep 27 '17 at 06:30
It would not work for a=b=k mod n for any k except 1. – fleablood Sep 27 '17 at 06:31
xb=1 mod n and xc=1 mod n so b=(1)b=(xc)b=(xb)c=(1)c= c mod n. No division was done at all. Just substitution. – fleablood Sep 27 '17 at 06:50
@fleablood thanks! But the key is I didn't find property about substitution. If operator $=$, I'm sure about substitution, however, for $\equiv mod$, I'm confused about substitution. – Chen Li Sep 27 '17 at 08:51
You are confused that if $a = b$ and $a \equiv c \mod n$ that $b \equiv c\mod n$??????? – fleablood Sep 27 '17 at 15:25
Substitution ALWAYS works for EVERYTHING. $A=C$ means that $A$ and $C$ are the exact same thing. So if I say $A$ can be tossed into a gamflanger with a torqboop factor of Quince resulting in $57$. Then will have to be true that $C$ can be tossed into a gamflanger with a torqboop factor of Quince resulting in $57$. Because $A$ and $C$ are the same thing. – fleablood Sep 27 '17 at 15:28

2 Answers2