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

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

I did found the solution to this problem , but I did it by brute force. When I was tackling this problem, I didn't know what multiples where so I had to look it up. I think I had a blurred view of what multiples are. So, to help me, I found the definition: multiples are some number multiplied by an integer. For instance, the multiples of 4 are ...-8,0,4,8,12,16,20 and so on.

And the least common multiple of 4 and 5(as in an example to help clarify the problem) is 20 because

The multiples of 4: 4,8,12,16,20

The multiples of 5: 5,10,15,20,25

I know I probably wasted your time writing that stuff above, but it helps me because I get forget what it means to find multiples.

Now back to the problem. The problem asks to find all values n such that 1000 is divisible by n. So basically, I just listed them like this:

n: 1 2 ,4, 5, 8, 10, 20, 25, 40, 50,100,125,200,250,500,1000

1000/n has remainder 0? : There are 16 n's.

So again, I feel like there's a trick or method in the problem that I don't know in order to solve the problem. Do you know any other way,besides my brute force method, in solving this problem?

Thank you.

• +1 for correctly going from "I don't know what multiple means" to "oh, it's just asking for the divisors of 1000". – Henning Makholm Jan 2 '14 at 4:12

Yes, we have another way to solve your question.

$N$ has to be a divisor of $1000$, and any divisor of $1000$ satisfies your condition. This means that what you want is the number of the divisors of $1000.$

By the way, we have a formula to count the number of the divisors of a number $a$.

It is known that the number of the divisors of a number $a$ such that $$a={p_1}^{a_1}\cdot {p_2}^{a_2}\cdots {p_k}^{a_k}$$ is $$(a_1+1)(a_2+1)\cdots (a_k+1)$$ where $p_1\lt p_2\lt\cdots p_k$ are prime numbers.

Noting that $1000=2^3\cdot 5^3,$ the answer for your question will be $$(3+1)\cdot (3+1)=16.$$

• Nice solution mathlove..... – juantheron Jan 2 '14 at 4:18
• @juantheron: Thanks a lot! – mathlove Jan 2 '14 at 4:41

$1000=2^35^3$, so for a divisor of 1000, you have 4 choices for the exponent of 2 and 4 choices for the exponent of 5, giving 4*4=16 divisors of 1000.