Question

Find an integer x such that 37x $\equiv$ 1 (mod 101).}

Answer 1

$101=37\times2+27$
$37=27\times1+10$
$27=10\times2+7$
$10=7\times1+3$
$7=3\times2+1$

$\implies1=7-3\times2$
$\implies1=7\times3-10\times2$
$\implies1=127\times3-10\times8$
$\implies1=27\times11-37\times8$
$\implies1=101\times11-37\times30$

$\implies(101\times11+37\times(-30))\equiv37\times(-30)\equiv1\pmod{101}$

$\implies 37^{-1}\equiv-30\equiv(101-30)\equiv71\pmod{101}$