Solving inverse of modulo

Question

How can I solve for: $$5^{-1} \mod 3$$ ?

I am having hard time to understand how it is solve so please make it easy for me how it works.

Answer 1

$5^{-1}$ is the number such that if you multiply by $5$, you get $1$. In other words, it's the solution to $5x\equiv 1\pmod 3$.

Modulo $3$, multiplying by $5$ is the same as multiplying by $2$, so $5^{-1}$ is the same as $2^{-1}$.

Now, what number (modulo $3$) is such that if you multiply by $2$, you get $1$? In other words, solve $2x\equiv 1\pmod 3$. There are only three different values that $x$ could have, so try them all, and you will find the answer.

There are ways of actually finding this $x$, in case we are working modulo $n$ and $n$ becomes too large to feasibly test every case. Specifically, the extended Euclidean algorithm will let you find $x$ in $O(\log n)$ steps, assuming a solution exists (and if a solution doesn't exist then the algorithm will tell you that too).

Answer 2

First note $5=2$. Then consider $2\times ?=1$ where you can try $?$ from $0,1,2$. Not a tedious task.