Thread: Solve a Congruence

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!

Originally Posted by meggnog

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!