Question

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

Answer 1

`101=37*2+27`

`37=27*1+10`

`27=10*2+7`

`10=7*1+3`

`7=3*2+1`


`\implies1=7-3*2`

`\implies1=7*3-10*2`

`\implies1=127*3-10*8`

`\implies1=27*11-37*8`

`\implies1=101*11-37*30`


`\implies(101*11+37*(-30))\equiv37*(-30)\equiv1\pmod{101}`


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