# Finding inverse modulo

I'm trying to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19.

Here is what I have done before I got stuck:

1. $x ≡ 9 \mod 19$
2. $\gcd(9,19) = \gcd(19,9)\\ 19 = 9*2 + 1\\ 9 = 1*9 + 0$
3. Bezout's Theorm

$\gcd (19,9) = m*19 + n*9\\ 1 = 19 - 9*2\\ = 1*19 -2*9$

THUS, x = -2 mod 19 = 17 mod 19 = 17

BUT! 17 is not a multiple of 100, so from here, what do I do to find "the smallest positive multiple of 100" that leaves remainder 9 when divided by 19?

Thanks!

• Try LCM, instead of modular arithmetic. Commented May 14, 2013 at 23:13
• LCM on which numbers? Commented May 15, 2013 at 4:37
• Now that you edited the question, LCM no longer works. Previously, the number you wanted was a multiple of 19 and 100, hence you take the LCM of 19 and 199. Commented May 15, 2013 at 4:45

You seek a multiple of $19$, which is prime and not a divisor of $100$. Hence the smallest multiple of $100$ that includes $19$ as a divisor is $1900$.

• Thanks for your answer, but I had a typo. I was trying to find "the smallest positive multiple of 100" that leaves remainder 9, not 0, when divided by 19. I found the inverse to be 17 but that's not a multiple of 100, can you help me from here? thanks! Commented May 15, 2013 at 4:36
• Once you have an answer and multiple comments, you really shouldn't change the question like this; accept the answer and make a new question. Commented May 15, 2013 at 12:13

We have $100 N \equiv 9 \pmod{19}$, and want to find the smallest value of $N$.

This is equivalent to $5 N \equiv 9 \pmod{19}$.

This is equivalent to $N \equiv 36 \equiv 17 \pmod{19}$, where we multiplied by $4 = 5^{-1} \pmod{19}$.

mod $19\!:\ 100\equiv 5,\,\ 9\equiv -10\ \,$ so $\, \ 100 n\equiv 9 \iff 5n\equiv -10 \iff n\equiv -2\equiv 17.$