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

• 59 and 1 are not congruent mod 19! – user21820 Dec 12 '14 at 13:07
• @user21820 : What does that mean? If you check the link you can see the calculation I'd like to find the steps for. – OptimusCrime Dec 12 '14 at 13:09
• You wrote $59 \equiv 1 \pmod{19}$. That is simply false! See my answer for what you should write. – user21820 Dec 12 '14 at 13:10
• It just means that $59\cdot 10\equiv 1\bmod 19$. – Dietrich Burde Dec 12 '14 at 13:10
• By the way I didn't downvote your question but I can see why someone might for the reason I take issue with what you wrote. – user21820 Dec 12 '14 at 13:13

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}$.
• Thanks. I'll accept as soon as I can. What about $$19x \equiv 1 \pmod{59}$$? This method does not work then. – OptimusCrime Dec 12 '14 at 13:39
• What method are you referring to? The algebraic manipulations I showed above is to solve your question of what to do when you want to find the inverse of $x$ mod $m$ where $|x| > m$. In any case, once you find that $59 \cdot 10 \equiv 1 \pmod{19}$, you have $59 \cdot 10 - 19k = 1$ for some integer $k$ and hence you also have found an inverse of 19 mod 59 by definition of inverse. – user21820 Dec 12 '14 at 14:01