Please help with this problem:
49x is congruent to 4000 (mod 999).
I need to solve for x, and I can't figure out how to work it. Trying to use the Euclidean Algorithm.
Thanks all!
To begin with one can notice the following:
4000 = 4*999 + 4 ≡ 4 (mod 999)
So, we've reduced the problem to 49x ≡ 4 (mod 999)
Now, by Euclid's algorithm
999 = 20*49 + 19
49 = 2*19 + 11
19 = 11 + 8
11 = 8 + 3
8 = 3*3 - 1
Going backwards in the algorithm you'll get the following
1 = 367*49 - 18*999 ≡ 367*49 (mod 999)
with other words: the inverse of 49 in Z_999 is 367
So,
49x ≡ 4 (mod 999)
367*49x ≡ 367*4 (mod 999)
x ≡ 367*4 = 1468 = 999 + 469 ≡ 469 (mod 999)
x ≡ 469 (mod 999)
and that's it!