How can I apply modular arithmetic?

Question

I am reading a text on Data Mining. Given the problem:

How do we determine that the inverse of 11 is 120?

Answer 1

We want to solve $11x \equiv 1 \pmod{120}$ for $x$.

So by Euclidean algorithm,

$120 = 11*10 + 10 \\ 11 = 10*1 + 1 \\ 10 = 1*10 + 0$

Now using the above and doing some substitutions we express $1$ as a linear combination of $120$ and $11$,

$1 = 11 - 10*1 = 11 - (120 - 11*10)*1 = 11*11 - 120*1$

Then by definition of congruence modulo $120$ we have,

$11*11 - 120*1 = 1 \implies 11*11 = 1 + 120*1 \implies 11*11 \equiv 1 \pmod{120}$

Therefore, $x = 11$ satisfies the given equation above.

What do you need to know to find inverses like I did above?

1. Euclidean algorithm.
2. For all integers $a, b$, not both zero, if $d = \gcd(a, b)$, then there exist integers $s, t$ such that $as + bt = d$.
3. For all integers $a, n$, if $\gcd(a, n) = 1$, then there exists an integer $s$ such that $as \equiv 1 \pmod n$, and so $s$ is an inverse for $a$ modulo $n$.

Of course, you also must know the definitions of divisibility, greatest common divisor, congruence modulo bla and Euclid's division lemma. You can learn all that from any elementary number theory or discrete math textbook.