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!

Printable View

- February 6th 2010, 11:53 AMmeggnogSolve 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! - February 7th 2010, 05:35 AMswallenberg
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!