How to solve $97x \equiv 1 \mod 61$ in a quick way?
I tried to solve it in the Diophantine equation form $97x + 61y = 1$ by using Euclidean algorithm and got the sample result of $x = 22$ and $y = 35$.
However, the calculation took me quite long to do it, even if I was highly concentrated it would still take me $5-7$ min to solve.
I want to ask whether we had any other way to quickly solve these kind of linear congruence equations?
You can add and subtract in congruences just like normal equations. You can reduce numbers to the range $0,1,\ldots,m-1$, where $m$ is the modulus. Or reduce to a small negative number if that's easier. You can also cancel a factor from the left and right hand sides, provided the factor you cancel is coprime to the modulus. In the present case you could very quickly solve the congruence like this: $$\eqalign{97x\equiv1\pmod{61}\quad &\Leftrightarrow\quad 36x\equiv1\pmod{61}\cr &\Leftrightarrow\quad 36x\equiv-60\pmod{61}\cr &\Leftrightarrow\quad 3x\equiv-5\pmod{61}\cr &\Leftrightarrow\quad 3x\equiv-66\pmod{61}\cr &\Leftrightarrow\quad x\equiv-22\pmod{61}\cr &\Leftrightarrow\quad x\equiv39\pmod{61}\ .\cr}$$ The two cancellation steps have removed $12$ and $3$, each of which is coprime to $61$.