let n be a positive integer and a,b be invertible integers modulo n such that a is congruent to b^-1 (mod n). What is the remainder when ab is divided by n?

Question

let n be a positive integer and a,b  be invertible integers  modulo n  such that a is congruent to b^-1 (mod n). What is the remainder  when ab is divided by  n?

ganeshie8 · Answer

$$a\equiv b^{-1}\pmod{n}$$
multiply both sides by $b$ and obtain
$$ba \equiv bb^{-1}\pmod{n}$$
$$ba \equiv 1\pmod{n}$$

that means the remainder when $ab$ is divided by $n$ is $1$

anonymous · Answer

plain and simple.. this was fast,  thanks ganeshie8

mathmath333 · Answer

invertible means inverse ?

ganeshie8 · Answer

Yes. for example, $2$ is not invertible in mod $6$ because there is NO integer satisfying $2x\equiv 1 \pmod{6}$

mathmath333 · Answer

ok

ganeshie8 · Answer

http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

mathmath333 · Answer

i am having an observation that 
$\large \color{black}{\begin{align} 
(n-1)^{-1}\pmod n\equiv (n-1) ,n\in \mathbb{N}\hspace{1.5em}\~\
\end{align}}$

ganeshie8 · Answer

thats right!
$$(n-1)(n-1) \equiv (0-1)(0-1) \equiv 1 \pmod{n}$$

ganeshie8 · Answer

the inverse of `n-1` is `n-1`

is same as saying

the inverse of `-1` is `-1`

ganeshie8 · Answer

thats true in any modulo..

mathmath333 · Answer

u mean

$\large \color{black}{\begin{align} 
(n)^{-1}\pmod m\equiv n ,\quad n<m,\{n,m\}\in \mathbb{N}\hspace{1.5em}\~\
\end{align}}$

ganeshie8 · Answer

the inverse of `-1` is `-1`  in any modulo

ganeshie8 · Answer

thats true because  (-1)(-1) = 1

ganeshie8 · Answer

Basically inverse of $a$ in modulo $n$ is an integer $x$ which satisfies below congruence
$$ax\equiv  1\pmod{n}$$

ganeshie8 · Answer

when $a=-1$, we see that $x=-1$ satisfies the above congruence. so $(-1)^{-1}= -1$

ganeshie8 · Answer

this is exact same as our normal multiplcation inverse. 
the multiplicative inverse of 2 is 1/2  because 2*1/2 = 1

ganeshie8 · Answer

maybe consider all the inverses in modulo 7 : $$ax\equiv 1\pmod{5}$$

$1^{-1} = 1$

$2^{-1} = 3$

$3^{-1} = 2$

$4^{-1} = 4$

ganeshie8 · Answer

$(1)(1) \equiv \color{blue}{1} \pmod{5}$
$(2)(3) \equiv 6\equiv \color{blue}{1} \pmod{5}$
$(3)(2) \equiv 6\equiv \color{blue}{1} \pmod{5}$
$(4)(4) \equiv 16\equiv \color{blue}{1} \pmod{5}$

ganeshie8 · Answer

*inverses in modulo $\color{red}{5}$

mathmath333 · Answer

$\large \color{black}{\begin{align}
a\equiv b^{-1}\pmod{n} \end{align}}$


when you multiplied the above by b ,
then should'nt it be this $\downarrow$



$\large \color{black}{\begin{align}


ab\equiv b^{-1}b\pmod{nb} \~\
ab\equiv 1\pmod{nb} \~\
\end{align}}$

mathmath333 · Answer

@ganeshie8

ganeshie8 · Answer

yes both are same :  $ab\equiv ba \pmod{n}$

mathmath333 · Answer

i mean this one 

$\large \color{black}{\begin{align}
\color{blue}{1.}ab\equiv 1\pmod{nb} \~\
\end{align}}$
$\large \color{black}{\begin{align}
\color{blue}{2.}ab\equiv 1\pmod{n} \~\
\end{align}}$

ganeshie8 · Answer

Ahh okay we have this congruence property : 
$$a\equiv b \pmod{n} \implies   ac\equiv bc\pmod{n}$$

ganeshie8 · Answer

thats true because $n|(a-b) \implies  n|(ac-bc)$