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.

  • 1
    $\begingroup$ 59 and 1 are not congruent mod 19! $\endgroup$ – user21820 Dec 12 '14 at 13:07
  • $\begingroup$ @user21820 : What does that mean? If you check the link you can see the calculation I'd like to find the steps for. $\endgroup$ – OptimusCrime Dec 12 '14 at 13:09
  • $\begingroup$ You wrote $59 \equiv 1 \pmod{19}$. That is simply false! See my answer for what you should write. $\endgroup$ – user21820 Dec 12 '14 at 13:10
  • $\begingroup$ It just means that $59\cdot 10\equiv 1\bmod 19$. $\endgroup$ – Dietrich Burde Dec 12 '14 at 13:10
  • $\begingroup$ 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. $\endgroup$ – 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}$.

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

  • $\begingroup$ Thanks. I'll accept as soon as I can. What about $$19x \equiv 1 \pmod{59} $$? This method does not work then. $\endgroup$ – OptimusCrime Dec 12 '14 at 13:39
  • $\begingroup$ 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. $\endgroup$ – user21820 Dec 12 '14 at 14:01
  • $\begingroup$ @OptimusCrime: Anyway if you find any answer on Math SE helpful, not just to your questions, you can upvote it. $\endgroup$ – user21820 Dec 12 '14 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.