Hint: Use Euler's theorem. If you want the actual value of , you will need to compute . See here for how to do that.
Hint: Use Euler's theorem. If you want the actual value of , you will need to compute . See here for how to do that.
This can be done by a pigeon hole argument.
Choose 10001 different integers . Since there are 10000 remainders upon division by 10000, two of the numbers and in our set must have the property that and have the same remainder when divided by 10000. Say .
Hence for some integer , whereas . But 10000 and are relatively prime, hence for some integer , like you asked for.