Hello,

You can take a look at the Chinese remainder theorem , as far as i see your problem, this is the only way i've found to get only elements of solution...

If you were asked to show that it had a congruence with 1 mod 1001, i would have given you Euler's theorem