Dividing Modulo

Question

In the solution to a

$ax \equiv b \pmod m$

$71x \equiv 1 \pmod{771} \implies x \equiv -76 \pmod{771}$

and

$71x \equiv 1 \pmod{77} \implies x \equiv -13 \pmod{77}$

I'm unsure of how these congruences hold, how does one divide modulo $771$?

Answer 1

It's worth to notice that $1\equiv -770\pmod{771}$ and $71\equiv -700\pmod{771}$ then you can divide by $70$ to get $$-10x\equiv -11\pmod{771}$$ which is equivalent to $$10x\equiv 11\pmod{771}$$ and since $11\equiv -760\pmod{771}$ we have $$10x\equiv-760\pmod{771}$$ dividing by $10$ we get $$x\equiv-76\pmod{771}$$

Answer 2

The calculations are easy using a fractional form of the Extended Euclidean Algorithm.

${\rm mod}\ 77\!:\, \ \dfrac{0}{77}\overset{\large\frown}\equiv \dfrac{1}{71}\overset{\large\frown}\equiv\dfrac{-1}6\overset{\large\frown}\equiv\dfrac{13}{-1}$

Equivalently, without fractions

$\begin{array}{rrl} [1]\!:\!\!\!& 77\,x\!\!\!&\equiv\ 0\\ [2]\!:\!\!\!& 71\,x\!\!\!&\equiv\ 1\\ [1]\ \ -\ \ [2]=:[3]\!:\!\!\!& 6\,x\!\!\!&\equiv -1\\ [2]-12[3]=:[4]\!:\!\!\!& -x\!\!\! &\equiv 13\\ \end{array}$

Similarly for the first inversion

${\rm mod}\ 771\!:\,\ \dfrac{0}{771}\overset{\large\frown}\equiv \dfrac{1}{71}\overset{\large\frown}\equiv \dfrac{-11}{-10}\overset{\large\frown}\equiv \dfrac{-76}1$