modular arithmetic - Find inverse modulo when modulo is smaller than the number

I know how to use the Euclidean algorithm to find the inverse modulo in most cases, but I can't wrap my head around the calculations when the modulo is smaller than the number I'd like to find the inverse for.

For example:

$$59x \equiv 1 \pmod{19}$$

has solution $$x \equiv 10 \pmod{19}$$ according to online calculators but I can't figure out why.

Answer

What you want is a solution to $59x \equiv 1 \pmod{19}$.

But $59x \equiv 1 \pmod{19} \Leftrightarrow (3(19)+2)x \equiv 1 \pmod{19} \Leftrightarrow 2x \equiv 1 \pmod{19}$.

I'm sure you can now solve the last equation, which is equivalent to the original.