Question

How many positive integers N are there such that the least common multiple of N and 1000 is 1000?

Answer 1

This question reminds me of Euler's Totient Function.

Answer 2

http://en.wikipedia.org/wiki/Euler's_totient_function

There you go. You are only looking for \(\phi (1000)\).

Answer 3

<Stares wide-eyed and with disbelief>
O.O

Answer 4

Too bad gourav isn't online right now :/
The prime factorisation for 1000 is
\[\Large 2^3\cdot 5^3\]
Now, if an integer were to have any prime factors OTHER THAN 2 or 5, then its Least Common multiple with 1000 would also have a prime factor other than 2 or 5, which means it can't be 1000. (Verify!)

Now, we have established that any integer N must only have 2 or 5 for its prime factors.
And of course, there can't be any powers of 2 or 5 greater than 3, or else, the LCM won't be 1000 (Verify!)

So, we have
\[\Large N = 2^p\cdot 5^q\qquad p,q\in\mathbb{Z}^+\qquad 0\le p,q\le 3\]
This gives 16 possibilities.
Namely,
1,2,4,8,
5,10,20,40,
25,50,100,200,
125,250,500,1000