Congruence modulo $n$ - Solving equations when having a big $n$

Question

We are working in: $ \mathbb{Z}_{103}$

Find x for which: $ \widehat{61}\cdot x = \widehat{1} $

When I learned how to solve equations like this my teacher told me to check all available values. That method is working well and fast when working with $ \mathbb{Z}_{n} $ with a n which is not bigger.

But in this case what can I do?

Thank You!!

PS: I know I should write the numbers with a "^" over the number but I don't know how to do that in MathJax. Please edit my question if necessarry. EDIT: Thank you Ross Millikan for \widehat{}!

Answer 1

Doing arithmetic modulo $\;103\;$ all through:

$$61=-42=-6\cdot7\;\;,\;\;\begin{cases}6\cdot17=102=-1\implies-6^{-1}=17\\{}\\7\cdot44=308=-1\implies 7^{-1}=-44=59\end{cases}$$

Thus finally

$$(-6)^{-1}\cdot7^{-1}=17\cdot59=\ldots$$

Answer 2

More generally, you go through writing explicitly the Bezout identity.

If $(a,n)=1$ you know that there are integers $A$ and $B$ such that $$ aA+nB=1. $$ The integers $A$ and $B$ can be found by a (possibly repeated) application of the division algorithm.

In terms of congruences the identity displayed reads $$ aA\equiv1\bmod n $$ which is just what you want.

Answer 3

${\rm mod}\ 103\!:\,\ \dfrac{1}{61}\overset{ \times\, 2}\equiv \dfrac{2}{19}\,\overset{\times\,5}\equiv\,\dfrac{10}{-8}\equiv\dfrac{5}{-4}\equiv\dfrac{108}{-4}\equiv-27\ $ by Gauss's algorithm.