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.
Best 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.