Find all integers x such that 111x equivalence 2 mod 1001Sol

Find all integers x such that 111x equivalence 2 mod 1001.

Solution

We have 111x 2 (mod 1001)

We know that ax b (mod n) has a solution iff gcd(a, n) is a divisor of b.

We have gcd (111,1001) = 1, so there is a solution since 1 is a factor of 2.

Now we find x by testing the 1001 different remainders from 0, 1, 2, …...1000.

Trial and error yields x = 992 since 111 * 992 mod 1001 = 2.  

So, The solution is x = 992 (mod 1001).