Finding inverse modulo

Question

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!

Answer 1

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

Answer 2

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}$.

Hence, the answer is 1700.

Answer 3

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