Question: how many integers a from 1 to 1000 are there such that a 100 1 is divisible by 1000?
Answer: Now, 100 is a multiple of both ϕ(8)=4 and ϕ(125)=100 and so all numbers that are coprime with both 8 and 125 are solutions of this system. Therefore, the solutions of x100≡1mod1000 are exactly the numbers coprime with 1000. There are ϕ(1000)=400 solutions in [1,1000].